扫码获取 VIP 码
添加管理员微信获取 VIP 码
在软考中级软件设计师和数据库系统工程师的选择题里，有一个考点几乎每年都会以不同面目出现，那就是二叉排序树。它还有一个更为人熟知的名字，叫做二叉查找树，英文缩写为 BST，全称是 Binary Search Tree。不少考生在复习时把它和普通的二叉树、完全二叉树、哈夫曼树混在一起背，结果一做题就错。要真正拿下这个考点，第一步必须把它的定义吃透，一个字都不能含糊。
二叉排序树首先是一棵二叉树，它满足二叉树的全部结构约束：每个结点至多有两棵子树，分别称为左子树和右子树，且子树有明确的左右之分，不能随意调换。但仅仅是一棵二叉树还不够，二叉排序树在此基础上叠加了一条排序性质的约束。这条约束可以表述为：对于树中任意一个结点，若它的左子树不为空，则左子树上所有结点的关键字值均小于该结点的关键字值；若它的右子树不为空，则右子树上所有结点的关键字值均大于该结点的关键字值。这条性质不是只对根结点成立，而是对树中每一个结点都成立，换句话说，二叉排序树的左子树和右子树本身也各自是一棵二叉排序树，这是一种递归定义。
这里有两个非常关键的细节，很多考生会在这里丢分。第一，教材中标准术语用的是"小于"和"大于"，这意味着在严格定义的二叉排序树中通常不允许出现两个关键字相同的结点。第二，排序性质约束的是"子树整体"而非"直接孩子结点"。很多初学者错误地认为只要左孩子小、右孩子大就是二叉排序树，这是片面的，正确的判据是左子树上所有结点都小于该结点。例如根结点五十、左孩子三十、左孩子的右孩子六十，六十虽然大于三十，却位于根结点左子树中且大于五十，破坏了整体约束，因此这棵树不是二叉排序树。判断时必须看整棵子树，而非只看父子两代。
在数据结构学科的知识体系中，二叉排序树属于"动态查找表"的范畴。所谓动态查找表，是指在查找过程中允许进行插入和删除操作的查找结构。与之相对的静态查找表，比如顺序表上的折半查找，其结构在查找过程中是固定不变的。二叉排序树之所以被归为动态查找表，正是因为它天然地支持在查找的过程中同步完成插入和删除，而插入和删除之后，整棵树仍然保持二叉排序树的性质不变。这个"动态"属性，是理解二叉排序树全部后续内容的一把钥匙。
从考试的角度看，考生需要记住二叉排序树的几个等价称呼：二叉排序树、二叉查找树、二叉搜索树、BST，这四个词指向的是同一个数据结构，在真题中会轮换出现，切勿因为换了名字就认不出来。同时要能准确复述它的递归定义，并能够判断一棵给定的树是否满足排序性质。这是后续所有原理机制、算法分析和真题解题的基础。
二叉排序树最核心的操作是查找。查找的原理极其简洁：从根结点开始，将待查找的关键字与当前结点的关键字进行比较，如果相等，则查找成功；如果待查找的关键字小于当前结点的关键字，则转入左子树继续查找；如果大于，则转入右子树继续查找。如果沿着这条路径一直走到某个空子树的位置仍未找到，则判定查找失败。这个过程每比较一次，就把待查找的范围缩小到当前子树的一半左右，因此查找路径的长度，决定了查找的效率。
这条查找路径的本质，是二叉排序树对关键字集合进行了一种隐式的有序化。因为中序遍历的顺序是"左子树、根结点、右子树"，而二叉排序树恰好满足"左子树全小、根居中、右子树全大"，两者叠加，就必然推出中序遍历结果有序。反过来，对一棵二叉树做中序遍历若得到递增序列，则它一定是二叉排序树，这提供了判断二叉排序树的快速方法。
查找效率的高低，直接取决于树的高度。在最好的情况下，也就是树是一棵接近满二叉树的平衡形态时，树的高度约为以二为底结点数的对数，此时查找的平均比较次数与对数成正比，效率很高。但在最坏的情况下，也就是插入的关键字本身已经有序时，二叉排序树会退化成一棵"单链"，每个结点都只有左孩子或者只有右孩子，此时树的高度等于结点数，查找退化成顺序查找，效率急剧下降。这个退化问题，是二叉排序树最根本的缺陷，也是后续引出平衡二叉树、红黑树等变体的直接动因。
插入操作是理解动态查找表的钥匙。二叉排序树的插入，本质上就是一个"查找失败的位置"就是"新结点该挂接的位置"的过程。具体做法是：先以待插入的关键字执行一次查找，由于新关键字在树中尚不存在，这次查找必然以失败告终，而失败时所停下的那个空位置，就是新结点应当插入的位置。然后把新结点作为叶子结点挂接到这个空位置即可。整个插入过程不需要移动任何已有的结点，这是二叉排序树相对于顺序表插入的巨大优势。
值得强调的是，二叉排序树的插入一定是插到叶子结点上，绝不会插到内部结点的位置。因为插入算法的本质是顺着查找路径向下走，走到空指针处停下，新结点就诞生在那里，而空指针只可能出现在叶子结点的下一层。这一点在判断题和选择题中经常作为陷阱出现。例如真题中问"向二叉排序树中插入一个结点，可能改变树的什么"，正确答案应当围绕"新增结点一定是叶子结点、不改变其他结点的相对位置"来展开。
插入的比较次数等于新结点最终所处的深度加一，因此插入效率与查找效率一致，都取决于树高。这解释了为什么随机插入时平均性能令人满意，而顺序插入时会退化到不可接受的程度。
删除操作是二叉排序树三个基本操作中最复杂的一个，也是软考命题人最喜欢出难题的地方。删除一个结点，需要根据被删结点的孩子情况，分三种情形分别处理。
第一种情形，被删结点是叶子结点。此时处理最简单，直接删除该结点，并将其父结点中指向它的指针置为空即可，不影响整棵树的排序性质。
第二种情形，被删结点只有一个孩子。此时需要让被删结点的唯一孩子顶替它的位置，也就是把父结点中指向被删结点的指针，改为直接指向这个唯一的孩子。因为整棵子树内部的有序性没有被破坏，唯一孩子顶替后，排序性质依然保持。
第三种情形，被删结点有两个孩子，这是最麻烦的情况。此时不能简单地删除该结点，因为两个子树都需要重新挂接。标准的处理方法是"替代法"：先在被删结点的右子树中找出关键字最小的结点，也就是右子树中最靠左的那个结点，用它的关键字替换被删结点的关键字，然后再去删除那个最靠左的结点。由于右子树中最靠左的结点最多只有一个右孩子，甚至往往是叶子结点，所以这个删除最终会归结为第一种或第二种情形，问题便迎刃而解。对称地，也可以在被删结点的左子树中找关键字最大的结点来替代，两种做法都是正确的。
这个删除算法正确性的根源在于：右子树中的最小结点一定大于左子树所有结点，又小于右子树中除它以外的所有结点，用它顶替后恰好能保持"左小右大"的整体有序性。理解这一点比记住操作步骤重要得多，软考选择题常把删除操作的正确性作为辨析点。
要准确理解二叉排序树的应用边界，必须先厘清查找表的两大分类。静态查找表的典型代表是顺序表加折半查找，它要求数据事先有序且连续存储，查找效率高，但插入和删除需要移动大量元素，代价高昂。动态查找表的典型代表正是二叉排序树，它牺牲了部分查找的极致性能，换来了插入删除的灵活性。在数据频繁变动、同时需要频繁查找的场景下，二叉排序树优于顺序表；而在数据几乎不变、以查找为主的场景下，顺序表加折半查找往往更简单高效。
软考真题中反复出现的"折半查找要求顺序存储且有序排列"正是静态查找表的约束体现，而二叉排序树依靠指针组织结点、天然支持链式存储，对存储结构没有顺序要求。抓住"静态与动态""顺序存储与链式存储"这两条主线，就能把查找这一章的零散考点串成体系。
二叉排序树的致命弱点在于形态退化。当关键字以有序序列依次插入时，比如依次插入一、二、三、四、五，得到的二叉排序树会完全退化为一条右斜的单链，树高等于结点数，查找、插入、删除的时间复杂度全部退化为线性级别。这是二叉排序树在理论上的最坏情况，也是它无法单独胜任大规模数据索引任务的根本原因。
针对这个缺陷，计算机科学家们提出了多种平衡化改造方案，这些方案构成了二叉排序树家族的演进谱系。平衡二叉树，也就是 AVL 树，通过引入平衡因子，保证任意结点的左右子树高度差不超过一，从而把树高严格控制在以二为底结点数的对数级别，彻底避免了退化。红黑树则通过颜色属性和一套复杂的旋转与变色规则，在更宽松的平衡条件下获得近似的性能，同时降低了频繁调整的开销，被广泛用于各种
本篇完！