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