二叉排序树，又称二叉查找树、二叉搜索树，英文缩写为BST，是软件设计师考试数据结构板块中每年都绕不开的核心考点。它的正式定义可以这样表述：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树——若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值；且左、右子树本身也分别是二叉排序树。这个定义采用的是递归表述，读起来略显拗口，但其技术本质只有一句话：对于树中任意一个结点，其左子树的所有关键字都比它小，右子树的所有关键字都比它大，而这条约束对树中每一个结点同时成立。
要真正理解二叉排序树为什么重要，必须先回到它要解决的工程问题。在程序设计中，数据集合的存储与查找效率始终是一对需要权衡的矛盾。顺序表支持随机访问，折半查找的时间复杂度可以达到对数级别，但插入和删除元素需要移动大量元素，代价高昂；链表插入删除方便，但查找只能从头到尾顺序扫描，时间复杂度退化为线性级别。二叉排序树正是为调和这对矛盾而出现的结构：它把数据按照关键字的大小关系组织成一棵树，使得查找、插入、删除三种操作在最理想的情况下都能维持在树高的量级，也就是对数级别。
这里必须强调一个容易混淆的边界：二叉排序树强调的是结点之间关键字的有序关系，而不是树形态上的某种特定约束。一棵二叉排序树可以是形态各异的——它可能接近一棵完全二叉树，也可能退化成一棵向右或向左倾斜的单枝链表。形态不影响它作为二叉排序树的性质，只要任意结点的左小右大关系满足即可。这个认识是后续理解平衡二叉树、理解旋转操作的逻辑起点。
与二叉排序树密切相关但又必须区分的概念是平衡二叉树。平衡二叉树也称AVL树，得名于它的两位苏联发明者阿德尔森-维尔斯基和兰迪斯。它是在二叉排序树的基础上增加了一条严格的平衡约束：树中任意结点的左右子树高度之差的绝对值不超过一。这个高度之差被称为平衡因子，记作该结点左子树高度减去右子树高度的结果。平衡因子的取值范围被限定在负一、零、正一这三个值以内。一旦某结点的平衡因子超出这个范围，就认为该结点失衡，需要通过旋转操作恢复平衡。因此可以这样概括二者的关系：平衡二叉树是二叉排序树的加强版，它在保持二叉排序树全部有序性质的前提下，额外保证树高始终维持在对数级别，从而杜绝了二叉排序树退化导致的性能劣化。
从软考命题的角度看，这两个概念通常被放在同一道题或相邻的题目里考查，命题人常利用考生对"二叉排序树"与"平衡二叉树"边界模糊的弱点设置干扰项。因此，在概念层面就要把二者的从属关系记牢：平衡二叉树首先是二叉排序树，但二叉排序树不一定是平衡二叉树。
二叉排序树的查找机制本质上是一条从根结点出发、逐层比较、不断缩小搜索范围的路径。查找一个关键字的具体过程是：从根结点开始，若待查关键字等于当前结点关键字，则查找成功；若待查关键字小于当前结点关键字，则转向左子树继续查找；若大于，则转向右子树继续查找；若沿着路径走到了空子树而仍未找到，则判定查找失败。这个过程每一层只做一次比较，每一次比较都排除掉大约一半的候选结点，因此它的比较次数在最理想情况下等于树的高度。
从算法设计的视角看，这个查找过程与有序顺序表上的折半查找在策略上是同构的。折半查找每次取区间中点作为比较基准，二叉排序树查找每次取当前子树根结点作为比较基准，二者的本质都是分治策略——把问题规模在每一步减半。二者的区别在于存储结构：折半查找依赖顺序表的随机访问能力和下标计算，而二叉排序树依赖链式存储的指针链接。理解这层对应关系，就能理解为什么教材说二叉排序树是"树形结构的折半查找"。
值得深入的是，二叉排序树的查找效率高度依赖树的形态，而树的形态又取决于结点插入的先后顺序。如果关键字序列本身接近有序，比如按照从小到大或从大到小的顺序依次插入，那么每次插入的新结点都会成为前一个结点的单一后继，树最终会退化成一条链，此时查找退化为顺序查找，时间复杂度从对数级别恶化为线性级别。这个退化机制正是引入平衡二叉树的根本动因，也是命题人反复设问的逻辑靶点。
二叉排序树的插入操作与查找操作共享同一条路径。插入一个新关键字时，首先执行一次查找，沿着与查找相同的比较路径向下探索，最终必然到达一个空位置，也就是某个叶子结点的空左孩子或空右孩子指针处，新结点就落在这个位置上。由于插入总是发生在叶结点位置，它不会破坏树中已有的有序关系，插入后整棵树仍然满足二叉排序树的性质。
这里有一个极其重要且极易被考生忽略的规律：在插入序列中，第一个被插入的关键字必然是整棵树的根结点。这是因为根结点不依赖任何前驱，后续所有结点都是在已有树的基础上依据大小关系落位的。由这个规律可以推出一条非常实用的解题技巧——当题目给出一个关键字序列要求判定生成的二叉排序树形态时，序列的第一个元素就是根，后续元素依次按照左小右大的规则定位，就能快速手绘构造过程而不必死记结论。
二叉排序树的删除操作是三操作中逻辑最复杂的一个，也是软考下午题算法设计题的热门素材。删除一个结点需要分三种情形处理。第一种情形是待删结点为叶子结点，此时直接将其删除，并把其父结点指向它的指针置空即可。第二种情形是待删结点只有一个孩子，此时让这个孩子直接顶替被删结点的位置，即把父结点原本指向待删结点的指针改为指向这个唯一的孩子。第三种情形是待删结点同时拥有左右两个孩子，此时不能简单删除，而需要找一个替代者来维持有序性。
第三种情形的标准处理策略是：在待删结点的左子树中找到关键字最大的结点，即左子树的最右下结点，用它的值替换待删结点的值，然后转而删除这个最右下结点；或者对称地，在右子树中找到关键字最小的结点，即右子树的最左下结点，用它的值替换后再删除这个最左下结点。这个替代者被称作待删结点的中序前驱或中序后继。之所以选取中序前驱或中序后继，是因为它们在中序遍历序列中紧邻待删结点，替换之后不会破坏整棵树的有序性，而且它们至多只有一个孩子，删除起来只会落入前两种简单情形，从而把复杂问题化归为简单问题。
理解删除操作的中序后继策略，关键在于把握中序遍历与二叉排序树的深刻联系。对二叉排序树进行中序遍历，得到的一定是一个按关键字从小到大排列的有序序列，这是二叉排序树区别于普通二叉树最本质的性质。反过来，这个性质也常常作为判断题的设问点，命题人常把先序遍历、后序遍历混入选项，考查考生对"只有中序遍历才能得到有序序列"这一结论的掌握程度。
平衡二叉树的原理机制集中在平衡因子的维护与旋转操作上。平衡因子的定义是左子树高度减去右子树高度，值域被约束在负一、零、正一之间。每当一次插入或删除导致某个结点的平衡因子绝对值超过一，就需要从该结点开始进行旋转调整，使树恢复平衡。旋转操作有四种基本类型，分别对应失衡的四种形态。
以插入导致失衡为例，若在某结点的左子树的左子树上插入导致失衡，称为左左型，对应一次右旋；若在其左子树的右子树上插入导致失衡，称为左右型，对应先左旋后右旋的双旋转；若在其右子树的左子树上插入导致失衡，称为右左型，对应先右旋后左旋；若在其右子树的右子树上插入导致失衡，称为右右型，对应一次左旋。这四种形态可以概括为：直线型失衡用单旋，折线型失衡用双旋。
旋转操作的几何本质是改变树中局部子树的父子关系，使较高的子树"抬升"为新的根，从而把高度差重新压回允许范围。以右旋为例，围绕失衡结点的左孩子做旋转，让左孩子成为新的根，原根结点降为左孩子的右子树，而左孩子原来的右子树则转移为原根结点的左子树。整个过程只修改少数几个指针，不改变中序遍历得到的序列，因此旋转前后的树仍然是同一棵二叉排序树。抓住"旋转不改变中序序列"这一不变性，是理解并记忆四种旋转最可靠的锚点。
平衡二叉树在插入删除过程中可能出现的失衡情形可以归纳为四种类型，这是软考选择题的高频设问点，必须逐类辨析清楚。左左型的特征是：在失衡结点的左孩子的左子树一侧插入新结点，导致失衡结点的平衡因子由一变为二。此时失衡路径是一条向左延伸的直线，处理方式是围绕失衡结点做一次右旋，旋转后失衡结点与其左孩子互换父子角色，平衡因子恢复。右右型是左左型的镜像，在右孩子的右子树一侧插入导致失衡，路径向右延伸，处理方式是围绕失衡结点做一次左旋。
本篇完！