我要评论目录
1.概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此，两位俄罗斯的数学家g.m.adelson-velskii 和e.m.landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵avl树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是avl树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
高度之差=右子树高度 - 左子树高度
avl == 高度平衡二叉树搜索树
由于avl树的自平衡特性，它适用于需要频繁插入和删除操作的场景，尤其是对于需要快速搜索和有序遍历的数据集合。
为了涵盖更多的情况，例如为节点个数为 4 如下，高度差 1 也相对平衡了
增删查改：高度次->o（logn）
最后一 h 层有 2^(h-1)个节点
满二叉树和 avl 树 在量级上都是约等于 log n 的
2.实现
2.1 初始化
avl树的节点定义包括以下几个属性：
- 值：每个节点存储的值，可以是任意类型，通常是一个关键字或数据。
- 左子节点指针：指向当前节点的左子节点的指针。左子节点的值应该小于或等于当前节点的值。
- 右子节点指针：指向当前节点的右子节点的指针。右子节点的值应该大于当前节点的值。
- 父节点指针：指向当前节点的父节点的指针。根节点的父节点指针为空。（为了便于后面更好的更新设计的）
- 平衡因子：表示当前节点的左子树高度和右子树高度之差。平衡因子可以为-1、0或1。
下面是一个示例代码来定义一个avl树的节点结构：
template<class k, class v>
struct avltreenode
{
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) //balance factor
{}
};2.2 插入
avl树就是在二叉搜索树的基础上引入了平衡因子，因此avl树也可以看成是二叉搜索树。那么avl树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新节点
- 调整节点的平衡因子
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* 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;//再指回去插入这部分代码倒是没问题，难的是新节点插入后，avl树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了avl树，破坏了avl树就需要旋转调整再次变成avl树。
如何根据这三种情况来实现插入和对高度的管理？
新增支点：右子树高度++，左子树高度--
插入会对祖先产生影响，平衡因子为 0 了，就再不会对上面的祖先产生影响了，变 0 就平衡了
对以上插入情况，分析可知
是否继续向上更新依旧：子树的高度是否变化
- parent->_bf == 0，说明之前parent->_bf是1或者-1，说明之前parent一边高一边低，而这次的插入是把矮的那边填上了，parent所在子树高度不变，不需要往上继续更新。
- parent->_bf == 1 或者 -1，说明之前parent->_bf为0，两边一样高，现在插入使一边变得更高了，parent所在子树高度变了，继续往上更新。
- parent->_bf == 2 或者 -2，说明之前parent->_bf是1或者-1，现在插入导致严重不平衡，违反规则，就地处理—>旋转。
_bf==0 或者更新到了根节点的时候
实现平衡因子的更新
// ... 控制平衡
// 更新平衡因子
while (parent)
{
if (cur == parent->_left)
{
parent->_bf--;
}
else // if (cur == parent->_right)
{
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)
{
rotatel(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
}接下来我们来看看旋转的实现
2.2.1 旋转（重点）
左单旋
[c++] 详解avl树左旋的实现~
旋转的时候需要注意的问题：
- 保持他是搜索树
- 变成平衡树且降低这个子树的高度
核心操作：
parent->right=cur->left;
cur->left=parent;如下情况都会用到左旋：
代码：
void rotatel(node* parent)
{
// 保存父节点的右子节点
node* cur = parent->_right;
// 保存右子节点的左子节点
node* curleft = cur->_left;
// 利用区间性，将子左给父右
parent->_right = curleft;
if (curleft)
{
// 将右子节点的左子节点作为父节点的右子节点
curleft->_parent = parent;
}
// 将父节点作为右子节点的左子节点
cur->_left = parent;
// 保存父节点的父节点
node* ppnode = parent->_parent;
// 将父节点的父节点指向右子节点
parent->_parent = cur;
// 判断原父节点是否为根节点
if (parent == _root)
{
// 更新根节点为右子节点
_root = cur;
// 将新根节点的父指针置为空
cur->_parent = nullptr;
}
else
{
// 判断原父节点是其父节点的左子节点还是右子节点
if (ppnode->_left == parent)
{
// 更新父节点的左子节点为右子节点
ppnode->_left = cur;
}
else
{
// 更新父节点的右子节点为右子节点
ppnode->_right = cur;
}
// 更新右子节点的父指针为父节点的父节点
cur->_parent = ppnode;
}
// 将父节点和右子节点的平衡因子都设置为0，表示树已经平衡
parent->_bf = cur->_bf = 0;
}右单旋
代码：
void rotater(node* parent)
{
// 获取父节点的左子节点
node* cur = parent->_left;
// 获取左子节点的右子节点
node* curright = cur->_right;
// 将左子节点的右子节点作为父节点的左子节点
parent->_left = curright;
if (curright)
{
// 更新左子节点的右子节点的父指针
curright->_parent = parent;
}
// 引入父父节点
node* ppnode = parent->_parent;
// 将父节点作为左子节点的右子节点
cur->_right = parent;
// 更新父节点的父指针
parent->_parent = cur;
// 判断原父节点是否为根节点
if (ppnode == nullptr)
{
// 更新根节点为左子节点
_root = cur;
// 将新根节点的父指针置为空
cur->_parent = nullptr;
}
else
{
// 判断原父节点是其父节点的左子节点还是右子节点
if (ppnode->_left == parent)
{
// 更新父节点的左子节点为左子节点
ppnode->_left = cur;
}
else
{
// 更新父节点的右子节点为左子节点
ppnode->_right = cur;
}
// 更新左子节点的父指针
cur->_parent = ppnode;
}
// 将父节点和左子节点的平衡因子都设置为0，表示树已经平衡
parent->_bf = cur->_bf = 0;
}双旋
左右旋转：插入的两种情况，看的是折线情况
旋转判断
根据 parent 和 cur 的平衡因子，实现对使用哪种旋转的判断
else if (parent->_bf == 2 || 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);
}
break;
}
else
{
assert(false);
}
}
1.
双旋的结果本质：比 60 小 ，比 30 大的小插入 到 30 下面，找到一个区间中的点
2.❗ 双旋后，对平衡因子的处理
3.h==0 60 本身就是插入的
三种情况，关心 60 的值是-1 0 1
不存在其他奇怪的情况，分别做了 60 的左右
以 rl 为例实现代码：
void rotaterl(node* parent)
{
node* cur = parent->_right;
node* curleft = cur->_left;
int bf = curleft->_bf;
rotater(parent->_right);
rotatel(parent);
//举例思考填写
if (bf == 0)
{
cur->_bf = 0;
curleft->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
cur->_bf = 0;
curleft->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
cur->_bf = 1;
curleft->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}lr 旋转：
平衡因子是根据 curright 初始情况，经过旋转后的图分析分类后得带的
⭕具体而言，先左单旋再右单旋的操作步骤如下：
最后一部分使用了if语句判断旋转后各个节点的平衡因子，并进行相应的调整，以便使avl树保持平衡。
void rotatelr(node* parent)
{
node* cur = parent->_left;
node* curright = cur->_right;
int bf = curright->_bf;
rotatel(parent->_left);
rotater(parent);
//解耦合，旋转bf 重新定义
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
}2.3 判断测试
树的结构出问题了，某次旋转出事了
我们可以根据avl树的性质来测试
一棵avl树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是avl树
- 即左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）
求高度这有个对重载函数的巧妙使用:
int height()
{
return height(_root);
}
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;
}对于平衡的测试：
isbalance(node* root) 是一个递归函数，其工作流程如下：
bool isbalance()
{
return isbalance(_root);
}
bool isbalance(node* root)
{
if (root == nullptr)
return true;
int lefthight = height(root->_left);
int righthight = height(root->_right);
if (righthight - lefthight != root->_bf)
{
cout << "平衡因子异常:" <<root->_kv.first<<"->"<< root->_bf << endl;
return false;
}
return abs(righthight - lefthight) < 2
&& isbalance(root->_left)
&& isbalance(root->_right);
}
private:
node* _root = nullptr;
public:
int _rotatecount = 0;
};手动制作条件断点，一定要注意父亲回指的设定
// 更新父节点的父指针
parent->_parent = cur;对于这个纰漏的处理，来检验和调试这个问题
测试：
int main()
{
avltree<int, int> tree;
// 插入一些节点
tree.insert({10, 10});
tree.insert({20, 20});
tree.insert({30, 30});
tree.insert({40, 40});
tree.insert({50, 50});
cout << "树高度: " << tree.height() << endl;
cout << "树是否平衡: " << (tree.isbalance() ? "是" : "否") << endl;
// 插入更多节点来触发旋转
tree.insert({25, 25});
tree.insert({5, 5});
tree.insert({15, 15});
cout << "树高度: " << tree.height() << endl;
cout << "树是否平衡: " << (tree.isbalance() ? "是" : "否") << endl;
return 0;
}
发现错误：
拼写错误修正：例如 rotatecount 应为 _rotatecount。parent 不要拼写掉 e。
目前还不知道是为什么，重写了一遍，就跑起来了
完整代码：
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class k, class v>
struct avltreenode
{
pair<k, v> _kv;
avltreenode<k, v>* _left;
avltreenode<k, v>* _right;
avltreenode<k, v>* _parent;
int _bf; // balance factor
avltreenode(const pair<k, v>& kv)
: _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(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;
// update balance factor
while (parent)
{
if (cur == parent->_left)
{
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)
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);
break;
}
else
{
assert(false);
}
}
return true;
}
void rotatel(node* parent)
{
++_rotatecount;
node* cur = parent->_right;
node* curleft = cur->_left;
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent;
}
cur->_left = parent;
node* ppnode = parent->_parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
parent->_bf = cur->_bf = 0;
}
void rotater(node* parent)
{
++_rotatecount;
node* cur = parent->_left;
node* curright = cur->_right;
parent->_left = curright;
if (curright)
curright->_parent = parent;
cur->_right = parent;
node* ppnode = parent->_parent;
parent->_parent = cur;
if (ppnode == nullptr)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
parent->_bf = cur->_bf = 0;
}
void rotaterl(node* parent)
{
node* cur = parent->_right;
node* curleft = cur->_left;
int bf = curleft->_bf;
rotater(parent->_right);
rotatel(parent);
if (bf == 0)
{
cur->_bf = 0;
curleft->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
cur->_bf = 0;
curleft->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
cur->_bf = 1;
curleft->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
void rotatelr(node* parent)
{
node* cur = parent->_left;
node* curright = cur->_right;
int bf = curright->_bf;
rotatel(parent->_left);
rotater(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
else
{
assert(false);
}
}
int height()
{
return height(_root);
}
int height(node* root)
{
if (root == nullptr)
return 0;
int leftheight = height(root->_left);
int rightheight = height(root->_right);
return max(leftheight, rightheight) + 1;
}
bool isbalance()
{
return isbalance(_root);
}
bool isbalance(node* root)
{
if (root == nullptr)
return true;
int leftheight = height(root->_left);
int rightheight = height(root->_right);
if (rightheight - leftheight != root->_bf)
{
cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;
return false;
}
return abs(rightheight - leftheight) < 2
&& isbalance(root->_left)
&& isbalance(root->_right);
}
private:
node* _root = nullptr;
public:
int _rotatecount = 0;
};拓展：删除
插入到 0，不用更改
删除到 0，还要更改
删除会更加的复杂，平衡因子的更新，旋转等等，将上面的思路总结和拓展一下，大家有兴趣可以看看如下的实现代码：
bool erase(const pair<t, v>& kv)
{
if (_root == nullptr)
return false;首先，检查树是否为空。如果树为空，直接返回 false，表示删除失败。
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
{
break;
}
}
if (cur == nullptr)
return false;这部分代码用于在树中查找要删除的节点。通过比较当前节点 cur 的键值 cur->_kv.first 与要删除的键值 kv.first，决定向左子树还是右子树继续搜索。最终，cur 将指向要删除的节点，parent 是 cur 的父节点。如果找不到该键值，返回 false。
// 处理删除节点的三种情况
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
if (_root)
_root->_parent = nullptr;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
parent->_bf++;
}
else
{
parent->_right = cur->_right;
parent->_bf--;
}
if (cur->_right)
cur->_right->_parent = parent;
}
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
if (_root)
_root->_parent = nullptr;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
parent->_bf++;
}
else
{
parent->_right = cur->_left;
parent->_bf--;
}
if (cur->_left)
cur->_left->_parent = parent;
}
}
else // 左右子树都不为空
{
node* successorparent = cur;
node* successor = cur->_right;
while (successor->_left)
{
successorparent = successor;
successor = successor->_left;
}
cur->_kv = successor->_kv;
if (successorparent->_left == successor)
{
successorparent->_left = successor->_right;
successorparent->_bf++;
}
else
{
successorparent->_right = successor->_right;
successorparent->_bf--;
}
if (successor->_right)
successor->_right->_parent = successorparent;
cur = successor;
parent = successorparent;
}
delete cur;这一部分处理删除节点的三种情况：
- 左子树为空：直接用右子树替代删除节点。如果删除节点是根节点，直接更新根节点
_root。否则，更新父节点的左或右子树指针，并调整平衡因子。 - 右子树为空：直接用左子树替代删除节点。如果删除节点是根节点，直接更新根节点
_root。否则，更新父节点的左或右子树指针，并调整平衡因子。 - 左右子树都不为空：找到右子树中的最小节点（即中序后继节点），用这个节点替代当前节点。然后删除中序后继节点，并调整其父节点的指针和平衡因子。
// 更新平衡因子并处理旋转
bool islrupdated = true;
while (parent)
{
if (!islrupdated)
{
if (cur == parent->_left)
parent->_bf++;
else
parent->_bf--;
}
islrupdated = false;
if (parent->_bf == 1 || parent->_bf == -1)
return true;
else if (parent->_bf == 0)
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
node* higherchild;
int sign;
if (parent->_bf > 0)
{
sign = 1;
higherchild = parent->_right;
}
else
{
sign = -1;
higherchild = parent->_left;
}
if (higherchild->_bf == 0)
{
if (sign > 0)
{
rotatel(parent);
parent->_bf = 1;
higherchild->_bf = -1;
}
else
{
rotater(parent);
parent->_bf = -1;
higherchild->_bf = 1;
}
return true;
}
else if (higherchild->_bf == sign)
{
if (sign == 1)
rotatel(parent);
else
rotater(parent);
}
else
{
if (sign == 1)
rotaterl(parent);
else
rotatelr(parent);
}
cur = parent;
parent = cur->_parent;
}
else
{
assert(false);
}
}
return true;
}这一部分用于在删除节点后更新平衡因子并处理旋转，以保持树的平衡：
- 平衡因子为 ±1：子树高度没有变化，直接返回。
- 平衡因子为 0：子树高度减少，继续向上更新平衡因子。
- 平衡因子为 ±2：子树严重不平衡，需要旋转。根据较高子树的平衡因子选择合适的旋转方式：
-
- 如果较高子树的平衡因子为 0，进行单旋转。
- 如果较高子树的平衡因子与父节点相同，进行单旋转。
- 如果较高子树的平衡因子与父节点不同，进行双旋转。
通过这些操作，就可以确保树在删除节点后仍然保持平衡啦
发表评论