扫码获取 VIP 码
添加管理员微信获取 VIP 码
二叉排序树是软考数据结构部分的核心考点，同时出现在数据库系统工程师、软件设计师、系统分析师等多个科目的上午选择题与下午试题中，是命题人反复取材的知识点。要真正掌握它，第一步必须把定义背准背透，因为绝大多数考题的失分点恰恰来自对定义细节的模糊理解。
在软考官方教材中，二叉排序树又被称为二叉查找树或二叉搜索树，英文简称BST。它的标准定义是这样表述的：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树。第一，如果它的左子树不空，那么左子树上所有结点的值都小于它的根结点的值。第二，如果它的右子树不空，那么右子树上所有结点的值都大于它的根结点的值。第三，它的左子树和右子树本身也分别是二叉排序树。
这个定义有三层含义需要逐一拆解。第一层是递归性，定义中的第三条要求左右子树自身也必须满足二叉排序树的性质，意味着判定是一个递归过程，不能只看根结点和它的直接孩子，还要看整棵树每一层结点之间的相对大小关系。第二层是全局性，定义强调的是"左子树上所有结点的值都小于根结点的值"，而不是仅要求左孩子小于根。很多考生在判定时只比较每个结点和自己的左右孩子，忽略了跨层比较，结果误判。第三层是空树特例，空树被视为合法的二叉排序树，这在递归判定的边界条件中非常关键。
普通二叉树只规定了结点的度和层次结构，对结点值之间的大小关系没有任何约束。二叉排序树则在结构约束之上，额外增加了一整套关于关键字取值的序关系约束。正是这套序关系约束，使二叉排序树具备了普通二叉树所没有的快速查找能力。理解这层区别，才能理解为什么同样的结点集合，按不同顺序插入会得到形状完全不同的二叉排序树，也才能理解为什么查找效率与树的形态密切相关。
从数据结构本质看，二叉排序树是把"线性有序"与"树形组织"两者结合起来的一种结构。线性表的有序性让查找可以利用比较结果进行二分，但插入删除需要移动大量元素；链表的插入删除方便，但查找只能顺序进行。二叉排序树用树的形态组织数据，让查找、插入、删除三种操作都能沿着一条从根到叶的路径完成，平均情况下三种操作的时间复杂度都能达到对数级别。这正是它被设计出来的根本目的，也是它区别于普通二叉树的核心价值。
二叉排序树有一条几乎年年被考的黄金性质：对一棵二叉排序树进行中序遍历，得到的结点序列一定按关键字递增有序排列。这条性质是定义的自然推论，理解它需要回到中序遍历本身的访问顺序。中序遍历的规则是"左子树、根结点、右子树"，由于二叉排序树规定左子树所有结点都小于根、右子树所有结点都大于根，那么按左、根、右的顺序访问，天然就得到从小到大的有序序列。
这条有序性性质在考试中有三个应用方向。第一是正用，即给定一棵二叉排序树，要求写出它的中序遍历序列，正确答案一定是递增序列，可用来快速验证遍历结果。第二是反用，即给定一个递增序列和它对应的某种遍历序列，判断该遍历是什么遍历。第三是判定，即判断一棵二叉树是否是二叉排序树，最简洁的方法就是看它的中序遍历序列是否递增有序。
这里需要特别提醒，中序遍历有序是二叉排序树的充要条件，二者可以互相推出。也就是说，一棵二叉树是二叉排序树，当且仅当它的中序遍历序列严格递增。如果允许重复关键字，那么中序序列就是非递减的。命题人经常利用"严格递增"与"非递减"的细微差别设置陷阱，考生需根据题目是否允许重复来具体判断。
理解定义之后，就要深入三大核心操作，也就是查找、插入和删除。它们的底层机制是上午选择题的常考内容，也是理解后续平衡二叉树、红黑树等高级结构的基础。只背结论而不理解机制，遇到变形计算题就会手足无措。
二叉排序树的查找，本质上是一个不断缩小搜索范围的过程。查找从根结点开始，将待查关键字与当前结点关键字比较。若相等则查找成功；若小于则转入左子树继续查找；若大于则转入右子树继续查找。如此反复，直到找到目标结点，或沿路径到达空指针位置，此时查找失败。
查找的时间复杂度取决于树的高度，也就是从根到叶的最长路径长度。在理想情况下，若树接近平衡，高度约为以2为底n的对数，查找的平均时间复杂度就是对数级别。但在最坏情况下，若结点按严格递增或严格递减顺序插入，二叉排序树会退化成一棵单支树，也就是一条链表，此时高度为n，查找退化为顺序查找，时间复杂度退化为线性级别。这个退化现象是二叉排序树最根本的缺陷，也是命题人最爱考查的考点之一。
查找过程中还有一个易被忽视的细节：查找失败时经过的路径终点位置，恰恰就是将来插入该关键字时应该放置的位置。查找失败位置与插入位置的这种对应关系，是插入操作的理论基础，命题人有时会围绕这一点设置考题。
二叉排序树的插入操作有一个鲜明特点，就是新结点总是作为叶子结点插入。插入的执行过程是：先按查找的方法，从根结点开始寻找待插入关键字的位置。若发现树中已存在相同关键字，则插入失败，因为二叉排序树通常不允许重复关键字；若查找走到了空指针，就在该位置生成一个新的叶子结点，放入关键字。
这里有一个重要结论需要牢记：插入永远不会改变树中已有结点之间的父子关系，新结点只作为某个已有结点的孩子出现。这使得插入的结构破坏最小，只需修改一个空指针的指向即可完成，时间复杂度仍与查找相同，取决于树的高度。
插入顺序对树的形态有决定性影响。同样是关键字集合{50,30,70,20,40,60,80}，若按50、30、70、20、40、60、80的顺序插入，会得到一棵较平衡的树；若按20、30、40、50、60、70、80的顺序插入，则会得到一棵完全向右倾斜的单支树。这个例子生动说明二叉排序树的形态完全由插入序列决定，也是引入平衡二叉树进行自平衡调整的动机所在。
删除是三大操作中最复杂的，也是命题的重灾区。删除一个结点需分三种情形处理。第一种是删除叶子结点，最简单，直接把父结点中指向它的指针置空。第二种是删除只有一个孩子的结点，让这个唯一孩子直接替代它的位置。第三种是删除有两个孩子的结点，最复杂，不能简单用某个孩子替代，需要采用特殊策略。
对于有两个孩子的结点，删除的标准策略是找一个"替身"来替换被删结点。替身有两种选择：一种是被删结点的中序前驱，即左子树中关键字最大的结点；另一种是中序后继，即右子树中关键字最小的结点。找到替身后，把替身的关键字复制到被删结点位置，再删除替身结点本身。由于替身结点要么是叶子、要么只有一个孩子（中序前驱位于左子树最右下方，没有右孩子；中序后继位于右子树最左下方，没有左孩子），所以删除替身就回到了前两种简单情形。
中序前驱和中序后继的概念是理解删除的关键，也是命题人反复考查的点。中序前驱就是结点在中序序列中的前一个结点，由于中序有序，它正好是比该结点小的所有结点中最大的那个；中序后继则是比该结点大的所有结点中最小的那个。理解这个有序背景，就能明白为什么中序前驱一定是左子树的最右下结点、中序后继一定是右子树的最左下结点。两种替身策略都能保持二叉排序树性质不变，考试中两种都可能出现，考生必须都掌握。
二叉排序树在应用中暴露出的退化问题，催生了一系列改进的变体结构。理解这些变体，既有助于应对软考中关于平衡二叉树、红黑树、B树的相关考题，也能帮助考生建立整个查找结构演进的知识脉络。
为克服退化成链表的缺陷，人们提出了平衡二叉树，最具代表性的就是AVL树。AVL树是一种特殊的二叉排序树，在满足二叉排序树全部性质的基础上，额外增加约束：任意结点的左右子树高度之差的绝对值不超过1。这个高度差被称为平衡因子，AVL树要求所有结点的平衡因子只能是负1、0或正1。
AVL树通过旋转操作维持平衡。当插入或删除破坏某结点的平衡时，需进行左旋、右旋或由它们组合而成的双旋来恢复。旋转的本质是在不改变中序遍历序列的前提下，调整局部结点的父子关系，因此旋转不会破坏二叉排序树的有序性质。AVL树保证树高始终维持在O(log n)级别，从而保证三种操作的对数级复杂度。软考对AVL树的考查集中在平衡因子计算、旋转类型判断及旋转后形态变化。
AVL树虽保证严格平衡，但每次插入删除都可能触发多次旋转，工程实践中开销较大。红黑树放宽了平衡条件，通过给结点着色并维护五条红黑性质，保证树高最多不超过最优平衡的两倍，在维护开销和查找效率之间取得更好折中。红黑
本篇完！