简介
AVL树是一棵平衡二叉搜索树.
对于它的每一棵子树：左子树 和 右子树 的高度，相差不超过1.
因此它的查找效率 比 普通二叉搜索树 要高，效率稳定在log(N).
二叉搜索树的左旋和右旋
在AVL树进行插入或删除时，都有可能让 某一棵子树的 左右子树高度差距 超过1.
此时需要对这棵子树进行旋转处理，旋转方式有以下两种：
个人记忆方法
如果是左旋，记作有一个人在左边向下拉绳子,以cur为支点
当right到达最高点时把cur顶下去，同时right的左边由于惯性接到cur的右边去.
具体实现
--成员属性
平衡因子：用来记录当前结点 左右子树 的高度差.
平衡因子 = 右子树的高度 - 左子树的高度( 也可以反过来 )
//AVL树的结点声明
//当前结点的平衡因子 = 当前结点的右子树高度 - 左子树高度 //用来记录当前结点的左右子树高度差
template
struct AVLTreeNode
{
AVLTreeNode(const pair& kv = std::pair())
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)//新插入的结点，没有左右子树，平衡因子为0;
{}
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
std::pair _kv;
int _bf;//平衡因子balance factor
};
template
class AVLTree
{
typedef AVLTreeNode Node;
private:
Node* _root = nullptr;
}
--插入
插入后祖先结点平衡因子调整
( 1 )新插入的结点，只会影响它的祖先结点的平衡因子：
因为结点的平衡因子只跟结点的左右子树差有关.
只有新插入结点的祖先结点的子树高度可能发生变化，其它结点的子树高度不变.
( 2 ) 调整祖先结点平衡因子
核心 —— 左子树高度增加,--平衡因子；右子树高度增加,++平衡因子
插入前当前结点的平衡因子是0，插入后平衡因子变为-1/1，
说明以当前结点为根的子树高度增加，继续向上调整.
插入前，当前结点的左子树和右子树高度相同.
插入后，平衡因子变为1/-1，它的左右子树有一边高，一边低;
以当前结点为根的子树高度也发生了变化，需要继续沿着祖先路径继续向上调整平衡因子.
插入前当前结点的平衡因子是-1/1，插入后平衡因子变为0，停止向上调整
插入之前，左右子树一边高，一边低;
插入之后，左右子树高度相同.
以当前结点为根的子树高度没有变化，其祖先结点的左右子树高度差也不会有任何变化.
插入前当前结点的平衡因子是-1/1，插入后平衡因子变为2/-2，停止向上调整，同时处理该子树
插入之后，以当前结点为根的子树，左右子树高度差距为2，不满足AVL树的性质，需要调整.
template
bool AVLTree::insert(const std::pair& kv)
{
//直接插入，得到插入结点的指针
Node* insertNode = _ordinaryInsert(kv);
//如果插入结点是根，插入完成
//如果插入结点是nullptr,插入失败，树中已经有相同的key值
if (insertNode == _root) return true;
if (insertNode == nullptr) return false;
//接着更新插入结点的祖先结点的平衡因子
Node* child = insertNode;
Node* parent = child->_parent;//parent才是需要更新bf的结点，child用来判断parent->_bf如何更新
while (parent != nullptr)//parent == nullptr,说明祖先结点的平衡因子已经全部更新完成
{
//先更新平衡因子
//child用来判断parent->_bf如何更新
if (parent->_left == child)
--parent->_bf;
else
++parent->_bf;
//若更新后，平衡因子为0，说明parent所在的子树高度不变，不需要继续向上更新
//若parent->_bf变为1/-1，parent所在子树的高度变了，要继续向上更新
//parent->_bf == 2/-2,平衡被打破，parent所在子树要旋转处理
if (parent->_bf == 0)
break;
else if (parent->_bf == 1 || parent->_bf == -1)
{
child = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//对parent这棵子树进行旋转处理+平衡因子调整
_insertRotateAdjustBF(parent);
break;
}
else
assert(false);
}
return true;
}
//常规插入，返回新插入的结点指针
template
AVLTreeNode* AVLTree::_ordinaryInsert(const std::pair& kv)
{
//要插入的新结点
Node* newNode = new Node(kv);
//插入前是空树
if (_root == nullptr)
{
_root = newNode;
return _root;
}
//找到插入位置 和 插入位置的父亲结点，插入并链接
Node* cur = _root;//记录插入的位置
Node* parent = nullptr;//记录插入位置的父亲结点
while (cur != nullptr)
{
//插入的值 > 当前结点的值（用key去比较） —— 去右树找插入位置
//插入的值 (cur->_kv).first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first _kv).first)
{
parent = cur;
cur = cur->_left;
}
else
{
delete newNode;
//已经有相等的key，插入失败
return nullptr;
}
}
插入后发生子树的旋转
发生平衡因子调整时，cur是最先被调整到-2/2的结点.
因此cur下面结点的平衡因子都是0/1/-1
插入前模型的分析过程：
( 1 ) 插入后，cur->_bf被调整为2/-2
说明插入前，cur->_bf = 1/-1：cur的左右子树一边高一边低.
这里以左边高为例子（插入前树的情况）：
( 2 ) 左子树较高，最后一定是插入在a树中，让a的高度增高.
先把cur的左子树展开：（插入前树的情况）
( 3 ) cur->_bf是插入后，最开始被调整到-2的结点.
在left子树插入新结点后，会沿着新结点的祖先路径往上调整平衡因子.
只有当插入前left->_bf = 0时，
才能在插入后left->_bf 转成-1/1，cur->_bf才能调整到-2.
（插入结点沿祖先结点路径调整平衡因子的情况，前面已经分析过）
( 4 ) 插入前，cur左子树较高，cur右子树较低；
往左子树插入会导致cur->_bf = -2的抽象图如下
a、b、c都是一棵高度为h的AVL子树
插入前，cur的右子树较高，cur的左子树较低
往右子树插入会导致cur->_bf = 2的抽象图 也用类似方法分析出来.
插入结点后的抽象图情况分析：
( 1 )cur的左子树较高，插入在cur左子树的左子树，导致cur的左子树过高
处理方式：直接对cur这棵子树进行右旋
判断条件：cur->_bf == -2 && cur->_left->_bf == -1
右旋之后，这棵子树的高度和插入之前一样，所以不需要继续向上调整.
template
AVLTreeNode* AVLTree::_rightRotate(AVLTreeNode* cur)//返回旋转后子树新的根
{
Node* parent = cur->_parent;
Node* left = cur->_left;
Node* leftRight = cur->_left->_right;
//按图从上往下调整（注意parent和leftRight为空的情况）
if (parent != nullptr)
{
if (parent->_left == cur)
parent->_left = left;
else
parent->_right = left;
}
left->_parent = parent;
left->_right = cur;
cur->_parent = left;
cur->_left = leftRight;
if(leftRight != nullptr)
leftRight->_parent = cur;
//如果cur == _root，要更新_root
if (cur == _root)
_root = left;
//返回这棵子树新的根
return left;
}
template
void AVLTree::_insertRightRotateAdjustBF(Node* newRoot)
{
newRoot->_bf = 0;
newRoot->_right->_bf = 0;
}
( 2 ) cur右子树较高，插入在cur右子树的右子树中，导致cur的右子树过高
处理方式：直接对cur这棵子树进行左旋
判断条件：cur->_bf == 2 && cur->_right->_bf == 1
左旋之后，这棵子树的高度和插入之前一样，所以不需要继续向上调整.
template
AVLTreeNode* AVLTree::_leftRotate(AVLTreeNode* cur)//返回旋转后子树新的根
{
Node* parent = cur->_parent;
Node* right = cur->_right;
Node* rightLeft = cur->_right->_left;
//按图从上往下调整（注意parent和rightLeft为空的情况）
if (parent != nullptr)
{
if (parent->_left == cur)
parent->_left = right;
else
parent->_right = right;
}
right->_parent = parent;
right->_left = cur;
cur->_parent = right;
cur->_right = rightLeft;
if (rightLeft != nullptr)
rightLeft->_parent = cur;
//如果cur == _root，要更新_root
if (cur == _root)
_root = right;
//返回这棵子树新的根
return right;
}
template
void AVLTree::_insertLeftRotateAdjustBF(Node* newRoot)
{
newRoot->_bf = 0;
newRoot->_left->_bf = 0;
}
( 3 ) cur的左子树较高，插入在cur的左子树的右子树，导致cur的左子树过高
判断条件：cur->_bf == -2&& cur->_left->_bf == 1
仅仅右旋，会让cur的右子树过高.
分析：
A 可以先考虑将它转化成：left子树左子树高，右子树低的情况 —— 左旋left子树
B 这样就成了前面可以直接右旋的情况 —— 右旋cur子树
为了形象看左旋left子树的过程，我们把left的右子树继续展开.
C 插入后，旋转的具体过程在下图.
新插入的结点可能插入在b子树上，也可能在c子树上，但旋转过程是不变的
但最后平衡因子的调整会有多种情况：(保存LR原来的平衡因子，判断最后平衡因子调整的方案.)
1 若在b树插入导致b树增高，旋转完成后，b树高度为h：【LR->_bf = -1】
left的平衡因子为0，cur的平衡因子为1;
2 若在c树插入结点导致c树增高，旋转完成后，c树的高度为h: 【LR->_bf = 1】
left的平衡因子为-1，cur的平衡因子为0.
3 若h = 0 ,LR就是新增的结点. 【LR->_bf = 0】
左右双旋cur子树后，该子树的高度和插入之前一样，不需要继续向上调整
template
AVLTreeNode* AVLTree::_leftRightRotate(AVLTreeNode* cur)
{
_leftRotate(cur->_left);
Node* newRoot = _rightRotate(cur);
return newRoot;
}
template
void AVLTree::_insertLeftRightRotateAdjustBF(Node* newRoot)
{
//旋转完成后，用来判断平衡因子调整情况的leftRight，成为了子树的新根
int flag = newRoot->_bf;
//flag = 0:leftRight就是新插入的结点
//flag = 1:说明在c子树插入结点
//flag = -1:说明在b子树插入结点
if (flag == 0)
newRoot->_bf = newRoot->_left->_bf = newRoot->_right->_bf = 0;
else if (flag == 1)
{
newRoot->_bf = 0;
newRoot->_left->_bf = -1;
newRoot->_right->_bf = 0;
}
else if (flag == -1)
{
newRoot->_bf = 0;
newRoot->_left->_bf = 0;
newRoot->_right->_bf = 1;
}
else
assert(false);
}
( 4 ) cur的右子树高，插入在cur右子树的左子树.
判断条件：cur->_bf == 2 && cur->_right->_bf == -1
和情况3类似，通过右旋，转换成可以直接左旋处理的情况.
在b/c树插入结点导致左右子树高度差改变，最终都会调整为下图模型.
保存RL原来的平衡因子，用于判断最后平衡因子的调整
A 若在b树插入，cur的平衡因子为0，right的平衡因子为1.
B 若在c树插入，cur的平衡因子为-1，right的平衡因子为0.
C 若插入前h = 0，那么RL就是新插入的结点，最终cur、right、RL的平衡因子都为0.
右左双旋cur子树后，该子树的高度和插入之前一样，不需要继续向上调整
template
AVLTreeNode* AVLTree::_rightLeftRotate(AVLTreeNode* cur)
{
//先对cur的右子树右旋
//再对cur整体子树左旋
//得到子树的新根
_rightRotate(cur->_right);
Node* newRoot = _leftRotate(cur);
return newRoot;
}
template
void AVLTree::_insertRightLeftRotateAdjustBF(Node* newRoot)
{
//旋转完成后，用来判断平衡因子调整情况的rightLeft，成为了子树的根
int flag = newRoot->_bf;
//调整平衡因子
//flag = 0:说明rightLeft就是新插入的结点
//flag = 1:说明在c子树插入结点发生高度差改变
//flag = -1,说明在b子树插入结点发生高度差改变
if (flag == 0)
newRoot->_bf = newRoot->_left->_bf = newRoot->_right->_bf = 0;
else if (flag == 1)
{
newRoot->_bf = 0;
newRoot->_left->_bf = -1;
newRoot->_right->_bf = 0;
}
else if (flag == -1)
{
newRoot->_bf = 0;
newRoot->_left->_bf = 0;
newRoot->_right->_bf = 1;
}
else
assert(false);
}
对旋转情况进行分类的代码
//对cur这棵子树(cur->_bf == 2)进行旋转处理
template
void AVLTree::_insertRotateAdjustBF(AVLTreeNode* cur)
{
//4种旋转情况需要画图，这里简单叙述
//1 插入前cur的右子树较高，新插入的结点在cur右子树的右子树中 ——直接左旋
//2 插入前cur的左子树较高，新插入的结点在cur左子树的左子树中 ——直接右旋
//3 插入前cur的右子树较高，新插入的结点在cur右子树的左子树中 ——先对cur->right子树右旋，再对cur子树左旋
//4 插入前cur的左子树较高，新插入的结点在cur左子树的右子树中 —— 先对cur->left子树左旋，再对cur子树右旋
if ( cur->_bf == 2 && cur->_right->_bf == 1)
{
Node* newRoot = _leftRotate(cur);
_insertLeftRotateAdjustBF(newRoot);
}
else if ( cur->_bf == -2&& cur->_left->_bf == -1 )
{
Node* newRoot = _rightRotate(cur);
_insertRightRotateAdjustBF(newRoot);
}
else if (cur->_bf == 2 && cur->_right->_bf == -1)
{
Node* newRoot = _rightLeftRotate(cur);
_insertRightLeftRotateAdjustBF(newRoot);
}
else if (cur->_bf == -2 && cur->_left->_bf == 1)
{
Node* newRoot = _leftRightRotate(cur);
_insertLeftRightRotateAdjustBF(newRoot);
}
else
//有错误方便调试
assert(false);
}
--删除
普通二叉搜索树的删除，
删除结点只有1/0孩子，让删除结点的父亲结点指向删除结点的孩子即可.
删除结点有2个孩子，替换法删除，可以用删除结点左子树的最大结点替换删除...
(具体看我上一篇博客)二叉搜索树 - 掘金 (juejin.cn)
总之真正被删除的结点最多只有一个孩子.
//常规删除，返回被删除结点的父亲结点
template
AVLTreeNode* AVLTree::_ordinaryErase(const K& key)
{
//记录删除结点位置 和 删除结点的父亲结点位置
Node* del = _root;
Node* delParent = nullptr;
while (del != nullptr)
{
if (key > del->_kv.first)
{
delParent = del;
del = del->_right;
}
else if (key _kv.first)
{
delParent = del;
del = del->_left;
}
else//成功找到要删除的结点
{
//1 删除结点左子树为空
//2 删除结点右子树为空
//3 删除结点有两个孩子，替换法删除，左孩子的最大结点可以替换删除
if (del->_left == nullptr)
{
if (delParent == nullptr)
_root = del->_right;
else if (delParent->_left == del)
delParent->_left = del->_right;
else if (delParent->_right == del)
delParent->_right = del->_right;
delete del;
return delParent;
}
else if (del->_right == nullptr)
{
if (delParent == nullptr)
_root = del->_left;
else if (delParent->_left == del)
delParent->_left = del->_left;
else if (delParent->_right == del)
delParent->_right = del->_left;
delete del;
return delParent;
}
else//待删除结点有两个孩子，替换法删除
{
//左子树的最大结点替换删除
Node* max = del->_left;
Node* maxParent = del;;
while (max->_right)
{
maxParent = max;
max = max->_right;
}
del->_kv = max->_kv;
//删除max
if (maxParent->_left == max)
maxParent->_left = max->_left;
else
maxParent->_right = max->_left;
delete max;
return maxParent;
}
}
}
return nullptr;
}
删除后祖先结点平衡因子调整
( 1 ) 真正被删除的结点最多有一个孩子.
( 2 ) 结点被删除，会影响删除结点的祖先结点的平衡因子.
( 3 ) 调整祖先结点平衡因子
核心 —— 左子树高度减少,++平衡因子；右子树高度减少,--平衡因子
删除前，以left为根的子树，left->_bf = -1/1;
删除后，left左子树高度减小/右子树高度减小,导致left->_bf = 0.继续沿着祖先结点向上调整.
分析：删除前，left的左右子树，一边高一边低；
删除后导致某一棵子树高度降低，left左右子树一样高.
所以删除后以left为根的子树高度降低，需要继续向上调整(直到根).
删除前，以cur为根的子树，cur->_bf = 0;
删除后，左子树高度降低/右子树高度降低，导致cur->_bf = 1/-1.停止向上调整
分析：删除前，cur的左右子树一样高；
删除后导致其中一棵子树降低，但以cur为根的树，高度不变.
删除前，cur->_bf = 1/-1;
删除后，cur->_bf = 2/-2;该子树需要旋转，停止向上调整
template
bool AVLTree::erase(const K& key)
{
//cur是被删除结点的父亲结点
Node* cur = _ordinaryErase(key);
Node* child = nullptr;
if (cur == nullptr)
{
//在删除前，可以事先保存_root的key，判断下面情况，这里直接返回true
//1 被删除的结点是_root，不需要调整
//2 没有找到删除的结点
return true;
}
//由于可能用替换法删除，刚开始 真正被删除结点的key值不确定
int leftTreeHeight = _height(cur->_left);
int rightTreeHeight = _height(cur->_right);
cur->_bf = rightTreeHeight - leftTreeHeight;
//删除结点 会影响它的祖先结点的平衡因子
while (cur != nullptr)
{
if (child != nullptr)
{
if (cur->_left == child)
++cur->_bf;
else
--cur->_bf;
}
if (cur->_bf == 0)
{
child = cur;
cur = cur->_parent;
}
else if (cur->_bf == 1 || cur->_bf == -1)
break;
else if (cur->_bf == 2 || cur->_bf == -2)
{
_eraseRotateAdjustBF(cur);//这里后面会有所修改
break;
}
else
assert(false);
}
return true;
}
代码解析
1 为什么求 删除结点的父亲结点 左右子树高度？不能直接和给出的key比较吗？
( 1 ) 删除有两个孩子的结点，要用替换法删除，
所以真正被删除的结点，是 本该删除结点的 左子树的最大结点 / 右子树的最小结点.
( 2 ) 一开始，要用 被删除的结点的key 和 delParent的key 进行比较，
但我们不确定真正被删除结点的key值（可能用替换法删除）.
2 求 删除结点的父亲结点 左右子树高度的时间复杂度会高吗？
( 1 ) 删除前，这是AVL树，每棵子树的左右子树高度差不超过1;
( 2 ) 删除前，真正被删除的结点，最多只有一个孩子 —— 以该结点为根的子树高度最多为2.
( 3 ) 删除前，以delParent结点为根的高度，它的一棵子树最高为2，那么另一棵子树最高为3;
所以求 删除结点的父亲结点 左右子树高度的时间复杂度可以视为O(1).
3 求一棵二叉树高度代码，用队列实现层序遍历
template
size_t AVLTree::_height(Node* root)
{
if (root == nullptr) return 0;
//用队列层序遍历，每一层遍历完 ++ret
int ret = 0;
//当前层还需要遍历的结点数目
int curLevelLeftNum = 1;
//记录遍历到的结点
Node* cur = nullptr;
queue q;
q.push(root);
while (!q.empty())
{
cur = q.front();
q.pop();
//遍历到的结点，它的孩子不为空就入队列
if (cur->_left != nullptr)
q.push(cur->_left);
if (cur->_right != nullptr)
q.push(cur->_right);
//当前层待遍历的结点数目-1
curLevelLeftNum--;
if (curLevelLeftNum == 0)//当前层遍历完成
{
++ret;
curLevelLeftNum = q.size();
}
}
return ret;
}
删除后发生子树的旋转
发生平衡因子调整时，cur是最先被调整到-2/2的结点.
因此cur下面结点的平衡因子都是0/1/-1.
另外，删除前子树高度 和 旋转处理后的子树高度，有些情况下会有不同.
【与插入结点导致的旋转不同】
意味着完成旋转后，可能仍需要继续沿着祖先路径向上调整平衡因子.
删除前抽象图的分析过程
和插入前的模型分析过程类似，可以跳过.
以左子树较高，右子树较低为例.
( 1 ) 删除后，cur->_bf = -2;
说明删除前，cur的左右子树高度相差1.
( 2 ) 删除后，cur->_bf = -2，
说明最后一定要对cur子树进行右移，先展开左子树.
A left->_bf = 0 —— ab子树的高度都是h
B left->_bf = -1 —— a子树高度为h,b子树高度为h-1
C left->_bf = 1 —— a子树高度为h-1,b子树高度为h
( 3 ) cur右子树较高，左子树较低的情况也类似.
加起来一共6种.
删除结点后的旋转情况分析
根据left->_bf划分情况：
当left->_bf = -1时，直接右旋cur树.
注意右旋后的子树，它的高度比删除前要低，仍然要继续调整祖先结点的平衡因子.
当left->_bf = 0时，直接右旋cur树.
右旋后，子树的高度和删除前的高度相同，不需要继续调整.
当left->_bf = 1时，先左旋left子树，再右旋cur树.
LR的平衡因子会影响最终要调整的平衡因子,但旋转过程不变.
最终这棵子树的高度为 (h+1)，比删除前的高度要低，需要继续调整祖先结点的平衡因子
cur->_bf = 2的情况分析和上面类似，下面的代码是对应旋转处理,子树的平衡因子调整.
template
void AVLTree::_eraseLeftRotateAdjustBF(Node* newRoot)
{
if (newRoot->_bf == 1)
{
newRoot->_bf = 0;
newRoot->_left->_bf = 0;
}
else if (newRoot->_bf == 0)
{
newRoot->_bf = -1;
newRoot->_left->_bf = 1;
}
else
assert(false);
}
template
void AVLTree::_eraseRightRotateAdjustBF(Node* newRoot)
{
if (newRoot->_bf == -1)
{
newRoot->_bf = 0;
newRoot->_right->_bf = 0;
}
else if (newRoot->_bf == 0)
{
newRoot->_bf = 1;
newRoot->_right->_bf = -1;
}
else
assert(false);
}
template
void AVLTree::_eraseRightLeftRotateAdjustBF(Node* newRoot)
{
if (newRoot->_bf == 0)
{
newRoot->_bf = 0;
newRoot->_left->_bf = 0;
newRoot->_right->_bf = 0;
}
else if(newRoot->_bf == 1)
{
newRoot->_bf = 0;
newRoot->_left->_bf = -1;
newRoot->_right->_bf = 0;
}
else if(newRoot->_bf == -1)
{
newRoot->_bf = 0;
newRoot->_left->_bf = 0;
newRoot->_right->_bf = 1;
}
}
template
void AVLTree::_eraseLeftRightRotateAdjustBF(Node* newRoot)
{
if (newRoot->_bf == 0)
newRoot->_bf = newRoot->_left->_bf = newRoot->_right->_bf = 0;
else if (newRoot->_bf == 1)
{
newRoot->_bf = 0;
newRoot->_left->_bf = -1;
newRoot->_right->_bf = 0;
}
else if (newRoot->_bf == -1)
{
newRoot->_bf = 0;
newRoot->_left->_bf = 0;
newRoot->_right->_bf = 1;
}
}
对删除导致的旋转进行分类代码
template
AVLTreeNode* AVLTree::_eraseRotateAdjustBF(Node* cur)
{
//返回nullptr，说明旋转后 当前子树的高度不变，不需要继续调整祖先结点
//否则把子树的新根返回
if ( cur->_bf == 2 && cur->_right->_bf == 1)
{
Node* newRoot = _leftRotate(cur);
_eraseLeftRotateAdjustBF(newRoot);
return newRoot;
}
else if (cur->_bf == 2 && cur->_right->_bf == 0)
{
Node* newRoot = _leftRotate(cur);
_eraseLeftRotateAdjustBF(newRoot);
return nullptr;
}
else if (cur->_bf == -2 && cur->_left->_bf == -1)
{
Node* newRoot = _rightRotate(cur);
_eraseRightRotateAdjustBF(newRoot);
return newRoot;
}
else if (cur->_bf == -2 && cur->_left->_bf == 0)
{
Node* newRoot = _rightRotate(cur);
_eraseRightRotateAdjustBF(newRoot);
return nullptr;
}
else if (cur->_bf == 2 && cur->_right->_bf == -1)
{
Node* newRoot = _rightLeftRotate(cur);
_eraseRightLeftRotateAdjustBF(newRoot);
return newRoot;
}
else if (cur->_bf == -2 && cur->_left->_bf == 1)
{
Node* newRoot = _leftRightRotate(cur);
_eraseLeftRightRotateAdjustBF(newRoot);
return newRoot;
}
else
assert(false);
}
之前的删除要接收旋转处理完成的返回值，判断是否需要继续调整祖先结点.
template
bool AVLTree::erase(const K& key)
{
//cur是被删除结点的父亲结点
Node* cur = _ordinaryErase(key);
//child是高度被降低的子树
Node* child = nullptr;
if (cur == nullptr)
{
//在删除前，可以事先保存_root的key，判断下面情况，这里直接返回true
//1 被删除的结点是_root，不需要调整
//2 没有找到删除的结点
return true;
}
//由于可能使用替换法删除，真正被删除结点key值不能确定
int leftTreeHeight = _height(cur->_left);
int rightTreeHeight = _height(cur->_right);
cur->_bf = rightTreeHeight - leftTreeHeight;
//删除结点 会影响它的祖先结点的平衡因子
while (cur != nullptr)
{
if (child != nullptr)
{
if (cur->_left == child)
++cur->_bf;
else
--cur->_bf;
}
if (cur->_bf == 0)
{
child = cur;
cur = cur->_parent;
}
else if (cur->_bf == 1 || cur->_bf == -1)
break;
else if (cur->_bf == 2 || cur->_bf == -2)
{
//如果flag为空，旋转的新树高度不变，不需要继续调整
Node* flag = _eraseRotateAdjustBF(cur);
if (flag == nullptr)
break;
//否则沿着新根的祖先结点继续调整
child = flag;
cur = flag->_parent;
}
else
assert(false);
}
return true;
}
--判断一棵树是否为AVL树
可以配合这个接口验证之前写的插入删除是否正确.
思路：遍历每个结点(前序遍历或层序遍历都行)，
以当前结点为根的左右子树高度差必须 -2.
template
bool AVLTree::isAVLTree()
{
if (_root == nullptr) return true;
//遍历所有结点，只要所有结点都满足 其左右子树高度差不超过1 就是AVLTree
//前序遍历
stack st;
Node* cur = _root;
while (cur != nullptr || !st.empty())
{
while (cur)
{
st.push(cur);
if (isAVLTreeChild(cur) == false)
return false;
cur = cur->_left;
}
Node* top = st.top();
st.pop();
cur = top->_right;
}
return true;
}
//判断AVLTree中一棵子树的左右高度差是否合法
template
bool AVLTree::isAVLTreeChild(Node* root)
{
if (root == nullptr) return true;
int leftHeight = _height(root->_left);
int rightHeight = _height(root->_right);
int flag = rightHeight - leftHeight;
assert(flag == root->_bf);
if (flag == root->_bf && abs(flag) < 2)
return true;
else
return false;
}
--用随机值测试
void testAVLTree1()
{
srand(time(nullptr));
AVLTree tree;
int n = 1000;
//插入10000个随机值
for (int i = 0; i < n; ++i)
{
int x = rand() % n;
tree.insert(make_pair(x, i));
//每次插入完成后仍然是AVL树
if (tree.isAVLTree())
cout
