二叉排序树是数据结构课程中极为重要的动态查找表结构，在软考软件设计师上午题中几乎每年都有涉及。它的正式名称是二叉排序树，英文缩写为 BST，全称为 Binary Sort Tree，在教材中又常常被称作二叉查找树或二叉搜索树。这三个名称指向的是同一个概念，只是不同教材、不同翻译习惯下的叫法差异。软考命题中这三个名字会交替出现，考生必须能够一眼识别它们是同一个东西。
从形式化定义上看，二叉排序树要么是一棵空树，要么是满足如下三条性质的二叉树。第一，若左子树不为空，则左子树上所有结点的关键字值都小于根结点的关键字值。第二，若右子树不为空，则右子树上所有结点的关键字值都大于根结点的关键字值。第三，左右子树本身也分别是一棵二叉排序树。这三条性质相互嵌套，形成了递归定义的完整闭环。需要注意的是，这里强调的关键字值，也就是结点存储的数据项，在软考语境中通常简化为一个整数或者一个可比较大小的键值。
这个定义里有一个非常关键、也最容易被考生忽略的细节，那就是"所有结点"四个字。左子树上不是仅仅左孩子比根小，而是左子树上的每一个结点都要比根小；右子树上也不是仅仅右孩子比根大，而是右子树上的每一个结点都要比根大。如果只记住了"左孩子小于根、右孩子大于根"这半句，就极容易在判断题上栽跟头。一棵二叉树如果只是满足"每个结点的左孩子比它小、右孩子比它大"，但存在某个左子树的结点值大于根结点的情况，那它根本就不是二叉排序树，这一点在定义辨析题里是命题人最爱的陷阱。
为了更直观地理解这个全局约束，可以举一个具体的例子。假设有一棵二叉树，根结点是五十，根结点的左孩子是三十，右孩子是七十，而三十这个结点的右孩子是六十。表面上看，每个结点的直接孩子都满足左小右大，三十小于五十，七十大于五十，六十大于三十，似乎没有任何问题。但实际上，六十位于根结点五十的左子树上，而六十却大于五十，这就违反了"左子树所有结点都小于根结点"的全局约束，因此这棵二叉树不是一棵二叉排序树。这个反例清楚地说明，判断一棵二叉树是否为二叉排序树，绝不能只看每一层的父子大小关系，必须检查每一个结点与其所在子树根结点的全局序关系是否成立。
二叉排序树与普通二叉树最本质的区别，在于它施加了关键字大小的序关系约束。普通二叉树只关心结点之间的父子关系与树的形态，对结点存储的值没有任何大小要求；而二叉排序树在这个基础上，额外要求左小右大的全局有序约束。正是因为这种序约束的存在，二叉排序树才拥有了普通二叉树所不具备的快速查找能力，才能够在平均情况下把查找的时间复杂度控制在对数级别，才成为动态查找表最经典的物理实现方式之一。
二叉排序树的查找是它一切价值的起点。查找的过程可以这样描述：从根结点开始，将待查找的关键字与当前结点比较，如果相等，则查找成功；如果待查关键字小于当前结点，就转去左子树继续查找；如果大于当前结点，就转去右子树继续查找。如此层层下探，直到找到目标结点，或者走到空指针位置宣告查找失败。
这一查找策略的本质，是每一层比较都把搜索空间大致砍掉一半，其思想与有序数组的二分查找如出一辙。区别在于，有序数组的二分查找依赖的是数组下标可以直接定位到中间位置，而二叉排序树则是通过指针把这种"折半"的逻辑固化在了树的结构里。所以有人把二叉排序树的查找称为"结构化的二分查找"，这个说法是相当准确的。理解了这一点，也就理解了为什么二叉排序树的查找效率高度依赖树的高度。
二叉排序树的插入与查找是紧密结合的。插入一个新结点时，先从根结点开始做一次查找，当查找在某个空指针位置失败时，这个位置就是新结点应当安放的位置。换句话说，二叉排序树的新结点永远是被插入到树中某个空缺的叶子位置上的，它绝不会出现在树的中间。这个"插入必在叶子"的结论，是软考选择题反复考查的一个要点。
正因为插入位置由查找过程唯一确定，所以对于同一组关键字，采用不同的插入顺序，会得到形态完全不同的二叉排序树。先插入的值会成为根结点，后续的值按照大小关系被逐层分配下去。这个结论直接引出了二叉排序树一个著名的性能隐患：如果关键字恰好按照递增或递减的顺序插入，那么树会退化成一条单链，查找性能从对数级别急剧退化到线性级别，这也正是后面要讲到的平衡化处理的动因。
删除是二叉排序树三种基本操作里最复杂的一个，也是软考最容易出计算题和辨析题的地方。删除一个结点要分三种情况来讨论。第一种情况，被删除的结点是叶子结点，也就是它没有任何孩子，此时直接将它删除即可，不需要做任何结构调整。第二种情况，被删除的结点只有一棵子树，要么只有左子树，要么只有右子树，此时让它的这棵子树直接顶替它的位置即可，相当于把该结点从链条上摘除。
第三种情况是最棘手的，被删除的结点同时拥有左右两棵子树。这种情况下不能简单地直接摘除，因为摘除之后需要有一个合适的结点来填补空缺，并且填补之后整个树仍然要保持二叉排序树的有序性质。教材给出的标准做法是：用被删结点左子树中的最大值结点，或者右子树中的最小值结点来顶替它。左子树的最大值结点，就是沿着左子树一路向右走到尽头的那一个结点，也就是中序遍历序列中被删结点的直接前驱；右子树的最小值结点，就是沿着右子树一路向左走到尽头的那一个结点，也就是中序遍历序列中被删结点的直接后继。用前驱或后继顶替，能够保证替换之后树的有序性不被破坏，这是删除操作的精髓所在。
为什么用前驱或后继顶替就能保证有序性不被破坏，这背后有严密的逻辑。以中序前驱为例，中序前驱是左子树中值最大的结点，它比左子树上除它之外的所有结点都大，同时又比被删结点的值小，因而也比右子树上所有结点都小。因此，把中序前驱放到被删结点的位置，它对左子树上除它自身之外的其余结点而言仍然更大，对右子树上的所有结点而言仍然更小，恰好满足根结点的序约束。同理，中序后继是右子树中值最小的结点，它比右子树上其余结点都小，又比左子树上所有结点都大，同样完美地满足了根结点的位置要求。这个逻辑推导是删除操作的理论支撑，理解它之后，删除操作就不再是死记硬背的步骤，而是一条可以随时推理出来的规则。
二叉排序树有一条贯穿始终的核心性质：对一棵二叉排序树做中序遍历，得到的结点关键字序列一定是一个递增的有序序列。这一性质可以从定义直接推导出来。中序遍历的顺序是"左子树、根、右子树"，由于左子树的所有结点都小于根，右子树的所有结点都大于根，所以先遍历完左子树再访问根再遍历右子树，输出必然是从小到大的。这个性质是理解二叉排序树的钥匙，也是软考命题的高频考点。反过来理解同样成立：一棵二叉树的结点如果中序遍历结果是有序的，那么它基本就具备二叉排序树的特征，这为"验证一棵树是否为二叉排序树"这类题目提供了最直接的判定手段。
二叉排序树按照形态可以划分为两个大类，一类是形态良好的平衡二叉排序树，另一类是形态退化的链状二叉排序树。当插入顺序比较随机时，树的高度大致维持在 O(log n) 的水平，此时查找、插入、删除的时间复杂度都能保持在 O(log n)。而当插入顺序单调时，树会退化成一条近似的单链，高度逼近 n，此时各项操作的时间复杂度都会退化到 O(n)。这个从对数到线性的性能滑坡，是二叉排序树最大的软肋，也是推动人们去设计平衡二叉树、红黑树等一系列改进结构的根本原因。
平衡二叉树，也称作 AVL 树，是二叉排序树最经典的一种改进形态。它的核心约束是：树中任意一个结点的左右子树高度之差的绝对值不超过一，这个高度差被称作平衡因子。通过引入平衡因子并在插入删除后做旋转调整，AVL 树能够把树的高度严格控制在 O(log n) 的范围内，从而保证查找性能不会退化。软考软件设计师对 AVL 树的考查，主要集中在平衡因子的计算、失衡后的旋转类型识别、以及插入一个结点后如何重新平衡这几个点上。平衡因子等于左子树高度减去右子树高度，取值只可能是负一、零、正一，一旦某个结点的平衡因子
本篇完！