二叉排序树是数据结构中一类特殊的二叉树，它把"有序"这一性质直接编码进了树的形态里。教材与标准文献对它的定义十分严格：二叉排序树或者是一棵空树，或者是满足如下性质的二叉树——若它的左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值；若它的右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值；并且它的左子树和右子树本身也各是一棵二叉排序树。这段定义有三个必须同时成立的要点，缺一不可。第一，比较的基准是根结点，左子树整体小于根，右子树整体大于根，而不是只看某个叶子结点与根的大小关系。第二，大小关系对所有结点成立，即左子树上任意一个结点都要小于根，右子树上任意一个结点都要大于根，这是"全局有序"而非"局部有序"。第三，递归性要求左子树和右子树自身也必须满足二叉排序树的定义，这就把约束从根一路传递到整棵树的每一个结点上。
二叉排序树还有两个等价的说法，分别是二叉查找树和二叉搜索树，这三个名称指向的是同一个概念。在历年真题中，命题人有时写二叉排序树，有时写二叉查找树，有时写二叉搜索树，考生必须能一眼识别它们其实是同一类结构。之所以有多个名字，是因为这一结构同时承载了"排序"与"查找"两种视角：从构造角度看，按中序遍历这棵树得到的恰好是从小到大的有序序列，因此称二叉排序树；从使用角度看，它被设计出来就是为了让查找过程能够像二分查找一样高效，因此称二叉查找树或二叉搜索树。理解这个"一名多译"的细节，本身就是一个容易被忽视的考点。
平衡二叉树，又称AVL树，是在二叉排序树基础上附加了严格平衡约束的一种自平衡二叉查找树。它的定义同样精炼：平衡二叉树是一棵二叉排序树，且树中任意一个结点的左子树与右子树的高度之差的绝对值不超过一。这里引入了一个核心度量——平衡因子，它被定义为某个结点左子树的高度减去右子树的高度所得的差。按照定义，平衡二叉树中每一个结点的平衡因子只能取负一、零、正一这三个值；一旦某个结点的平衡因子落到了负二或正二甚至更极端的情况，整棵树就不再满足平衡条件，必须通过调整来恢复平衡。需要特别强调的是，平衡因子的计算单位是"高度差"，而不是结点个数差，也不是层数差。高度是指从该结点到其最远叶子结点所经过的边数或结点数，具体口径在不同的教材里略有差异，但无论采用哪一种口径，平衡因子的判断结论是一致的，考生只要在整套题目中保持一致即可。
平衡二叉树的提出背景，恰恰是二叉排序树存在的一个致命缺陷。一棵形态良好的二叉排序树，其查找效率可以逼近二分查找的对数级复杂度；但二叉排序树的形态完全取决于关键字插入的先后顺序，当关键字以递增或递减的顺序逐个插入时，得到的将是一棵退化成单链表形态的树，此时查找效率从对数级急剧跌落到线性级。平衡二叉树通过在每一次插入和删除之后主动维护"高度差不超过一"这一约束，保证了树的高度始终维持在接近对数量级的水平，从而把查找、插入、删除的最坏时间复杂度稳稳地控制在对数级。这个"为何要平衡"的动机，是理解后续所有旋转操作的钥匙，也是命题人反复出题考查的底层逻辑。
二叉排序树的查找过程，本质上是对二分查找思想在树形结构上的重新实现。查找从根结点开始，把待查找的关键字与当前结点的关键字进行比较：若二者相等，则查找成功，返回当前结点；若待查找关键字小于当前结点关键字，则转入左子树继续查找；若待查找关键字大于当前结点关键字，则转入右子树继续查找。如此反复，直到找到目标结点或者走到一棵空子树为止，走到空子树即代表查找失败，说明树中不存在该关键字。这条"从根出发、按大小分流"的查找路径，与二分查找在有序数组上每次折半比较的思路完全同构，区别只在于二分查找的分界点由下标计算得出，而二叉排序树的分界点由树的结构本身承载。
查找效率与树的高度直接挂钩。在一棵接近满二叉树的形态下，树的高度约为以二为底结点数的对数，因此一次查找最多只需要经过对数级次数的比较；而在退化形态下，树的高度等于结点个数，查找退化为沿单链表逐个扫描。这一对比揭示了二叉排序树的核心价值与核心风险都集中在"形态"二字上。命题人经常围绕查找成功与查找失败的平均查找长度做文章，尤其是二叉排序树的平均查找长度会随着树的形态变化而变化，这与顺序表、有序表等静态结构有着本质区别，是高频易错点。
插入操作遵循一个直观的原则：新结点一定是作为叶子结点插入的。具体做法是，从根结点出发，按照与查找相同的大小比较规则一路向下，找到一个合适的位置，当走到某棵子树为空时，把新结点挂在那里。之所以新结点一定是叶子，是因为二叉排序树的定义要求插入后仍然保持"左小右大"的全局有序性，而挂到空子树位置恰好不会破坏这一性质。若插入过程中发现待插入关键字与某个已有结点关键字相等，则视具体约定处理，通常不允许重复关键字，或者将其视为更新操作。
插入操作还有一个常被忽视的细节值得单独说明。二叉排序树允许以任意顺序插入关键字，但插入顺序完全决定了最终树的形态。同样一组关键字，例如依次为五十、三十、七十、二十、四十、六十、八十，若按这个相对均衡的顺序插入，得到的是一棵接近满二叉树的形态，树高约为三；若改按二十、三十、四十、五十、六十、七十、八十这样的递增顺序插入，则每一次新结点都挂在前一个结点的右孩子位置，最终得到一条完全右倾的单链，树高高达七。两组插入产生的是结点数相同、形态迥异的两棵树，查找效率也因此天差地别。这个例子直观地说明了二叉排序树为何需要平衡机制来兜底，也是理解后续平衡二叉树动机的最直接切入点。
删除操作远比插入复杂，因为删除的结点不一定是叶子，删除后必须保证剩余部分仍然是一棵合法的二叉排序树。删除分三种情况讨论。第一种情况，被删结点是叶子结点，直接删除即可，不影响其余结构。第二种情况，被删结点只有一个孩子，那么让这个孩子直接顶替被删结点的位置即可，这相当于在树的链条上摘掉一个中间环节。第三种情况，被删结点有两个孩子，这是最复杂的情形，通用的处理办法是寻找被删结点的中序前驱或中序后继，用它来顶替被删结点。中序前驱是左子树中最靠右的结点，中序后继是右子树中最靠左的结点，二者都必然要么是叶子、要么只有一个孩子，因此顶替之后问题被转化为前两种情况。删除操作的这个三分法，是数据结构考试中的经典考点，命题人常以选择题形式考查删除某结点后树的形态如何变化。
当插入或删除导致某个结点的平衡因子超出允许范围时，平衡二叉树通过旋转操作来恢复平衡。旋转的本质，是在不改变结点之间中序次序的前提下，重新组织局部子树的结构，把"长"的一侧的高度降下来，把"短"的一侧的高度补上去。旋转之所以能够保持二叉排序树的有序性，是因为它只是局部改变了父子关系，而中序遍历的结果保持不变。理解旋转必须牢牢抓住"中序次序不变"这条铁律，它是判断旋转是否正确的最可靠标准。
旋转操作分为四种基本类型，与插入导致失衡的四种情形一一对应。第一种是LL型，即新结点插入了某个结点左孩子的左子树，导致该结点左子树过重，此时做一次右单旋转即可恢复。第二种是RR型，即新结点插入了某个结点右孩子的右子树，此时做一次左单旋转。第三种是LR型，新结点插入左孩子的右子树，需要先对左孩子做左旋转，再对失衡结点做右旋转，即左右双旋转。第四种是RL型，新结点插入右孩子的左子树，需要先对右孩子做右旋转，再对失衡结点做左旋转，即右左双旋转。这四种旋转的名称，前一个字母表示失衡发生在哪一侧，后一个字母表示插入发生在该侧孩子树的哪一侧，LL和RR只需一次单旋转，LR和RL需要两次旋转。
四种旋转各有其精确的触发条件和操作细节，考生必须逐类吃透。LL型旋转的操作对象是一条"左倾"的链：失衡结点设为A，其左孩子设为B，旋转后B上升为新子树的根，A下降为B的右孩子，B原来的右子树挂到A的左子树上。这样处理后，A的左子树高度减一，右子树高度加一，平衡得以恢复。RR型旋转与LL型完全对称，只是方向相反，A的右孩子B上升为根，A下降为B的左孩子，B原来的左
本篇完！