C++：高度平衡二叉搜索树(AVLTree) [数据结构]

目录

一、AVL树

二、AVL树的理解 

1.AVL树节点的定义

2.AVL树的插入

 2.1更新平衡因子

3.AVL树的旋转

三、AVL的检查

四、完整代码实现

---

一、AVL树

AVL树是什么？我们对 map / multimap / set / multiset 进行了简单的介绍，可以发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的。但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成 O(N)，因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

此二叉树插入元素有序，进行查找的时候效率会相当低下，甚至当接近为单支树的时候，查找效率会相当于在顺序表中的查找效率。因此俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis发明了一个解决方案：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。这也就是AVL树的由来。

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

1、它的左右子树都是AVL树

2、左右子树高度之差的绝对值不会超过1

左右子树的高度差也叫做平衡因子，在这样的树中进行搜索，时间复杂度是O(logN)。

二、AVL树的理解 

1.AVL树节点的定义

AVL 树节点是一个 三叉链结构，除了指向左右孩子的指针，还有一个指向其父亲的指针，数据域是键值对，即 pair 对象，还引入了平衡因子，用来判断是否需要进行平衡操作。 

// AVL树节点的定义（KV模型）
template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<T>* _left;   // 该节点的左孩子AVLTreeNode<T>* _right;  // 该节点的右孩子AVLTreeNode<T>* _parent; // 该节点的双亲指针pair<K, V> _kv;          // 键值对int _bf;                 // 该节点的平衡因子(balance factor) = 右子树高度-左子树高度// 构造函数AVLTreeNode(const pari<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};// AVL树的定义（KV模型）
template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:// 成员函数private:Node* _root;
}

2.AVL树的插入

AVL 树就是在二叉搜索树的基础上引入了平衡因子，因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点到 AVL 树中。
2. 新节点插入后，AVL 树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了 AVL 树的平衡（控制树的平衡（旋转操作））。

// 插入节点
bool Insert(const pair<K, V>& kv)
{// 如果树为空，则直接插入节点if (_root == nullptr){_root = new Node(kv);return true;}// 如果树不为空，找到适合插入节点的空位置Node* parent = nullptr; // 记录当前节点的父亲Node* cur = _root;      // 记录当前节点while (cur) // while循环结束，说明找到适合插入节点的空位置了{if(kv.first > cur->_kv.first) // 插入节点键值k大于当前节点{parent = cur;cur = cur->_right;}else if(kv.first < cur->_kv.first) // 插入节点键值k小于当前节点{ parent = cur;cur = cur->_left;}else // 插入节点键值k等于当前节点{return false;}}// 插入新节点cur = new Node(kv); // 申请新节点// 判断当前节点是父亲的左孩子还是右孩子if (cur->_kv.first > parent->_kv.first){parent->_right = cur;     }else{parent->_left = cur;}cur->_parent = parent;// 控制平衡// 1、更新平衡因子// ...return true;
}

 2.1更新平衡因子

(1) 插入新节点cur 插入后，AVL树的平衡性可能会遭到破坏，引入平衡因子的意义也就在于此，parent 的平衡因子一定需要调整，在插入之前，parent 的平衡因子分为三种情况：-1，0，1，分以下两种情况：

①如果插入到 新节点父亲(parent)的左侧，只需给父亲(parent)的平衡因子--(_bf--)即可。

②如果插入到 新节点父亲(parent)的右侧，只需给父亲(parent)的平衡因子++(_bf++)即可。

(2) 新节点父亲的平衡因子更新以后，又会分为 3 种情况： 

①如果更新以后，parent 的平衡因子是 0（则说明插入之前 parent 的平衡因子之前一定为 1/-1），说明父亲所在子树高度没变（因为把矮的那边给填补上了），此时满足 AVL 树的性质，插入成功，不需要继续往上更新。

②如果更新以后，parent 的平衡因子是 1/-1（则说明插入之前 parent 的平衡因子 一定为 0），说明父亲所在子树高度增加，需要继续往上更新。（最坏情况：往上一直更新到根节点）。

③如果更新以后，parent 的平衡因子是 2/-2，说明父亲所在子树出现了不平衡，需要对其进行旋转处理。

根据此理解可以写出代码来更新平衡因子：

// 插入节点
bool Insert(const pair<K, V>& kv)
{// 控制平衡// 1、更新平衡因子while (parent) // 最坏情况：更新到根节点{// 更新双亲的平衡因子if (cur == parent->_left) // 新节点插入在父亲的左边parent->_bf--;else // 新节点插入在父亲的右边parent->_bf++;// 更新后检测双亲的平衡因子if (0 == pParent->_bf){    break;}//else if (1 == parent->_bf || -1 == parent->_bf)else if (abs(parent->_bf) == 1) // 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲为根的二叉树的高度增加了一层，因此需要继续向上调整{cur = parent;parent = cur->_parent;}else if (abs(parent->_bf) == 2) // 双亲的平衡因子为正负2，违反了AVL树的平衡性，需要对以parent为根的树进行旋转处理{// 1、父节点的右边高，左边低，需要往左旋if (parent->_bf == 2 && cur->_bf == 1) {RotateL(parent); // 左单旋}// 2、父节点的左边高，右边低，需要往右旋else if ((parent->_bf == -2 && cur->_bf == -1)){RotateR(parent); // 右单旋}// 3、父节点的左边高，且父节点左孩子的右边高else if (parent->_bf == -2 && cur->_bf == 1) {RotateLR(parent); // 左右双旋}// 4、父节点的右边高，且父节点右孩子的左边高else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent); // 右左双旋}break; // 旋转完成，树已平衡，退出循环}// 除了上述3种情况，平衡因子不可能有其它的值，报错处理else{assert(false);}}return true;
}

3.AVL树的旋转

那当上面的情况已经发生，AVL树应该如何进行平衡？这就引入了旋转的概念，旋转是在遵循二叉搜索树的规则下，让左右均衡，降低整颗树的高度。

在AVL树中，当破坏了AVL树的平衡后，总共有四种会引发的旋转：

1. 新节点插入较高左子树的左侧，引发右单旋

[操作] 

1、让 subL 的右子树 subLR 成为 parent 的左子树（因为 subLR 的右子树根节点值 > 30，< 60）。
2、让 parent 成为 subL 的右子树（因为 60 > 30）。
3、让 subL 变成这个子树的根。

这一步操作前需要先判断下：parent 是根节点，还是一个普通子树

• 如果是根节点，旋转完成后，则更新 subL 为新的根节点。
• 如果是普通子树（可能是某个节点的左子树，也可能是右子树，这里作一个判断），然后更新 subL 为这个子树的根节点。

4、根据树的结构，更新 parent 和 subL 的平衡因子为 0。

在旋转过程中，更新双亲指针的指向，有以下几种情况需要考虑：

• 30 节点的右孩子可能存在，也可能不存在。（subL 的右子树 subLR 可能存在，也可能为空。当不为空时才更新 subL 右子树 subLR 的双亲指针指向）。
• 60 可能是根节点，也可能是子树。（旋转完成后，subL 的双亲节点，可能是空，也可能是 parent 原先的父节点。所以在更新 subL 的双亲指针前需要判断下）。

依次调整 subLR、parent、subL 的位置和双亲指针的指向，下面为右单旋代码：

// 右单旋
void _RotateR(Node* parent)
{  Node* subL = parent->_left; // subL : parent的左孩子Node* subLR = subL->_right; // subLR : parent左孩子的右孩子// 旋转完成之后，让subL的右子树subLR成为parent的左子树parent->_left = subLR;// 如果subLR存在，更新subLR的双亲指针，指向parentif (subLR){subLR->_parent = parent;}// 因为parent可能是棵子树，因此在更新其双亲前必须先保存parent的父节点Node* ppNode = parent->_parent;// 让parent成为subL的右子树subL->_right = parent;// 更新parent的双亲指针，指向subLparent->_parent = subL;// 如果parent是根节点，根新指向根节点的指针if (_root == parent){_root = subL;            // 更新subL为新的根subL->_parent = nullptr; // 更新subL的双亲指针，指向空}// parent不是根节点，就是一个普通子树else{// 判断parent原先是左孩子还是右孩子if (ppNode->_left == parent){ppNode->_left = subL; // parent原先的双亲节点接管subL，subL为这个子树的根}else{ppNode->_right = subL;}subL->_parent = ppNode; // 更新subL的双亲指针}// 根据调整后的结构更新部分节点的平衡因子parent->_bf = pSubL->_bf = 0;
}

2. 新节点插入在较高右子树的右侧，引发左单旋

[操作]

1、让 subR 的左子树 subRL 成为 parent 的右子树（因为 subRL 的左子树根节点值 > 30，< 60）。
2、让 parent 成为 subR 的左子树（因为 30 < 60）。
3、让 subR 变成这个子树的根。

这一步操作前需要先判断下：parent 是根节点，还是一个普通子树

• 如果是根节点，旋转完成后，则更新 subR 为新的根节点。
• 如果是普通子树（可能是某个节点的左子树，也可能是右子树，这里作一个判断），然后更新 subR 为这个子树的根节点。

4、根据树的结构，更新 parent 和 subR 的平衡因子为 0。

在旋转过程中，更新双亲指针的指向，有以下几种情况需要考虑：

• subR 的左子树 subRL 可能存在，也可能为空。（当不为空时才更新 subR 左子树 subRL 的双亲指针指向）。
• 旋转完成后，subR 的双亲节点，可能是空，也可能是 parent 原先的父节点。（所以更新 subR 的双亲指针前需要判断下）。

依次调整 subRL、parent、subR 的位置和双亲指针的指向，左单旋代码：

// 左单旋
void treeRotateLeft(Node* parent)
{Node* subR = parent->_right; // subR：父亲的右孩子Node* subRL = subR->_left; // subRL：父亲的右孩子的左孩子（大于父亲，小于subR）// 让subRL成为父亲的右子树parent->_right = subRL;// 如果subRL不为空if (subRL){subRL->_parent = parent; // 更新subRL双亲指针，指向parent}// 因为parent可能是棵子树，因此在更新其双亲前必须先保存parent的父节点Node* ppNode = parent->_parent;// 让parent成为subR的左子树subR->_left = parent; // 更新parent双亲指针的指向parent->_parent = subR;// 判断parent是不是根节点if (parent == _root){_root = subR;            // subR为新的根subR->_parent = nullptr; // subR双亲指针指向空}// 不是根节点，就是一个普通子树else{// 判断parent原先是左孩子还是右孩子if (ppNode->_left == parent){ppNode->_left = subR; // parent原先的双亲节点接管subR，subR为这个子树的根}else{ppNode->_right = subR;}subR->_parent = ppNode; // 更新subR的双亲指针}// 根据树的结构，更新parent和subR的平衡因子parent->_bf = subR->_bf = 0;
}

3. 新节点插入较高右子树的左侧，引发先右单旋再左单旋

将新的节点插入到了 parent 右孩子的左子树上，导致的不平衡的情况。这时我们需要的是先对 parent 的右孩子进行一次右旋，再对 parent 进行一次左旋。

左右双旋操作后，根据树的结构，更新平衡因子时，需要注意：

插入新节点的位置不同，经过右左双旋后，得到树的结构也会有所不同，平衡因子也会有所不同，有以下三种情况：

• 新节点插入到了 parent 右孩子的左子树的左边。
• 新节点插入到了 parent 右孩子的左子树的右边。
• 新节点就是 parent 右孩子的左孩子。

这里可以观察到一个现象，根据这个现象就很好推出旋转后的平衡因子：

节点 60 的左右子树被分走了，左子树 b 最终成了节点 30 的右子树，右子树 c 最终成了节点 90 的左子树。

// 右左双旋
void treeRotateRL(Node* parent)
{Node* subR = parent->_right; // 记录parent的右孩子Node* subRL = subR->_left;   // 记录parent的右孩子的左孩子// 旋转之前，因为插入新节点的位置不同，subRL的平衡因子可能为-1/0/1int bf = subRL->_bf; // 记录subRL的平衡因子RotateR(parent->_right); // 先对parent的右孩子进行右单旋RotateL(parent);         // 再对parent进行左单选// 旋转完成之后，根据树的结构对其他节点的平衡因子进行调整subRL->_bf = 0;if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;}else if(bf == 0){parent->_bf = 0;subR->_bf = 0;}else{assert(false);}
}

4. 新节点插入较高左子树的右侧，引发先左单旋再右单旋

将新的节点插入到了 parent 左孩子的右子树上，导致的不平衡的情况。这时我们需要的是先对 parent 的右孩子进行一次左旋，再对 parent 进行一次右旋。

void _RotateLR(PNode pParent)
{Node* subL = parent->_left; // 记录parent的左孩子Node* subLR = subL->_right; // 记录parent的左孩子的右孩子// 旋转之前，因为插入新节点的位置不同，subLR的平衡因子可能是-1/0/1int bf = subLR->_bf; // 记录subLR的平衡因子// 先对parent的左孩子进行左单旋RotateL(parent->_left);// 再对parent进行右单旋RotateR(parent);// 旋转完成之后，根据情况对其他节点的平衡因子进行调整subLR->_bf = 0;if (bf == -1){parent->_bf = 1;subL->_bf = 0;}else if (bf == 1){parent->_bf = 0;subL->_bf = -1;}	else if (bf == 0){parent->_bf = 0;subL->_bf = 0;}else{assert(false);}
}

【总结】

假如以 parent 为根的子树不平衡，即 parent 的平衡因子为 2/-2，分以下情况考虑：
1、parent 的平衡因子为 2，说明 parent 的右子树高，设 parent 的右子树的根为 subR。

• 当 subR 的平衡因子为 1 时，执行左单旋。
• 当 subR 的平衡因子为 -1 时，执行右左双旋。

2、parent 的平衡因子为 -2，说明 parent 的左子树高，设 parent 的左子树的根为 subL。

• 当 subL 的平衡因子为 -1 时，执行右单旋。
• 当 subL 的平衡因子为 1 时，执行左右双旋。

旋转完成后，原 parent 为根的子树个高度降低，已经平衡，不需要再向上更新。

三、AVL的检查

依据上面的实现可以基本实现AVL树，那如何验证AVL树是否正确？其实验证也很简单，只需要看每个节点的平衡因子是否等于对应的右子树减左子树的值即可。 

// 计算当前树的高度
int Height(Node* root)
{// 当前树为空，则高度为0if (root == nullptr)return 0;// 当前树的高度 = 左右子树中高度最大的那个加1return max(Height(root->_left), Height(root->_right)) + 1;
}// 保持树的封装 进行检查AVL树
bool IsBalance1()
{return _IsBalance(_root);
}// 进行检查AVL树
bool _IsBalance1(Node* root)
{// 当前树为空，说明是平衡的if (root == nullptr)return true;// 当前树不为空，计算左右子树的高度int leftHT = Height(root->_left);int rightHT = Height(root->_right);int diff = rightHT - leftHT;if (diff != root->_bf) // 检查当前树的平衡因子是否计算正确{cout << root->_kv.first << "平衡因子异常" << endl;return false;}// 左右子树高度相减的绝对值小于2，说明当前树是平衡的，则继续往下判断其它子树return abs(diff) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);
}

四、完整代码实现

#pragma oncetemplate<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;//三叉链AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;//平衡因子pair<K, V> _kv;//key//构造函数AVLTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){//1.先按二叉搜索树的规则插入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->_left;}else if (cur->_kv.first < kv.first){paretn = cur;cut = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//2.更新平衡因子while (parent)//有可能要更新到根节点{if (cur == parent->_right){parent->_bf ++;}else{parent->_bf--;}if (parent->_bf == 0){//没变，更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){//说明所在子树的高度变了，继续往上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//parent 的子树出现不平衡了，需要旋转处理}}return true;}//左单旋void RotateL(Node* parent){/*Node* subR = parent->_right;parent->_right = subR->_left;subR->_left = parent;*///没有处理每个节点的parent，Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;//1.原来的parent是这棵树的根，现在subR是树的根//2.parent不是整棵树的根，那么链接关系要变，subR就要顶替parent的位置if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}parent->_bf = subR->_bf = 0;}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent)PPNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}// 先右单旋再左单旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 0){// 自己就是新增的节点parent->_bf = subR->_bf = 0;}else if (bf == -1){// 在左子树进行的插入parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1){// 在右子树进行的插入subRL->_bf = 0;subR->_bf = 0;parent->_bf = -1;}else{assert(false);}}// 先进行左单旋，再进行右单旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);// 更换平衡因子if (bf == 0){subL->_bf = subLR->_bf = 0;}else if (bf == 1){// 插入在右子树subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){// 插入在左子树parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}// 用于检查树的高度int TreeHeight(Node* root){if (root == nullptr)return 0;int leftheight = TreeHeight(root->_left);int rightheight = TreeHeight(root->_right);return max(leftheight, rightheight) + 1;}// 保持树的封装 进行检查AVL树bool IsBalance(){return _IsBalance(root);}// 进行检查AVL树bool _IsBalance(Node* root){if (root == nullptr)return true;int leftheight = TreeHeight(root->_left);int rightheight = TreeHeight(root->_right);if (rightheight - leftheight != root->_bf)return false;return abs(rightheight - leftheight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);}private:Node* _root = nullptr;
};

【总结】

AVLTree 高度平衡二叉搜索树。

1.搜索树

2.要求树的左右子树的高度差不超过1，树的左子树和右子树也满足高度差不超过1，(树及所有子树都要满足前面的要求)

3.为了方便实现，引入了平衡因子（这个只是一种方式，并不是必须要这种）

4.平衡因子 = 右子树的高度 - 左子树的高度

5.高度基本可以控制在O(logN)

6.AVLTree增删查改的效率就是O(logN)

7.平衡因子到底是用来干嘛的？

8.AVLTree 的插入三步：

• 按二叉搜索树方式插入
• 更新平衡因子
• 如果更新完，没有违反规定，则插入结束，有违规，则旋转处理

9.不是所有的平衡因子都会被影响，被影响的是祖先，沿着路径往根节点更新祖先节点的平衡因子，但也不是所有的祖先都会被影响。

1.cur 是 parent 的左，parent->bf--，cur 是 parent 的右， parent->bf++,

2.更新完parent的bf 后，如果parent->bf == 0 ,说明parent的高度不变，更新结束，插入完成

解释： 说明更新前，parent 的 bf 是 -1 or 1， 现在变成0， 说明把矮的那边子树给填上了，说明高度没有变，对上层没有影响

3.更新完parent 的 bf 后， 如果parent->bf == 1 or -1 ， 说明parent 的高度变了，继续往上更新

解释： 说明跟新前，parent 的 bf 是 0 ， 现在变成了 1 or -1， 说明 一边高，对上层有影响，继续往上更新。

4.再次更新完，parent 的 bf === -2 or 2 说明parent所在的子树出现了不平衡，需要旋转处理

5.旋转处理：

• 旋转完后，还得是搜索树
• 旋转之后能把它变成平衡（左子树，右子树高度差不超过1）（左单旋，右单旋）