#创作计划#浅谈 AVL 树和红黑树－1
2026-04-17 20:27:48
发布于：浙江
警告：五年级以上看不懂可能无法进 noip @yhz@yhz@wcqk@wcqk
请不要发布无意义评论，否则会删评。若发布大量发布类似“qp”“ddd”等评论也会删，发布一次无所谓
本篇讲一些前置知识，有点杂，排版和内容可能不是很好，语文也很差，请见谅。由于时间较为零碎，完成不知道要几个世纪了
前言（跳过本部分并不影响您阅读）：
先说一下我为啥写这个，AVL 树在 OI 中似乎啥用没有。但是我觉得学起来挺有意思的，对学红黑树或许有那么一丁点的帮助（？）。就当巩固一下平衡树再提升一下思维吧。
为啥我觉得指针比数组更看得懂呢🤔
概览
因为 ACGO 这边的同学知识面普遍较浅，我就讲的稍稍前面一点，但是总不可能让我给你讲输入输出的对吧。二叉树基础（指针），BST，平衡树的旋转操作，Treap（或许并没什么关联）。写的浅一点。鉴定为想水一篇精华帖。
二叉树基础
或许并没什么好讲的，但是因为我偏爱指针而且大部分人都不写指针我就来讲一下（吧）。
首先我们建立一个结构体，用于储存二叉树节点的信息，如下：
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);
}
为什么这里要说“A 的左孩子的右孩子”而不直接说“C 的右孩子”。因为在实际代码中，我们是通过当前节点，也就是我们现在所指的 A 节点来进行旋转操作，只是间接的经过左孩子节点也就是我们现在说的节点 C。这样子写代码会更好理解点。不过本质上没啥区别。 ↩︎
有帮助，赞一个