目录
- 底层结构
- avl树的概念
- 节点定义
- 插入
- 旋转
- 验证
- 删除
- 全
- 性能
1. 底层结构
前面对map/multimap/set/multiset进行了简单的介绍，在其文档介绍中发现，这几个容器有几个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现
2. avl树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskill和E.M.Landis在1962年，发明了一种解决上述问题的方法：当向二叉搜索树插入新节点后，如果能保证每个节点的左右子树高度只差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度
一颗AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差（简称平衡因子）的绝对值不超过1（-1/0/1）
如果一棵二叉树是高度平衡的，它就是AVL树。如果它有n个节点，其陶都可保持在
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)，搜索时间复杂度O(
l
o
g
2
n
log_2n
log2n)
3. 节点定义
节点保存左右孩子和模板数据，因为要调整高度，所以保存双亲和平衡因子
template <class K, class V>
struct TreeNode
{
struct TreeNode<K, V>* _parent;
struct TreeNode<K, V>* _left;
struct TreeNode<K, V>* _right;
std::pair<K, V> _kv;
int _bf;
TreeNode(std::pair<K, V> kv)
:_parent(nullptr), _left(nullptr), _right(nullptr)
, _kv(kv), _bf(0)
{}
};
4. 插入
平衡因子：右子树的高度-左子树的高度
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树叶可以看成是二叉搜索树，那么AVL树的插入过程可以分为两步：
1.按照二叉搜索树的方式插入新节点
2.调整节点的平衡因子
插入节点后，双亲结点的平衡因子一定要更新，如果插入在右侧，平衡因子++，左侧–
此时，平衡因子会出现三种情况：0,正负1，正负2
1.如果双亲结点平衡因子是0，说明插入前平衡因子是正负1，满足avl树性质，不需要向上更新，对祖先节点的平衡因子无影响
2.如果双亲结点的平衡因子是正负1，说明插入前的平衡因子一定是0，插入后变为了正负1，树的高度增加，需要持续向上更新
3.如果双亲结点的平衡因子是正负2，则违反了平衡树的性质，需要进行旋转处理
bool insert(const std::pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new node(kv);
return true;
}
node* parent = nullptr;
node* cur = _root;
while (cur)
{
parent = cur;
if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
cur = cur->_right;
}
else
{
return false;
}
}
//创建节点
cur = new node(kv);
cur->_parent = parent;
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//更新平衡因子
while (parent)
{
if (parent->_left == cur)
{
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)
{
//需要旋转调整
}
else
{
assert(false);
}
}
}
5. 旋转
如果在一棵原本平衡的avl树插入一个新节点，可能会造成不平衡，此时必须调整树的结构，使平衡化，根绝插入位置的不同，avl树的旋转分为四种：
1.新节点插入较高右子树的右侧–右右：左单旋
上面的是一个抽象图，a、b、c都是高度为h的avl树，如果在c的位置插入一个节点。根节点左边的高度是h，右边是h+2，平衡因子就变为2，失衡状态。
将a,b,c列举出高度为0,1,2三种情况
当h=2时，子树的情况有x,y,z三种情况，a，b是三种任一种，而z只能是x形状，如果是其他两种就不会更新到上面去，自己就会失衡。x节点的插入位置有4个，所以当高度为2时，就有36种情况
无论哪种情况，调整只涉及30,60,b，也就是parent，subR，subRL。只有这几个的高度需要更新，所有的例子里根节点平衡因子都是2，右子树的高度都是1，所以可以将这种情况归类。
当parent平衡因子为2，subR的平衡因子为1的情况，就要左单旋
将30作为parent，60叫subR，b叫subRL，调整只涉及了这三个节点
调整的方法将30拿下来，60提上去作为局部的根，b作为30的右子树
总结下来就是：
1.b变为30的右边
2.30变为60的右边
3.60称为树新的根
调整后30的左右都是h，平衡因子0，a和c没有更改不变。60左右都是h+1，也是0
全
具体分为三步
1.先更改结构，60的左子树改为30,30的右子树改为b
2.父节点的更改
如果b不为空，b的双亲改为30
如果调整前30是根节点，那么就没有双亲结点，所以要分两种情况
先记录30的双亲结点，30的双亲改为60，因为这个树可能作为一颗树的局部
a.如果30是根节点，调整后60作为根节点
b.如果不是根节点，判断调整前30是左节点还是右节点，分情况改为60
将60的的双亲结点改为保存的根节点，如果是根节点就是空
最后更新平衡因子，只有30和60的子树情况有更改，调整后都是0
void RotateLeft(node* parent)
{
node* sub = parent->_right;
node* subl = sub->_left;
sub->_left = parent;
parent->_right = subl;
//父节点修改
node* Pparent = parent->_parent;
parent->_parent = sub;
//有子节点改变指向
if (subl)
{
subl->_parent = parent;
}
if (parent == _root)
{
_root = sub;
}
else
{
//原parent在父节点的左右
if (Pparent->_left == parent)
{
Pparent->_left = sub;
}
else
{
Pparent->_right = sub;
}
}
sub->_parent = Pparent;
//更新平衡因子
parent->_bf = sub->_bf = 0;
}
2.新节点插入较高左子树的左侧—左左：右单旋
上图在插入前是平衡的，新节点插入到30的左子树，30左子树增加了一层，导致60为根的二叉树不平衡，要让60平衡，只能让60左子树的高度减少一层，右子树增加一层。即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况情况需要考虑
1.30节点的右孩子可能存在，也可能不存在
2.60可能是根节点，也可能是子树
如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树
右单旋和左单旋类似，只需要变一下方向
1.b变为60的左边
2.60变为30的右边
3.30称为树新的根
全
void RotateRight(node* parent)
{
node* sub = parent->_left;
node* subr = sub->_right;
sub->_right = parent;
parent->_left = subr;
if (subr)
{
subr->_parent = parent;
}
node* Pparent = parent->_parent;
parent->_parent = sub;
if (parent == _root)
{
_root = sub;
}
else
{
if (Pparent->_left == parent)
{
Pparent->_left = sub;
}
else
{
Pparent->_right = sub;
}
}
sub->_parent = Pparent;
sub->_bf = parent->_bf = 0;
}
旋转的目的
1.从不平衡，变成平衡子树
2.旋转本质降低了高度
高度和插入前一样，所以不会对上层造成影响，不需要往上更新平衡因子
3.新节点插入较高右子树的左侧–右左：先右单旋再左单旋
a和d是高度为h的avl树（h>=0），将b树拆为一个节点和两个高度为h-1的avl树（h>=1）
下面是高度的几个情况：
当h=2时，a和d是x，y，z中一种，60的高度是1，插入位置有4个，合计就是334=36种情况
h=3时，a和d就是高度为3的avl树，每一个可能有C44+C43+C42+C41=1+4+6+4=15种可能，b和c是高度为2的avl树，只有x的情况插入会引起旋转，当b是x时，插入位置有4个，c是x,y,z任一种，c是x时也同样，这两个是互斥，所以可能性总共是342=24种，总共就是151524=5400种
h=3时就有5400种可能，高度再往上情况更复杂，从这些情况中找出一种共性，不像前面的只有一边高一边插入，这里插入较高子树的左侧，单独的旋转无法解决情况，但可以先对根节点的右节点右旋，变为第一种右右的情况，再对根节点左旋
下面是具体旋转结果和平衡因子的改变：
这种情况根节点高度差都是2,右节点高度-1
大致可以分为两种，h=0和h=1
h=0时60就是新增的节点，调整完后三个节点的高度差都是0
h=1时，可以在b或c的位置插入，旋转后根节点的高度差是0，如果b插入，30就是0，不然就是-1。如果是c插入，高度就是0，不然就是1
a，b，c，d的内部没有动过，不需要更新。根节点是0，不会对上面的部分影响，也不需要向上更新
30叫parent，90是sub，60是subl
全
void RotateRL(node* parent)
{
node* sub = parent->_right;
node* subl = sub->_left;
//提前记录bf,旋转后会更改
int bf = subl->_bf;
RotateRight(parent->_right);
RotateLeft(parent);
//根据bf判断h=0 h=1的两种情况
if (bf == 0)
{
//subl自己就是新增节点
subl->_bf = sub->_bf = parent->_bf = 0;
}
else if (bf == -1)
{
//subl左侧插入
subl->_bf = parent->_bf = 0;
sub->_bf = 1;
}
else if (bf == 1)
{
//subl右侧插入
subl->_bf = sub->_bf = 0;
parent->_bf = -1;
}
else
{
assert(false);
}
}
新节点插入较高左子树的右侧–左右：先左单旋再右单旋
将双旋变为单旋后再旋转，即：先对30左单旋，然后再对90右单旋，旋转完成后再考虑平衡因子的更新
void RotateLR(node* parent)
{
node* sub = parent->_left;
node* subl = sub->_right;
//提前记录bf,旋转后会更改
int bf = subl->_bf;
RotateLeft(parent->_left);
RotateRight(parent);
if (bf == 0)
{
subl->_bf = sub->_bf = parent->_bf = 0;
}
else if (bf == -1)
{
//subl左侧插入
subl->_bf = sub->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
//subl右侧插入
subl->_bf = parent->_bf = 0;
sub->_bf = -1;
}
else
{
assert(false);
}
}
总结
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
1.pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
- 当pSubR的平衡因子为1时，执行左单旋
- 当pSubR的平衡因子为-1时，执行右左双旋
2.pParent的平衡因子-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
- 当pSubL的平衡因子为-1时，执行右单旋
- 当pSubL的平衡因子1时，执行左右双旋
旋转完成后，原pParent为根的子树高度降低，已经平衡，不需要向上更新
6. 验证
avl树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证avl树，可以分两步：
1.验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2.验证其为平衡树
每个节点子树高度差的绝对值不超过1（注意节点中如果没有平衡因子）
节点的平衡因子是否计算正确
树的高度
int TreeHeight()
{
return _TreeHeight(_root);
}
int _TreeHeight(node* node)
{
if (node == nullptr)
{
return 0;
}
int lhight = _TreeHeight(node->_left);
int rhight = _TreeHeight(node->_right);
return lhight > rhight ? lhight + 1 : rhight + 1;
检测平衡
孩子节点的差值是否等于自己的平衡因子
bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(node* node)
{
if (node == nullptr)
{
return true;
}
int leftlheight = _TreeHeight(node->_left);
int rightheight = _TreeHeight(node->_right);
if (rightheight - leftlheight != node->_bf)
{
std::cout << node->_kv.first << "平衡因子异常" << std::endl;
return false;
}
return abs(leftlheight - rightheight) < 2
&& _IsBalance(node->_left)
&& _IsBalance(node->_right);
}
计算节点个数
int size()
{
return _size(_root);
}
int _size(node* node)
{
if (node == nullptr)
{
return 0;
}
return _size(node->_left) + _size(node->_right) + 1;
}
验证用例
根据下面的数据次序，动手画avl树的创建过程，验证是否有漏洞
常规场景：{16, 3, 7, 11, 9, 26, 18, 14, 15}
特殊场景：{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}
7. 删除
因为avl树也是二叉搜索树，可按照搜索树的方式伤处节点，然后再更新平衡因子，最差的情况需要更新到根节点的位置
具体可以参考《算法导论》或《数据结构-用面向对象办法与C++描述》殷人昆版
分为三步：
第一步：找到删除位置
第二步：删除节点
第三步：更新平衡因子，调整高度
寻找删除位置
和插入的方法一样
node* del = _root;
while (del)
{
if (key < del->_kv.first)
{
del = del->_left;
}
else if (key > del->_kv.first)
{
del = del->_right;
}
else
{}
}
else里就是找到了删除的元素
删除节点
三种情况：
1.如果被删节点del有两个子女
找前驱或者后继替换删除节点，就会变成最多只有一个子女的情况
这里找del的直接前驱，将两个节点的val交换，然后要删除的节点变为前驱节点
2.如果被删节点最多只有一个子女q
可以把del的父节点par原来指向del的指针改指到q，如果节点del没有子女，par指向的指针就设置为NULL。然后将原来以节点par为根的子树的高度减1，并沿par通向根的路径反向追踪高度的这一变化对路径上各节点的影响
调整高度
平衡因子往上追踪的过程，如果q是par的左子女，则par的平衡因子增加1，否则减少1，平衡因子值会有下面三种情况，分别处理：
par的平衡因子改为-1或1
par的平衡因子原来是0，当子树的结点删除后，更新变为了1或-1。由于par为根的子树的高度没有变化
上图删除任一del节点后这个子树的高度没有变化，就不会对上面产生影响，从par到根节点的路径都不需要调整，结束本次删除的平衡过程
par的平衡因子变为0
par的平衡因子原不为0，较高的子树被缩短，par的平衡因子变为0.此时虽然以par为根的子树平衡，但其高度减1了，需要继续考察节点par的父节点的平衡状态
par的平衡因子变为2或-2
以par为根的子树不为0，一边高一边低，且较矮的子树又被缩短，这时par节点就会不平衡，需要旋转来调整。令par较高的子树的根为q，根据q的平衡因子表现的子树状态有下面三种平衡化操作：
- 如果q的平衡因子为0，执行一个单旋转恢复结点的平衡，如图是左单旋的例子，旋转后q为根的子树高度没有发生变化，可以直接结束平衡的过程，但平衡因子需要手动更改
- 如果q的平衡因子和par的平衡因子同号，只需要一个单旋转就能恢复平衡，旋转后par和q的平衡因子都变为0。经过旋转后树的高度降低了1，所以需要继续沿par的路径考察节点q的父亲的平衡状态
- 如果par和q的平衡因子反号，就需要双旋来恢复平衡，先围绕q旋转，再围绕par旋转，新的树的par和q的平衡因子都是0，其他节点相应处理。经过平衡后树的高度减少1，还需要考察父节点，向上平衡，下图是先右旋，再左旋
实现
下面是删除算法，用到了几个变量，其中del是删除节点，parent是del的父节点，q记录删除节点后parent指向的新节点。empty用来判断del节点左右孩子都为空的情况，deldir保存上面情况调整的方向，d记录失衡时parent的方向
旋转后传的是值，所以q和parent的结点位置需要更新
node* parent = del->_parent;
node* q;
bool empty = false;
int deldir; //两个孩子都为空时,判断方向
int d;/*左重-1 右重1*/
bool erase(const K& key)
{
if (_root == nullptr)
{
return false;
}
node* del = _root;
while (del)
{
if (key < del->_kv.first)
{
del = del->_left;
}
else if (key > del->_kv.first)
{
del = del->_right;
}
else
{
//找到 删除
node* parent = del->_parent;
node* q;
bool empty = false;
int deldir; //两个孩子都为空时,判断方向
int d;/*左重-1 右重1*/
//被删节点两个孩子
if (del->_left != nullptr && del->_right != nullptr)
{
//找前驱替换
node* leftmax = del->_left;
//node* q = del;
while (leftmax->_right)
{
leftmax = leftmax->_right;
}
parent = leftmax->_parent;
//node* leftnode = leftmax->_left;
//交换值
std::swap(del->_kv, leftmax->_kv);
//从leftmax的父节点开始更新
del = leftmax;
}
//右节点不为空
if (del->_left != nullptr)
{
q = del->_left;
}
else
{
if (del->_left == nullptr && del->_right == nullptr)
{
empty = true;
}
q = del->_right;
}
//判断是根节点
if (del == _root)
{
_root = q;
}
else
{
//判断左右,连接
if (parent->_left == del)
{
deldir = -1;
parent->_left = q;
}
else
{
deldir = 1;
parent->_right = q;
}
if (q != nullptr)
{
q->_parent = parent;
}
//重新平衡
while (parent)
{
//左右都为空
if (empty)
{
if (deldir == -1)
{
parent->_bf++;
}
else
{
parent->_bf--;
}
empty = false;
}
else
{
if (parent->_right == q)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
}
//|bf|=1;不影响高度,退出
if (parent->_bf == 1 || parent->_bf == -1)
{
break;
}
//|bf|==2,需要旋转,判断子树的bf
if (parent->_bf != 0)
{
//右边重,看右子树的bf
if (parent->_bf < 0)
{
d = -1;
q = parent->_left;
}
else
{
d = 1;
q = parent->_right;
}
//单旋转调整,更改bf,不影响高度,退出
if (q->_bf == 0)
{
if (d == -1)
{
RotateRight(parent);
parent->_bf = -1;
q->_bf = 1;
}
else
{
RotateLeft(parent);
parent->_bf = 1;
q->_bf = -1;
}
break;
}
//q和parent同号
if (q->_bf == d)
{
//p = -2 d = -1
if (d == -1)
{
RotateRight(parent);
}
// p = 2 d = 1
else
{
RotateLeft(parent);
}
}
else
{
//旋转后重新连接
// p = 2 d = -1
if (q->_bf == -1)
{
RotateRL(parent);
}
else
{
RotateLR(parent);
}
}
//旋转后更新节点
q = parent;
parent = parent->_parent;
}
//继续向上查找
q = parent;
parent = parent->_parent;
}
}
delete del;
return true;
}
return false;
}
}
8. 全
#pragma once
#include <iostream>
#include <assert.h>
#include <queue>
#include <stack>
template <class K, class V>
struct TreeNode
{
struct TreeNode<K, V>* _parent;
struct TreeNode<K, V>* _left;
struct TreeNode<K, V>* _right;
std::pair<K, V> _kv;
int _bf;
TreeNode(std::pair<K, V> kv)
:_parent(nullptr), _left(nullptr), _right(nullptr)
, _kv(kv), _bf(0)
{}
};
template <class K, class V>
class AVLTree
{
public:
typedef struct TreeNode<K, V> node;
bool insert(const std::pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new node(kv);
return true;
}
node* parent = nullptr;
node* cur = _root;
while (cur)
{
parent = cur;
if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
cur = cur->_right;
}
else
{
return false;
}
}
//创建节点
cur = new node(kv);
cur->_parent = parent;
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//更新平衡因子
while (parent)
{
if (parent->_left == cur)
{
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)
{
//旋转
//分四种旋转情况
//右边重，左单旋
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateLeft(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateRight(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
break;
}
else
{
assert(false);
}
}
}
void RotateLeft(node* parent)
{
node* sub = parent->_right;
node* subl = sub->_left;
sub->_left = parent;
parent->_right = subl;
//父节点修改
node* Pparent = parent->_parent;
parent->_parent = sub;
//有子节点改变指向
if (subl)
{
subl->_parent = parent;
}
if (parent == _root)
{
_root = sub;
}
else
{
//原parent在父节点的左右
if (Pparent->_left == parent)
{
Pparent->_left = sub;
}
else
{
Pparent->_right = sub;
}
}
sub->_parent = Pparent;
//更新平衡因子
parent->_bf = sub->_bf = 0;
}
void RotateRight(node* parent)
{
node* sub = parent->_left;
node* subr = sub->_right;
sub->_right = parent;
parent->_left = subr;
if (subr)
{
subr->_parent = parent;
}
node* Pparent = parent->_parent;
parent->_parent = sub;
if (parent == _root)
{
_root = sub;
}
else
{
if (Pparent->_left == parent)
{
Pparent->_left = sub;
}
else
{
Pparent->_right = sub;
}
}
sub->_parent = Pparent;
sub->_bf = parent->_bf = 0;
}
void RotateRL(node* parent)
{
node* sub = parent->_right;
node* subl = sub->_left;
//提前记录bf,旋转后会更改
int bf = subl->_bf;
RotateRight(parent->_right);
RotateLeft(parent);
//根据bf判断h=0 h=1的两种情况
if (bf == 0)
{
//subl自己就是新增节点
subl->_bf = sub->_bf = parent->_bf = 0;
}
else if (bf == -1)
{
//subl左侧插入
subl->_bf = parent->_bf = 0;
sub->_bf = 1;
}
else if (bf == 1)
{
//subl右侧插入
subl->_bf = sub->_bf = 0;
parent->_bf = -1;
}
else
{
assert(false);
}
}
void RotateLR(node* parent)
{
node* sub = parent->_left;
node* subl = sub->_right;
//提前记录bf,旋转后会更改
int bf = subl->_bf;
RotateLeft(parent->_left);
RotateRight(parent);
if (bf == 0)
{
subl->_bf = sub->_bf = parent->_bf = 0;
}
else if (bf == -1)
{
//subl左侧插入
subl->_bf = sub->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
//subl右侧插入
subl->_bf = parent->_bf = 0;
sub->_bf = -1;
}
else
{
assert(false);
}
}
void inorder()
{
_inorder(_root);
std::cout << std::endl;
}
void _inorder(node* root)
{
if (root == nullptr)
{
return;
}
_inorder(root->_left);
std::cout << root->_kv.first << " ";
_inorder(root->_right);
}
int size()
{
return _size(_root);
}
int _size(node* node)
{
if (node == nullptr)
{
return 0;
}
return _size(node->_left) + _size(node->_right) + 1;
}
int TreeHeight()
{
return _TreeHeight(_root);
}
int _TreeHeight(node* node)
{
if (node == nullptr)
{
return 0;
}
int lhight = _TreeHeight(node->_left);
int rhight = _TreeHeight(node->_right);
return lhight > rhight ? lhight + 1 : rhight + 1;
}
bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(node* node)
{
if (node == nullptr)
{
return true;
}
int leftlheight = _TreeHeight(node->_left);
int rightheight = _TreeHeight(node->_right);
if (rightheight - leftlheight != node->_bf)
{
std::cout << node->_kv.first << "平衡因子异常" << std::endl;
return false;
}
return abs(leftlheight - rightheight) < 2
&& _IsBalance(node->_left)
&& _IsBalance(node->_right);
}
void layer()
{
if (_root == nullptr)
{
return;
}
std::queue<node*> q;
q.push(_root);
int lay = 1;
while (!q.empty())
{
std::cout << "第" << lay << "层: ";
int num = q.size();
while (num--)
{
node* cur = q.front();
q.pop();
std::cout << cur->_kv.first << " 因子:" << cur->_bf << " ";
if (cur->_left != nullptr)
{
q.push(cur->_left);
}
if (cur->_right != nullptr)
{
q.push(cur->_right);
}
}
lay++;
std::cout << std::endl;
}
std::cout << std::endl;
}
bool erase(const K& key)
{
if (_root == nullptr)
{
return false;
}
node* del = _root;
while (del)
{
if (key < del->_kv.first)
{
del = del->_left;
}
else if (key > del->_kv.first)
{
del = del->_right;
}
else
{
//找到 删除
node* parent = del->_parent;
node* q;
bool empty = false;
int deldir; //两个孩子都为空时,判断方向
int d;/*左重-1 右重1*/
//被删节点两个孩子
if (del->_left != nullptr && del->_right != nullptr)
{
//找前驱替换
node* leftmax = del->_left;
//node* q = del;
while (leftmax->_right)
{
leftmax = leftmax->_right;
}
parent = leftmax->_parent;
//node* leftnode = leftmax->_left;
//交换值
std::swap(del->_kv, leftmax->_kv);
//从leftmax的父节点开始更新
del = leftmax;
}
//右节点不为空
if (del->_left != nullptr)
{
q = del->_left;
}
else
{
if (del->_left == nullptr && del->_right == nullptr)
{
empty = true;
}
q = del->_right;
}
//判断是根节点
if (del == _root)
{
_root = q;
}
else
{
//判断左右,连接
if (parent->_left == del)
{
deldir = -1;
parent->_left = q;
}
else
{
deldir = 1;
parent->_right = q;
}
if (q != nullptr)
{
q->_parent = parent;
}
//重新平衡
while (parent)
{
//左右都为空
if (empty)
{
if (deldir == -1)
{
parent->_bf++;
}
else
{
parent->_bf--;
}
empty = false;
}
else
{
if (parent->_right == q)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
}
//|bf|=1;不影响高度,退出
if (parent->_bf == 1 || parent->_bf == -1)
{
break;
}
//|bf|==2,需要旋转,判断子树的bf
if (parent->_bf != 0)
{
//右边重,看右子树的bf
if (parent->_bf < 0)
{
d = -1;
q = parent->_left;
}
else
{
d = 1;
q = parent->_right;
}
//单旋转调整,更改bf,不影响高度,退出
if (q->_bf == 0)
{
if (d == -1)
{
RotateRight(parent);
parent->_bf = -1;
q->_bf = 1;
}
else
{
RotateLeft(parent);
parent->_bf = 1;
q->_bf = -1;
}
break;
}
//q和parent同号
if (q->_bf == d)
{
//p = -2 d = -1
if (d == -1)
{
RotateRight(parent);
}
// p = 2 d = 1
else
{
RotateLeft(parent);
}
}
else
{
//旋转后重新连接
// p = 2 d = -1
if (q->_bf == -1)
{
RotateRL(parent);
}
else
{
RotateLR(parent);
}
}
//旋转后更新节点
q = parent;
parent = parent->_parent;
}
//继续向上查找
q = parent;
parent = parent->_parent;
}
}
delete del;
return true;
}
return false;
}
}
private:
node* _root = nullptr;
};
9. 性能
avl树是一颗绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值不超过1，这样可以保证查询时高效， l o g 2 ( N ) log_2(N) log2(N)。但是如果要对avl树做一些结构修改，性能非常低下。比如：插入时要维护绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑avl树，但一个结构经常修改，就不太适合
