C++AVL树（二）详解

AVL树

旋转

单旋

单旋是纯粹的一边高
单旋平衡因子是同号

右单旋

a,b,c自身不能发生旋转
并且也不能不向上继续更新（不能停止更新）

插入之前是h+2，插入后进行旋转后是h+2，没有对pParent它的子树的高度产生影响，不用继续向上更新

// 链接孩子和父亲
// 右单旋,旋转点是parent
void Rotate(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;// b可能为空树if (suLR != nullptr)subLR->_parent = parent;// 记录parent的parentpParent = parent->_parent;subL->_right = parent;parent->_parent = subL;// 1. 10是这棵树的总根if (parent == _root){subL = _root;subL->_parent = nullptr;}else{// 2. 10是这棵树的局部根// 就有父亲的父亲节点// pParent左可能是parent,右也可能是parentif (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}// 更新平衡因子subL->_bf = 0;parent->_bf = 0;}

左单旋

左单旋和右单旋类似

// 左单旋,旋转点是parent
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;// b不是空树if (subRL)subRL->_parent = parent;// 记录父亲节点的父亲节点Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;// 1. 10是这棵树的总根if (_root == parent){_root = subR;subR->_parent = nullptr;}else{// 2. 10是这棵树的局部根if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}subR->_parent = pParent;}subR->_bf = 0;parent->_bf = 0;
}

双旋

双旋平衡因子会异号
双旋是进行两次单旋

对于5来说右边高，对于10来说左边高，需要进行双旋
下面是进行的单旋解决不了问题

对于5来说右边高，对于10来说左边高，需要进行双旋
进行单旋解决不了问题，会变成下面的样子

左右双旋

h == 0

h == 1

右左双旋

右左双旋和左右双旋类似，这里就不画了

平衡因子的更新

左右双旋

双旋和单旋的平衡因子更新方式不同，双旋按照单旋的方式更新后5,10，8都是0，不符合逻辑

左右双旋中h0和h1具体场景分析，下面我们将a/b/c子树抽象为高度h的AVL
子树进行分析，另外我们需要把b子树的细节进一步展开为8和左子树高度为h-1的e和f子树，因为
我们要对b的父亲5为旋转点进行左单旋，左单旋需要动b树中的左子树。b子树中新增结点的位置
不同，平衡因子更新的细节也不同，通过观察8的平衡因子不同，这里我们要分三个场景讨论。

• 场景1：h >= 1时，新增结点插入在e子树，e子树高度从h-1并为h并不断更新8->5->10平衡因子，
  引发旋转，其中8的平衡因子为-1，旋转后8和5平衡因子为0，10平衡因子为1。
• 场景2：h >= 1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新8->5->10平衡因子，引
  发旋转，其中8的平衡因子为1，旋转后8和10平衡因子为0，5平衡因子为-1。
• 场景3：h == 0时，a/b/c都是空树，b自己就是一个新增结点，不断更新5->10平衡因子，引发旋转，其中8的平衡因子为0，旋转后8和10和5平衡因子均为0。

8的平衡因子会影响其它的平衡因子：

• 插入到8的左边，8的平衡因子为-1
• 插入到8的右边，8的平衡因子为1
• 8本身就是要插入的节点，8的平衡因子为0

// 左右双旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 提前存平衡因子int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (subLR->_bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (subLR->_bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (subLR->_bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

右左双旋

跟左右双旋类似，下面我们将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的细节进一步展开为12和左子树高度为h-1的e和f子树，因为我们要对b的父亲15为旋转点进行右单旋，右单旋需要动b树中的右子树。b子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察12的平衡因子不同，这里我们要分三个场景讨论。

• 场景1：h >= 1时，新增结点插入在e子树，e子树高度从h-1变为h并不断更新12->15->10平衡因子，引发旋转，其中12的平衡因子为-1，旋转后10和12平衡因子为0，15平衡因子为1。
• 场景2：h >= 1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新12->15->10平衡因子，引发旋转，其中12的平衡因子为1，旋转后15和12平衡因子为0，10平衡因子为-1。
• 场景3：h == 0时，a/b/c都是空树，b自己就是一个新增结点，不断更新15->10平衡因子，引发旋转，其中12的平衡因子为0，旋转后10和12和15平衡因子均为0。

3种情况：

• 插入到e那边
• 插入到f那边
• b本身就是插入的点

// 右左双旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;// 提前存放平衡因子int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else{assert(false);}
}

判断是不是AVL树

用高度差的绝对值是否 <= 1来检查

// 算树的高度,左右子树高的那个加1
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;
}// 判断是不是AVL树
bool _IsBalanceTree(Node* root)
{// 空树也是AVL树if (root == nullptr)return true;// pRoot的子树的平衡因子,左右子树的高度差int _leftheight = _Height(root->_left);int _rightheight = _Height(root->_right);int diff = _rightheight - _leftheight;// 高度差超过2或者pRoot的平衡因子不等于计算出的平衡因子就不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}else if (diff != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot节点的左树和右树都是AVL树,那么就是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

时间复杂度分析

插入：logN,寻找插入的位置，会找到叶子的位置
旋转：常数次
调整：假设最坏情况调整到根logN，平衡因子为-1/1,要继续调整
时间复杂度：logN

全部的代码

#pragma once
#include<iostream>
#include<assert.h>using namespace std;template<class K, class V>
struct AVLTreeNode
{// 需要parent指针pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;// 平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0)// 刚插入的节点平衡因子都是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{// 不冗余return false;}}// 链接父节点cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因子// 控制平衡while (parent){if (parent->_left == cur)parent->_bf--;else // if (parent->_right == cur)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){// 旋转if (parent->_bf == -2 && cur->_bf == -1){// 右旋,左高右低RotateR(parent);}else if(parent->_bf == 2&&cur->_bf == 1){// 左旋,右高左低RotateL(parent);}else if(parent->_bf == -2&&cur->_bf == 1){// 左右双旋,右高左高RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){// 右左双旋,左高右高RotateRL(parent);}else{assert(false);}break;}else{// 逻辑错误,之前就不是AVL树assert(false);}}return true;}// 右单旋,旋转点是parentvoid RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;// b可能为空树if (subLR != nullptr)subLR->_parent = parent;// 记录parent的parentNode* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;// 1. 10是这棵树的总根if (parent == _root){_root = subL;subL->_parent = nullptr;}else{// 2. 10是这棵树的局部根// pParent左可能是parent,右也可能是parentif (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}// 更新平衡因子subL->_bf = 0;parent->_bf = 0;}// 左单旋,旋转点是parentvoid RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;// b不是空树if (subRL)subRL->_parent = parent;// 记录父亲节点的父亲节点Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;// 1. 10是这棵树的总根if (_root == parent){_root = subR;subR->_parent = nullptr;}else{// 2. 10是这棵树的局部根if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}subR->_parent = pParent;}subR->_bf = 0;parent->_bf = 0;}// 左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;// 提前存平衡因子int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (subLR->_bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (subLR->_bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (subLR->_bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}// 右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;// 提前存放平衡因子int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else{assert(false);}}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}// 大小int Size(){return _Size(_root);}// 判断是不是AVL树bool IsBalanceTree(){return _IsBalanceTree(_root);}// 算树的高度int Height(){_Height(_root);}// 中序void InOrder(){_InOrder(_root);cout << endl;}
private:// 算树的高度,左右子树高的那个加1int _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;}// 算树的节点个数 int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}// 判断是不是AVL树bool _IsBalanceTree(Node* root){// 空树也是AVL树if (root == nullptr)return true;// pRoot的子树的平衡因子,左右子树的高度差int _leftheight = _Height(root->_left);int _rightheight = _Height(root->_right);int diff = _rightheight - _leftheight;// 高度差超过2或者pRoot的平衡因子不等于计算出的平衡因子就不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}else if (diff != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot节点的左树和右树都是AVL树,那么就是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root = nullptr;
};#include"AVLTree.h"void TestAVLTree1()
{AVLTree<int, int> t;// 常规的测试⽤例int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试⽤例//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.insert({ e, e });}t.InOrder();cout << t.IsBalanceTree() << endl;
}int main()
{TestAVLTree1();return 0;
}