AVL树剖析

devtools/2025/4/1 15:37:03/

目录

引入

概念

AVL树的实现

插入

找合适位置并插入

平衡因子更新

平衡因子出错

父节点为2，子节点为1

父节点为-2，子节点为-1

父节点为2，子节点为-1

父节点为-2，子节点为1

函数检查

引入

AVL树也是搜索树，其被称为二叉平衡搜索树，AVL树实际上是对二叉树搜索树的一种优化。普通二叉搜索树可能出现极端情况——一端很长，如下，这种极端情况会导致二叉搜索树退化为单枝树，搜索效率急剧下降。

二叉搜索树-CSDN博客文章浏览阅读477次，点赞19次，收藏8次。关于搜索二叉树的结构及原理的分析，对搜索二叉树的算法进行剖析，实现搜索二叉树的结构及功能，对部分函数使用递归的方法实现 https://blog.csdn.net/2401_87944878/article/details/146377883

AVL树是基于二叉搜索树出现的，所以其也满足二叉搜索树的要求：左树小于节点，右树大于节点。关于普通二叉搜索树详细介绍课移至上方链接。

概念

AVL树基于普通二叉搜索树基础上，增加了一个要求：左右子树的高度差的绝对值不超过1。

左右子树的高度差又被称为平衡因子，高度差的绝对值不超过1也就意味着平衡因子只能是1，0，-1。

平衡因子的计算方法是：平衡因子=右树高度-左树高度。

下面展示的就是各个节点的平衡因子（以下两棵树非AVL树）。

 

AVL树也正是通过调节平衡因子时刻保持在正常范围内，使得树不会出现"一边长"的问题。

所以在每一次向二叉树种插入值后，多要进行平衡因子的检查，有平衡因子出错就及时进行调整。

总结AVL树的性质：1）每一个节点的左右子树是AVL树；2）左右子树的平衡因子的绝对值不超过1。

AVL树的实现

AVL树的每一个节点包含：左右子树，父节点，存储的数（数据用pair结构体存储），平衡因子。

template<class K,class V>
struct AVLTreeNode
{//默认构造函数AVLTreeNode(const pair<K,V>& kv=pair()):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}pair<K, V> _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;             //平衡因子
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public://默认构造AVLTree():_root(nullptr){}private:Node* _root;   //此处也可以使用缺省值代替默认构造：  Node* _root=nullptr;
};

插入实现

与普通二叉搜索树一样，AVL树的插入也是先找到合适位置插入。

插入包含3个步骤：1）找数据插入位置并将数据插入；2）向上更新平衡因子；3）当出现错误平衡因子时，对树进行调整。

找合适位置并插入

通过二叉搜索树的性质（左树小于节点，右树大于节点）找到合适位置，再将数据插入到合适位置即可。

//插入
bool Insert(const pair<K, V>& kv)
{Node* newnode = new Node(kv);if (_root == nullptr)  //空树直接进行替代{ _root = newnode;return true;}//非空树先找节点插入位置Node* pcur = _root;   //寻找目标位置Node* parent = nullptr;  //保留目标位置的父节点while (pcur){if (pcur->_kv.first > kv.first){parent = pcur;pcur = pcur->_left;}else if (pcur->_kv.first < kv.first){parent = pcur;pcur = pcur->_right;}else   //相等说明节点中已存在，不能再进行插入{return false;}}//跳出循环，找到目标位置//将新节点插入if (parent->_kv.first > kv.first)  //通过父节点与插入数据比较，找到新节点在左还是右{parent->_left = newnode;}else{parent->_right = newnode;}newnode->_parent = parent;//进行平衡因子的调整//......
}

平衡因子更新

更新平衡因子方法：

1）不论如何新插入的节点没有左右子树，所以其平衡因子是0；

2）对于新插入的节点只会影响其所在节点的子树高度，因此只需要向上更新节点平衡因子即可。

3）根据平衡因子计算公式：平衡因子=右树高度-左树高度。当新节点插入到父节点的左树上：父节点平衡因子-1；当插入到父节点的右树上：父节点+1；

4）当向上更新时，父节点平衡因子调整后是0就不需要继续向上更新了。原因：当一个节点平衡因子变成0，不论是其+1还是-1都意味着：新增节点仅仅是使得当前节点的左右树平衡了，当前树的高度并没有发生变化，不需要继续向上调整。

//进行平衡因子的调整
Node* cur = newnode;
while (parent)   //此处条件是parent不为空。到达根时，_root的父节点为空，停止调整
{ if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//检查平衡因子if (parent->_bf == 1 || parent->_bf == -1){//继续向上调整cur = parent;parent = cur->_parent;}else if (parent->_bf == 0){return true;  //插入完成，不用继续向上调整}else if (parent->_bf == 2 || parent->_bf == -2){//平衡因子错误，对树进行调整break;}else //添加额外的else保证在平衡因子不在预定范围内时即使报错。{perror("平衡因子不在范围内");  }
}if (parent == nullptr)
{return true;
}

平衡因子出错

平衡因子出错分为4中情况，也就对应4种处理方法，依据平衡因子划分。

单旋（一侧高）：1）父节点平衡因子是2，子节点平衡因子是1；  

2）父节点平衡因子是-2，子节点平衡因子是-1；

多旋：3）父节点平衡因子是2，子节点平衡因子是-1；

4）父节点平衡因子是-2，直子节点平衡因子是1；

对于平衡因子调整的方法是：

1）保持搜索树的结构；

2）变成平衡树并降低树的高度。

父节点为2，子节点为1

左旋：对于一边高的情况，才有单旋来实现。将父节点左旋，即减小了子树的高度也解决了平衡因子异常的问题。

此处需要调整的节点：parent的父节点和右节点；cur的父节点和右节点；curleft(cur的左节点)父节点。

void RotateL(Node* parent)
{//调整parent的父节点，右节点//调整cur的父节点，左节点//调整curleft的父节点//调整parent的父节点的指向Node* pparent = parent->_parent; Node* cur = parent->_right;Node* curleft = cur->_left;cur->_parent = pparent;if (parent == _root)   //注意：如果parent是根，在旋转后要对根进行更新{_root = cur;}else{if (pparent->_left == parent){pparent->_left = cur;}else{pparent->_right = cur;}}parent->_right = curleft;parent->_parent = cur;if(curleft)curleft->_parent = parent;;cur->_left = parent;//将平衡因子进行调整cur->_bf = parent->_bf = 0;
}if (parent->_bf == 2 && cur->_bf == 1)
{//进行左旋RotateL(parent);
}

父节点为-2，子节点为-1

右旋：将父节点进行右旋。

//进行右旋
void RotateR(Node* parent)
{//调整parent的父节点，左节点//调整cur的父节点，右节点//调整curright的父节点//调整parent的父节点的指向Node* pparent = parent->_parent;Node* cur = parent->_left;Node* curright = cur->_right;cur->_parent = pparent;if (parent == _root)   //注意：如果parent是根，在旋转后要对根进行更新{_root = cur;}if (pparent){if (pparent->_left == parent){pparent->_left = cur;}else{pparent->_right = cur;}}parent->_left = curright;parent->_parent = cur;cur->_right = parent;if(curright)curright->_parent = parent;parent->_bf = cur->_bf = 0;
}else if (parent->_bf == -2 && cur->_bf == -1)
{//进行右旋RotateR(parent);
}

父节点为2，子节点为-1

右左双旋：对于非单侧高的情况，就不能再仅仅使用单旋来达到结果了。此处需要使用双旋来实现。

采用右左双旋：先以cur为中心进行右旋，再以parent为中心进行左旋。

注意：双选相当于将curleft变成头，将curleft的左支给parent，将cur的右支给cur；因此平衡因子调整要看curleft的平衡因子。

1）curleft是0，parent和cur都是0；

2）curleft是1，parent是-1，cur是0；

3）culeft是-1，parent是0，cur是1；

else if (parent->_bf == 2 && cur->_bf == -1)
{//右左双旋//先对cur进行右旋，再对parent进行左旋Node* curleft = cur->_left;int bf = cur->_left->_bf;RotateR(cur);RotateL(parent);if (bf == 0){parent->_bf = cur->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = 0;}else if (bf == -1){parent->_bf = 0;cur->_bf = 1;}else{perror("平衡因子错误");}curleft->_bf = 0;
}

父节点为-2，子节点为1

左右双旋：对cur进行左旋，对parent进行右旋。

else if (parent->_bf == -2 && cur->_bf == 1)
{//进行左右双旋Node* curright = cur->_right;int bf = cur->_right->_bf;RotateL(cur);RotateR(parent);if (bf == 0){parent->_bf = cur->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;}else{perror("平衡因子错误");}curright->_bf = 0;
}

插入代码汇总 

//插入
bool Insert(const pair<K, V>& kv)
{Node* newnode = new Node(kv);if (_root == nullptr)  //空树直接进行替代{_root = newnode;return true;}//非空树先找节点插入位置Node* pcur = _root;   //寻找目标位置Node* parent = nullptr;  //保留目标位置的父节点while (pcur){if (pcur->_kv.first > kv.first){parent = pcur;pcur = pcur->_left;}else if (pcur->_kv.first < kv.first){parent = pcur;pcur = pcur->_right;}else   //相等说明节点中已存在，不能再进行插入{return false;}}//跳出循环，找到目标位置//将新节点插入if (parent->_kv.first > kv.first)  //通过父节点与插入数据比较，找到新节点在左还是右{parent->_left = newnode;}else{parent->_right = newnode;}newnode->_parent = parent;//进行平衡因子的调整//进行平衡因子的调整Node* cur = newnode;while (parent)   //此处条件是parent不为空。到达根时，_root的父节点为空，停止调整{if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//检查平衡因子if (parent->_bf == 1 || parent->_bf == -1){//继续向上调整cur = parent;parent = cur->_parent;}else if (parent->_bf == 0){return true;  //插入完成，不用继续向上调整}else if (parent->_bf == 2 || parent->_bf == -2){//平衡因子错误，对树进行调整break;}else //添加额外的else保证在平衡因子不在预定范围内时即使报错。{perror("平衡因子不在范围内");}}if (parent == nullptr){return true;}if (parent->_bf == 2 && cur->_bf == 1){//进行左旋RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){//进行右旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//右左双旋//先对cur进行右旋，再对parent进行左旋Node* curleft = cur->_left;int bf = cur->_left->_bf;RotateR(cur);RotateL(parent);if (bf == 0){parent->_bf = cur->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = 0;}else if (bf == -1){parent->_bf = 0;cur->_bf = 1;}else{perror("平衡因子错误");}curleft->_bf = 0;}else if (parent->_bf == -2 && cur->_bf == 1){//进行左右双旋Node* curright = cur->_right;int bf = cur->_right->_bf;RotateL(cur);RotateR(parent);if (bf == 0){parent->_bf = cur->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;}else{perror("平衡因子错误1");}curright->_bf = 0;}return true;
}

函数检查

在写完AVL树后，需要对树进行检查，而如果通过调试窗口一次次对比效率太低了。此处可以使用函数来完成检查，AVL树的关键就是平衡因子是否正确，所以此处可以设计一个函数完成平衡因子的检测。通过得出左右子树的高度确定真实的平衡因子，再去与当前节点存储的平衡因子进行对比。

	bool Isbance(){return Isbance(_root);}int Height(Node* root){if (root == nullptr)return 0;int leHeight = Height(root->_left);int riHeight = Height(root->_right);if (leHeight > riHeight){return leHeight + 1;}else{return riHeight + 1;}}private:bool Isbance(Node* root){if (root==nullptr)return true;int leftheight = Height(root->_left);   //得到树的高度进而确定平衡因子int rightheight = Height(root->_right);if (root->_bf < -1 || root->_bf>1){perror("failed");}if (root->_bf!=rightheight-leftheight)  //检查平衡因子是否正确{cout << root->_kv.first << "  平衡因子错误" << endl;}return Isbance(root->_left) && Isbance(root->_right);}


http://www.ppmy.cn/devtools/172354.html

相关文章

k近邻算法K-Nearest Neighbors（KNN）

k近邻算法K-Nearest Neighbors（KNN）

算法核心 KNN算法的核心思想是“近朱者赤&#xff0c;近墨者黑”。对于一个待分类或预测的样本点&#xff0c;它会查找训练集中与其距离最近的K个样本点&#xff08;即“最近邻”&#xff09;。然后根据这K个最近邻的标签信息来对当前样本进行分类或回归。 在分类任务中&#…
阅读更多...
供应链系统设计-供应链中台系统设计（十九）- 库存中心

供应链系统设计-供应链中台系统设计（十九）- 库存中心

概述 我们之前的文章主要讲了业务中台的结算、通用中台的商品、风控中心等等&#xff0c;今天想和大家一起来聊聊库存。因为在整个供应链中&#xff0c;库存是一个非常重要的概念&#xff0c;因为是供应链中产品流、物流流和信息流的结果。 为什么需要有库存中心 很多同学可能…
阅读更多...
leetcode78-子集

leetcode78-子集

leetcode 78 思路 本题主要考的是回溯 result用来存储结果值&#xff0c;path表示每层遍历存放的值&#xff0c;每次递归的时候path中的结果都是结果值&#xff0c;所以每次递归的时候需要先把path中的内容存入result中&#xff0c;当startIndex nums.length时&#xff0c;…
阅读更多...
Windows系统安装Node.js和npm教程【成功】

Windows系统安装Node.js和npm教程【成功】

0.引言——Node.js和npm介绍 项目描述Node.js基于Chrome V8引擎的JavaScript运行环境&#xff0c;使JavaScript可用于服务器端开发。采用单线程、非阻塞I/O及事件驱动架构&#xff0c;适用于构建Web服务器、实时应用和命令行工具等npmNode.js的包管理器与大型软件注册表。拥有…
阅读更多...
Docker Desktop 界面功能介绍

Docker Desktop 界面功能介绍

Docker Desktop 界面功能介绍 左侧导航栏 Containers（容器）： 用于管理容器，包括查看运行中或已停止的容器，检查容器状态、日志，执行容器内命令，启动、停止、删除容器等操作。Images（镜像）： 管理本地 Docker 镜像，可查看镜像列表、从 Docker Hub 拉取新镜像、删除镜…
阅读更多...
hackmyvm-JO2024

hackmyvm-JO2024

arp-scan -l nmap -sS -v 192.168.222.202 gobuster dir -u http://192.168.222.202 -w /usr/share/wordlists/dirbuster/directory-list-2.3-medium.txt -x php -b 301,401,403,404 访问/preferences.php 看一下cookie 解密 TzoxNToiVXNlclByZWZlcmVuY2VzIjoyOntzOjg6Imxhbmd1…
阅读更多...
人生感悟8

人生感悟8

前言 今天&#xff0c;在这里跟各位聊一些看法。为什么现在的歌曲和影视剧越来越没有艺术性和内涵&#xff1f;为什么现在读书的人越来越少&#xff1f; 正文 这里我先声明一点&#xff0c;就像C或者是Java创建variable or constant一样&#xff0c;本文所述内容只限于个人观…
阅读更多...
【Java/数据结构】Map与Set（图文版）

【Java/数据结构】Map与Set（图文版）

该博客将详细介绍Java当中Map和Set是什么、Map和Set是怎么工作的、Map和Set的实现模拟以及Map和Set的使用说明。我们的重点在工作原理以及实现模拟的讲解&#xff0c;废话不多说&#xff0c;我们开始吧&#xff01; ps&#xff1a;别担心&#xff0c;其实原理很简单、朴素&…
阅读更多...
最新文章

Copyright @ 2022~2023