AVL概念
当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在
O(log2n),搜索时间复杂度O(log2n)
AVL操作
插入
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
| 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->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else { return false; } }
cur = new Node(kv); if (parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent;
while (parent) { if (parent->_left == cur) { parent->_bf--; } else { parent->_bf++; }
if (parent->_bf == 0) { break; } else if (abs(parent->_bf) == 1) { parent = parent->_parent; cur = cur->_parent; } else if (abs(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(false); }
break; } else { assert(false); } } return true; }
|
判断平衡
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| bool is_balance() { return _is_balance(_root); }
int get_height(Node *root) { if (root == nullptr) return 0;
int left = get_height(root->_left); int right = get_height(root->_right);
return max(left, right) + 1; }
bool _is_balance(Node *root) { if (root == nullptr) { return true; }
int left = get_height(root->_left); int right = get_height(root->_right);
int diff = right-left; if (diff != root->_bf) { cout << root->_kv.first << " 平衡因子异常" << endl; return false; } return abs(diff) < 2 && _is_balance(root->_left) && _is_balance(root->_right); }
|
平衡因子更新
![](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202212131300912.png)
更新平衡因子的规则
- 新增在右,parent->bf++,新增在左,parent->bf–
- 更新后,parent->bf == 1 or -1, 说明parent插入前的平衡因子是0,说明左右子树高度相等,插入后有一边高,parent高度变了,需要继续往上更新
- 更新后,parent->bf == 0,说明parent插入前的平衡因子是1 or -1, 说明左右子树一边高一边低,插入后两边一样高,插入填上了矮的那边,parent所在子树高度不变,不需要往上更新
- 更新后,parent->bf == 2 or -2 ,说明parent插入前的平衡因子是1 or -1,已经平衡临界值,插入后变成2 or -2,打破平衡,parent所在子树需要旋转处理
- 更新后,parent->bf >2 or < -2,不可能,如果存在,则说明插入前就不是AVL树,需要去检查之前操作的问题
旋转的场景
旋转的价值和意义:
左单旋
情景分析
![](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202212131542366.png)
![](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202212131543737.png)
具体进行左旋的时候也要分两种情况
![](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202212131544284.png)
调整完成之后,parent的平衡因子变为0,subR变为新的根,同时平衡因子也变为0
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| void RotateL(Node* parent) { Node *subR = parent->_right; Node *subRL = subR->_left;
parent->_right = subRL; if(subRL) { subRL->_parent = parent; }
Node *ppNode = parent->_parent; subR->_left = parent;
if(parent==_root) { _root = subR; subR->_parent = nullptr; } else { if(ppNode->_left=parent) { ppNode->_left = subR; } else { ppNode->_right = subR; }
subR->_parent = ppNode; } }
|
右单旋
情景分析‘
![](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202212131547708.png)
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| void RotateR(Node* parent) { Node* subL = parent->_left; Node *subLR = subL->_right;
Node *ppNode = parent->_parent;
parent->_left = subLR; if(subLR) { subLR->_parent = parent; }
subL->_right = parent; parent->_parent = subL;
if(_root==parent) { _root = subL; subL->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = subL; } else { ppNode->_right = subL; }
subL->_parent = ppNode; }
subL->_bf = 0; parent->_bf = 0; }
|
左右旋
情景分析
三种情况:
1、在b新增,那么60节点的平衡因子是-1
2、在c新增,那么60节点的平衡因子是1
![](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202212131548304.png)
3、subLR就是新增
![](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202212131609243.png)
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| void RotateLR(Node *parent) { Node *subL = parent->_left; Node *subLR = subL->_right; int bf = subLR->_bf;
RotateL(parent->_left); RotateR(parent);
subLR->_bf = 0;
if (bf == -1) { parent->_bf = 1; subL->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subL->_bf = 0; } else if (bf == 1) { parent->_bf = 0; subL->_bf = -1; } else { assert(false); } }
|
右左旋
情景分析
1、新增在b,那么subRL平衡因子变成-1,先对subR进行右旋,然后再对parent进行左旋,调整完成之后,subRL也就是70节点变成了根,平衡因子为0,parent的平衡因子为0,subR就是90的平衡因子变成1.
![](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202212132009280.png)
2、新增在c,那么subRL平衡因子变成1,先对subR进行右旋,然后再对parent进行左旋,调整完成之后,subRL也就是70节点变成了根,平衡因子为0,parent的平衡因子为-1,subR就是90的平衡因子变成0。
![](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202212131937234.png)
3、新增就是subRL,subRL平衡因子为0,调整完成后都是0
![](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202212131937964.png)
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| void RotateRL(Node *parent) { Node *subR = parent->_right; Node *subRL = subR->_left; int bf = subRL->_bf;
RotateR(subR); RotateL(parent);
subRL->_bf = 0;
if (bf == -1) { subR->_bf = 1; parent->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subR->_bf = 0; } else if (bf == 1) { parent->_bf = -1; subR->_bf = 0; } else { assert(false); } }
|