详解—[C++ 数据结构]—AVL树

目录

一.AVL树的概念

二、AVL树节点的定义

三、AVL树的插入

3.1插入方法

四、AVL树的旋转

1. 新节点插入较高左子树的左侧---左左：右单旋

2. 新节点插入较高右子树的右侧---右右：左单旋

3.新节点插入较高左子树的右侧---左右：先左单旋再右单旋

4.新节点插入较高右子树的左侧---右左：先右单旋再左单旋

5.AVL树的插入代码

五、AVL树的验证

六、AVL树的性能

---

一.AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

平衡因子 = 右子树高度 - 左子树高度

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 ，搜索时
间复杂度O( )。
 

二、AVL树节点的定义

AVL树每个节点都会记录他的左右孩子和父节点

并且每个节点记录一下自己的平衡因子

用模板T存储他的数据

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft; // 该节点的左孩子AVLTreeNode<T>* _pRight; // 该节点的右孩子AVLTreeNode<T>* _pParent; // 该节点的双亲T _data;int _bf; // 该节点的平衡因子
};

三、AVL树的插入

对于AVL树的插入，因为它是要结合AVL树的旋转的，所以在本文中，AVL树的插入和AVL树的旋转合起来才是完整的插入过程，所以这里我们主要讲一下插入的大体的一个过程，具体插入的细节及代码实现后面实现

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：
1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

3.1插入方法

1. 先按照二叉搜索树的规则将节点插入到AVL树中

2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了
AVL树的平衡性

新节点插入后，他的父节点的平衡因子一定需要调整，在插入之前，父节点
的平衡因子分为三种情况：-1，0, 1，分以下两种情况：

1. 如果新节点插入到父节点的左侧，只需给父节点的平衡因子-1即可
2. 如果新节点插入到父节点的右侧，只需给父节点的平衡因子+1即可

此时：父节点的平衡因子可能有三种情况：0，正负1， 正负2
1. 如果父节点的平衡因子为0，说明插入之前父节点的平衡因子为正负1，插入后被调整成0，此
时满足AVL树的性质，插入成功

2. 如果父节点的平衡因子为正负1，说明插入前父节点的平衡因子一定为0，插入后被更新成正负1，此时以父节点为根的树的高度增加，需要继续向上更新

3. 如果父节点的平衡因子为正负2，则父节点的平衡因子违反平衡树的性质，需要对其进行旋转
处理

四、AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

1. 新节点插入较高左子树的左侧---左左：右单旋

最终，根据我们图上所画的这种右单选的情况，我们可以按照上图写出右旋转的代码：

 void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;// 更新节点之间的连接关系parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* pparent = parent->_parent;parent->_parent = subL;if (!pparent){_root = subL;subL->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subL;}else if (pparent->_right == parent){pparent->_right = subL;}subL->_parent = pparent;}// 更新平衡因子parent->_bf = subL->_bf = 0;}

根据上图判断：

我们定义了父亲的左subL和父亲左的右subLR

首先根据上图第一步，把父亲左的右节点给父亲的左，如果subLR不为空，更新一下subLR的父节点

然后把parent链接在subL的右边，（记录一下父亲的父亲（pparent），一会需要subL更新父节点）  更改父亲的父节点为subL

下面就开始更新subL的父节点了

第一步判断旋转前的person是不是根节点，如果是根节点的父亲（pparent）为空，然后把根节点更新为subL，把subL的父节点置为空

如果不是根节点，判断以前pparent的左边还是右边是父亲（parent），让pparent指向父亲改为指向subL，再把subL的父节点更新为pparent

最后，更新平衡因子，把parent和subL的平衡因子置为0

2. 新节点插入较高右子树的右侧---右右：左单旋

最终，根据我们图上所画的这种右单选的情况，我们可以按照上图写出左旋转的代码：

 // 左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;// 更新节点之间的连接关系parent->_right = subRL;if (subRL)// subRL不为空才需要更新它的父亲{subRL->_parent = parent;}subR->_left = parent;Node* pparent = parent->_parent;parent->_parent = subR;if (!pparent)// parent为根时的处理{_root = subR;subR->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}// 更新平衡因子parent->_bf = subR->_bf = 0;}

对于左单旋解释，左单旋跟右单旋 两者非常类似，所以这里不再花费篇幅去讲解.

3.新节点插入较高左子树的右侧---左右：先左单旋再右单旋

将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。

// 左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int flag = subLR->_bf;// 记录subLR的平衡因子，最后要依据它来更新其他节点的平衡因子// 依次旋转RotateL(subL);RotateR(parent);// 根据subLR平衡因子的值更新不同插入情况下的平衡因子if (flag == 1)// 说明是在subLR的右子树插入的，那么subLR的左子树变为subL的右子树，subL平衡因子变为-1，subLR和parent的为0{subL->_bf == -1;}else if (flag == -1)// 说明是在subLR的左子树插入的，subLR的右子树最后会被分给parent作为左子树，parent的平衡因子变为-1，subL和subLR的平衡因子变为0{parent->_bf == 1;}}

4.新节点插入较高右子树的左侧---右左：先右单旋再左单旋
 

 void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int flag = subRL->_bf;// 依次旋转RotateR(subR);RotateL(parent);// 更新平衡因子if (flag == 1){parent->_bf == -1;}else if (flag == -1){subR->_bf == 1;}}

5.AVL树的插入代码

bool Insert(const pair<k, v>& kv){// 空树的话，就让插入的那个节点作为根if (!_root){_root = new Node(kv);return true;}// 不是空树，就按照搜索树的性质找到插入的位置和它的父亲Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (cur->_kv.first == kv.first){return false;}else if (cur->_kv.first > kv.first){cur = cur->_left;}else{cur = cur->_right;}}// 创建要插入的节点Node* newNode = new Node(kv);// 更新关系，插入节点newNode->_parent = parent;if (parent->_kv.first < newNode->_kv.first){parent->_right = newNode;}else{parent->_left = newNode;}cur = newNode;parent = cur->_parent;while (parent){// 向上更新平衡因子if (cur == parent->_left){--(parent->_bf);}else{++(parent->_bf);}// 检查是否需要调整// 0的话就平衡了// -1或1的话还要向上更新// -2或2的话需要旋转处理if (parent->_bf == 0)// 平衡因子为0，整棵树高度依然不变，只是补了原来低的那边，依然平衡{break;}else if (parent->_bf == 1 || parent->_bf == -1)// 整棵树高度增加了，但是这颗树依然平衡，再往上是否平衡不知道需要继续验证{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 右子树高if (parent->_bf == 2){if (cur->_bf == 1)// 右子树的右子树也高 -->  左单旋{RotateL(parent);}else if (cur->_bf == -1)// 右子树的左子树也高  -->  右左双旋{RotateRL(parent);}}else if (parent->_bf == -2)// 左子树高{if (cur->_bf == -1)// 左子树的左子树也高  -->  右单旋{RotateR(parent);}else if (cur->_bf == 1)// 左子树的右子树也高  -->  左右双旋{RotateLR(parent);}}break;}}return true;}

五、AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
1. 验证其为二叉搜索树
    如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树
       每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
       节点的平衡因子是否计算正确

  int Height(Node* root){if (root == nullptr)return 0;int RightHeight = Height(root->_left);int LeftHeight = Height(root->_right);return RightHeight > LeftHeight ? RightHeight + 1 : LeftHeight + 1;}bool _IsBalance(Node* root){if (root == nullptr)return true;//空的话应该返回true，因为不影响平衡int LeftHeight = Height(root->_left);//迭代计算高度int RightHeight = Height(root->_right);if (RightHeight - LeftHeight != root->_bf)//仅仅判断高度是不够的，有可能平衡因子还是错了，所以要对每个平衡因子做检查{cout << "平衡因子现在是:" << root->_bf << endl;cout << "平衡因子应该是：" << (RightHeight - LeftHeight) << endl;return false;//平衡因子错了直接返回}return RightHeight - LeftHeight < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);}

六、AVL树的性能

       AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合