#创作计划#浅谈 AVL 树和红黑树－1
2026-04-27 13:38:56
发布于：浙江
警告：五年级以上看不懂可能无法进 noip @yhz@yhz@wcqk@wcqk@Stars_Seeker@Stars_Seeker
请不要发布无意义评论，否则会删评。若发布大量发布类似“qp”“ddd”等评论也会删，发布一次无所谓
本篇讲一些前置知识，有点杂，排版和内容可能不是很好，语文也很差，请见谅。由于时间较为零碎，完成不知道要几个世纪了
前言（跳过本部分并不影响您阅读）：
先说一下我为啥写这个，AVL 树在 OI 中似乎啥用没有。但是我觉得学起来挺有意思的，对学红黑树或许有那么一丁点的帮助（？）。就当巩固一下平衡树再提升一下思维吧。
为啥我觉得指针比数组更看得懂呢🤔
概览
因为 ACGO 这边的同学知识面普遍较浅，我就讲的稍稍前面一点，但是总不可能让我给你讲输入输出的对吧。二叉树基础（指针），BST，平衡树的旋转操作，平衡被破坏的情况。写的浅一点。鉴定为想水一篇精华帖。
二叉树基础
或许并没什么好讲的，但是因为我偏爱指针而且大部分人都不写指针我就来讲一下（吧）。
首先我们建立一个结构体，用于储存二叉树节点的信息，如下：
struct Treenode{
int val;
Treenode* l;//左孩子指针
Treenode* r;//右孩子指针
Treenode(int v):val(v),l(nullptr),r(nullptr){}
};
其中 Treenode(int v):val(v),l(nullptr),r(nullptr){} 是构造函数。我们每创建一个新的节点，调用这个构造函数就可以“初始化”这一节点。这里的作用是将该节点的值初始为 ，左右孩子指针初始为空。
接下来建立一个指针数组，用于存储指向节点 的指针。
std::vector<Treenode*> Node;
这里根据实际情况选择是否需要。像后文所讲的 AVL 树就不需要。
然后是输入，这里的输入方式是每行给出节点 的左右孩子，若为 则代表它没有孩子。
void build(){
int n;
std::cin >> n;
Node.resize(n+1,nullptr);//初始化
for(int i=1;i<=n;i++)Node[i]=new Treenode(i);
for(int i=1;i<=n;i++){
int l,r;
std::cin >> l >> r;
Node[i]->l=(l?Node[l]:nullptr);
Node[i]->r=(r?Node[r]:nullptr);
}root=Node[1];//root 为当前根节点
}
前序遍历：顺序为根，左，右，递归即可：
void first(Treenode* node){
if(node==nullptr)return ;
std::cout << node->val << " ";
first(node->l);
first(node->r);
}
中序遍历：顺序为左，根，右
void middle(Treenode* node){
if(node==nullptr)return ;
middle(node->l);
std::cout << node->val << " ";
middle(node->r);
}
后序遍历：顺序为左，右，根
void back(Treenode* node){
if(node==nullptr)return ;
back(node->l);
back(node->r);
std::cout << node->val << " ";
}
二叉搜索树（BST）
觉得有点跑题了赶紧回来
首先我们了解一下 BST 的基本概念。BST 是一种特殊的二叉树，满足以下性质：
- 空树为 BST
- 若左子树不为空，则左子树的所有节点权值小于根节点
- 若右子树不为空，则右子树所有节点权值大于根节点
- 二叉搜索树的所有子树均为二叉搜索树
看着很麻烦，但是你先别急。实现起来真的很简单。
节点结构体
struct Node{
int val,siz,cnt;//真实值，字树大小，计数器
Node *ls,*rs;
Node(int v):val(v),siz(1),cnt(1),ls(0),rs(0){}//构造函数
}*root;
不多赘述.具体请参考注释。
插入
主要是个判断，大概这样：
首先，如果与当前节点值相等：计数器加一，返回
如果小于当前节点：有左孩子，递归左孩子；否则新建节点
如果大于当前节点：有右孩子：递归右孩子；否则新建节点
别忘了增加子树大小。
void push(Node* &x,int v){
x->siz++; //增加子树大小
if(x->val==v){//值已存在，计数器加一
x->cnt++;
return ;
}if(x->val>v){//要插入的值更小，往左子树走
if(x->ls!=0)push(x->ls,v);//左孩子存在，递归
else x->ls=new Node(v);//左孩子不存在，新建
}else{// 要插入的值更大，往右子树走
if(x->rs!=0)push(x->rs,v);//右孩子存在，递归
else x->rs=new Node(v);//右孩子不存在，新建
}
}
查询前驱——小于 的最大数
和插入差不多，因为二叉搜索树保证了 左子树<根节点<右子树。根据这条性质我们可以轻松实现查询前驱的功能。具体实现请参考代码注释。
int queryfr(Node* x,int val,int ans){
if(x->val>=val){//当前值大于等于目标，往左找更小的值
if(x->ls==0)return ans;//没有左子树，直接返回答案
else return queryfr(x->ls,val,ans);
}else{//当前值小于目标，尝试更新答案，往右找更大的值
if(x->rs==0)return x->val;
else return queryfr(x->rs,val,x->val);
}
}
查询后继
和前驱一样的，只不过反了一下，参考注释即可。不多赘述。
int queryne(Node* x,int val,int ans){
if(x->val<=val){//当前值小于等于目标，往右找
if(x->rs==0)return ans;//右子树丝了，返回答案
else return queryne(x->rs,val,ans);
}else{//当前值大于目标，尝试更新答案，往左找
if(x->ls==0)return x->val;
else return queryne(x->ls,val,x->val);
}
}
删除
棍木
查询第 k 小
也是递归实现，若在左子树则递归左子树，在当前节点则直接返回，当在右子树的时候记得减去左子树和当前节点的数量。
int queryrk(Node* x,int rk){
if(x==0)return INF;// 空节点
int lsiz=0;
if(x->ls)lsiz=x->ls->siz;//左子树大小
if(lsiz>=rk)return queryrk(x->ls,rk);//第 k 小在左子树
if(lsiz+x->cnt>=rk)return x->val;//第 k 小就是当前节点
return queryrk(x->rs,rk-lsiz-x->cnt);//第 k 小在右子树，减去左子树和当前节点的数量
}
查排名
因为二叉搜索树的性质是左子树 根节点 右子树，所以当找到目标值，排名就是左子树的大小。若目标在右子树，则为右子树的查询结果加上左子树大小、当前节点值重复的数量。
int queryval(Node* x,int val){
if(x==0)return 0;//空节点
int lsiz=0;
if(x->ls)lsiz=x->ls->siz;//左子树大小
if(val==x->val)return lsiz;//找到目标值，排名为左子树大小，由 BST 的性质可得
if(val<x->val)return queryval(x->ls,val);//目标值更小，去左子树
return queryval(x->rs,val)+lsiz+x->cnt;//目标值更大，右子树查询结果+左子树 +当前节点数量
}
完整代码就不放了。那么这样我们就得到了一个朴实无华的 BST 代码。
平衡树的旋转与平衡调整
使我的节点旋转
旋转是平衡树维持平衡的一个重要方法。它可以在不违反二叉搜索树的性质下降低树高。这里我们来讲左旋（zag）和右旋（zig）。
右旋
先来讲右旋，其实你学完右旋就能直接推出左旋了。
下面给出两幅图，各位可以进行理解。分别是对于节点 A 的右旋前和右旋后的：
仔细观察，我们可以发现，对于节点 A 的右旋就像是把他的左孩子“提”起来，事实上我们只改变了三个节点的链接关系：
-
将 A 的右孩子 C 的右孩子指针指向 A，将 A 的父指针指向 C；
-
将 A 的左孩子的右孩子的父指针指向 A；
-
将 A 的左孩子指针指向 A 的左孩子的右孩子。
那么这个时候我们的右旋操作就结束了。[1]
void zig(Treap*&u){//右旋
Treap* left_child=u->l;
u->l=left_child->r,left_child->r=u,u=left_child;
pushup(u->r),pushup(u);//更新节点，这里的 pushup 函数在下面的 Treap 里会讲到。
}
左旋
本质上和右旋是一样的，就是把右旋的操作反了一下。这里不多赘述。具体参考代码实现。
void zag(Treap*&u){//左旋
Treap* right_child=u->r;
u->r=right_child->l,right_child->l=u,u=right_child;
pushup(u->l),pushup(u);
}
那么在学完左右旋之后我们来学习如何调整平衡树的平衡。这里介绍四种情况。
LL
当前节点左孩子的左子树过长。通过一次右旋调整[2]
RR
当前节点右孩子的右子树过长，一次左旋调整
LR
当前节点左孩子的右子树过长，左旋当前节点后再右旋。可以理解为先把他变成 LL 型，然后进行右旋操作。
RL
当前节点右孩子的左子树过长，右旋再左旋
鸣谢
| 用户 | 帮助 |
|---|---|
| @AAA逃离森林湖的蔡锡龙批发 | 帮助修改大量格式问题，/bx |
有帮助，赞一个