【STL】AVLTree模拟实现

1 前言

二叉搜索树的不足：如果出现极端情况，效率会变得很低。

AVL：二叉平衡搜索树
平衡因子：右子树的高度 - 左子树的高度 平衡因子绝对值不超过1(-1, 0, 1)

1.平衡因子为什么不是0？而是 -1， 0 ，1？？

做不到，两个节点的时候不能相等，四个节点也做不到

AVL树的效率：
增删查改：高度次 O(log N)
满二叉树：2^h - 1 = N
AVL树：2^h - x = N
x的范围：[1, 2^(h - 1) - 1]

2 AVL树的插入

2.1 平衡因子不继续向上更新的情况

插入的原则：
新增在左：parent的平衡因子–
新增在右：parent的平衡因子++

从这里可以看出，当平衡因子的值为 -1 或者 1 的时候，并不会停止向上更新。
只有当平衡因子更新为0的时候，才不会继续往上更新了。

2.2 平衡因子变为2或者-2，发生旋转

当平衡因子的值更新为 -2或者2的时候，就代表这棵树不平衡了，就需要进行旋转。这时候更新也停止了（因为要进行旋转了）

2.什么情况要继续往上更新？（更新结束的条件）
更新后的parent平衡因子==0，说明parent所在的子树的高度不变，不会再影响祖先，不用再继续往上更新
更新后的parent平衡因子 ==1 或者 -1，说明parent所在的子树的高度发生改变，会影响祖先，要继续往上更新
更新后的parent平衡因子 ==2 或者 -2，说明parent所在的子树的高度发生改变且不平衡，想办法调整平衡（对parent所在子树进行旋转，让他平衡）
更新到根节点 --> 更新结束

2.2.1 左单旋

发生左单旋的情况：(具体图，某一种情况)

发生左单旋的抽象图(有很多种情况)：

什么情况会发生左单旋？

在右边高的情况下往右边插入。

转化成代码就是：在插入之后，parent->_bf = 2 && cur->_bf = 1.这里parent->_bf = 2说明是右边高，如果parent->_bf = -2，说明是左边高。

总结：
cur->left 比 parent大，所以，cur->left做parent的右没有问题
cur->left比cur小，所以，cur->left做cur的左没有问题

核心操作：
parent->right = cur->left
cur->left = parent;

2.2.2 右单旋

发生右单旋的情况（具体图）：

发生右单旋的抽象图（有很多种情况）：

旋转：
右边高 --> 往左边旋转
左边高 --> 往右边旋转

旋转的时候要注意的问题：

1. 保持他是搜索树
2. 变成平衡树且降低这个子树的高度

2.2.3 左右双旋

左右双旋的情况：
当父节点左边高并且当前节点的右边高时，就会发生左右双旋。

双旋平衡因子的更新：
区分的关键，看插入节点的父节点的平衡因子
平衡因子的三种情况：h == 0, h > 0。h > 0又分为两种情况：插入节点是父节点的左子树或者插入节点是父节点的右子树

2.2.4 右左双旋

右左双旋：
当父节点的右边高并且当前节点的左边高时，就会发生右左双旋


如何分清是单旋还是双旋？
单旋：单纯的一边高，左边高或者右边高
双旋：有折现的产生。

3 代码

AVLTree.h

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;template <class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;//new一个AVLTreeNode节点的时候就会调用这个构造函数// 如果传入参数，就是kvAVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template <class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){//搜索的插入//...控制平衡//新增在左边，父节点的平衡因子-- | 新增在右边，父节点的平衡因子++  新增的节点会影响到它的祖先if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{assert("插入相同的节点");}}//走到这里，找到了要插入的位置 --> 将cur插入进去cur = new Node(kv);if (cur->_kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;//因为是三叉链，所以cur的_parent指针还要指回去cur->_parent = parent;//走到这里，插入完成了。需要检查平衡因子，判断是否平衡，不平衡要进行旋转while (parent){//插入的位置是左孩子，bf--;插入的位置是右孩子，bf++if (cur == parent->_left)parent->_bf--;elseparent->_bf++;//接下来要判断根据不同的平衡因子进行不同的更新的情况if (parent->_bf == 0){break;  //如果是0， 就不用更新了}else if (parent->_bf == -1 || parent->_bf == 1)   //如果插入之后parent的平衡因子等于-1或者1，说明还要向上调整{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//如果平衡因子走到这里，说明要发生旋转了：左旋，右旋，双旋。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){//父节点右边高，当前节点左边高  --> 右左双旋RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//父节点左边高，当前节点右边高  --> 左右双旋RotateLR(parent);}else{assert("平衡因子出错");}break;}else{assert("平衡因子出错");}}return true;}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;//1.把curleft给parent的right  --> parent的_right指向curleftparent->_right = curleft;//判断curleft是否为空，如果不为空，就curleft的父节点指回去if (curleft){curleft->_parent = parent;}//2.parent的right给cur的left  --> cur的_left指向parentcur->_left = parent;//3.判断parent是不是当前的根节点,如果是，cur的_parent就为空。如果不是，cur的_parent还要指向ppnodeNode* ppnode = parent->_parent;//4.parent还要往回指，因为是三叉链parent->_parent = cur;if (parent == _root)  //如果是根节点{_root = cur;cur->_parent = nullptr;}else{//如果不是根节点，就要判断是ppnode的左孩子还是右孩子if (ppnode->_left == parent)ppnode->_left = cur;elseppnode->_right = cur;//往回指cur->_parent = ppnode;}//更新平衡因子parent->_bf = cur->_bf = 0;}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;//1.让parent的左指向cur的右parent->_left = curright;if (curright){//第一次往回指curright->_parent = parent;}//找到parent的父节点Node* ppnode = parent->_parent;//2.cur的右指向parentcur->_right = parent;//第二次往回指parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{parent->_parent = cur;if (ppnode->_left == parent)ppnode->_left = cur;elseppnode->_right = cur;//第三次往回指cur->_parent = ppnode;}//更新平衡因子cur->_bf = parent->_bf = 0;}//左右双旋void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);//根据不同的情况修改平衡因子if (bf == 0){cur->_bf = 0;parent->_bf = 0;curright->_bf = 0;}else if (bf == 1)   //说明左边低，右边高{parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}else{assert("RotateLR false");}}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;   //提前保存下来RotateR(cur);RotateL(parent);if (bf == 0){cur->_bf = 0;parent->_bf = 0;curleft->_bf = 0;}else if (bf == 1)  //说明插入的位置是curleft的右边{parent->_bf = -1;cur->_bf = 0;curleft->_bf = 0;}else if (bf == -1)  //插入的位置是curleft的左边{parent->_bf = 0;cur->_bf = 1;curleft->_bf = 0;}else{assert("RotateRL false");}}//bool Erase(const pair<K, V>& key)//{//}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;int leftHight = Height(root->_left);int rightHight = Height(root->_right);if (rightHight - leftHight != root->_bf){cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;return false;}return abs(rightHight - leftHight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}void Inorder(){_Inorder(_root);}private:void _Inorder(Node* cur){if (cur == nullptr)return;_Inorder(cur->_left);cout << cur->_kv.first << " : " << cur->_kv.second << " : " << cur->_bf << endl;_Inorder(cur->_right);}
private:Node* _root = nullptr;
};

Test_AVLTree.cpp

#include "AVLTree.h"void testAVL1()
{int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.IsBalance();t.Inorder();
}int main()
{testAVL1();return 0;
}