二叉排序树，又称二叉查找树、二叉搜索树，英文缩写为BST，是软件设计师考试数据结构部分几乎年年出现的核心考点。它本质上是一棵二叉树，却又不是一棵普通的二叉树，而是在二叉树的形态之上叠加了一条严格的结点大小排序规则，这条规则正是二叉排序树区别于其他一切二叉树的灵魂所在。要真正理解二叉排序树，必须先回到教材给出的正式定义，再沿着这条定义推演它全部的性质与运算，而不是死记硬背几个结论。
教材对二叉排序树给出的标准定义是：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树。其一，若左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值。其二，若右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值。其三，左右子树本身也分别是二叉排序树。这条定义采用了递归的表述方式，第三条性质尤为关键，它说明二叉排序树的性质并非只作用于根结点这一层，而是向下递归地贯穿整棵树的每一个结点，每一个结点都满足左小右大的排序约束。
这里必须强调"所有"二字的分量。左子树上"所有"结点的值都小于根，右子树上"所有"结点的值都大于根，而不是仅要求左孩子小于根、右孩子大于根。这是极易混淆的细节，也是命题人最爱设的陷阱之一。一棵树若仅满足左孩子小于双亲、右孩子大于双亲，却存在左子树中某结点的值大于根的情况，仍不能称为二叉排序树。判断是否为二叉排序树，必须对每个结点验证其左右子树全体结点值的范围，而不是只盯着直接孩子。
普通二叉树只规定了一棵树的形状约束，即每个结点至多有两个孩子，除此之外对结点中存放的键值没有任何顺序上的要求，键值可以任意摆放。二叉排序树则在此基础上追加了键值的排序约束，使得整棵树内部的键值呈现出一种可以预测、可以利用的规律性。正是这种规律性，赋予了二叉排序树支持高效查找、高效插入、高效删除的能力，也让中序遍历这一操作对它产生了特殊的含义。可以说，普通二叉树关注的是"形"，而二叉排序树关注的是"序"，形序兼备之后，查找操作才能从无序的逐个比较变为有序的逐步逼近。
引入二叉排序树的动机源自查找效率的追求。顺序存储的线性表查找需逐个比较，平均比较约一半元素；即便有序线性表能用折半查找降到对数级别，其插入删除仍需移动大量元素，维护成本高昂。二叉排序树在链式存储上实现了有序性，查找时借助左小右大的性质逐步缩小范围，达到对数级复杂度，插入删除又只需调整少数指针，是在查找效率与动态维护成本之间取得平衡的经典结构。
查找是二叉排序树最核心、最基础的运算，插入和删除都建立在对查找路径的依赖之上。理解二叉排序树的查找机制，也就理解了它作为查找结构存在的全部价值。查找的底层逻辑并不复杂，可以概括为一句朴素的原则：从根结点出发，将待查关键字与当前结点比较，若相等则查找成功，若小于则进入左子树继续找，若大于则进入右子树继续找，直到找到目标结点或者遇到空子树而查找失败。
假设存在一棵已经构造好的二叉排序树，现在要查找关键字为某个特定值的结点。查找从根结点开始，把待查值与根结点的值作比较。如果两者相等，说明目标就是根结点，查找立即成功结束。如果待查值小于根结点的值，那么根据二叉排序树左小右大的性质，目标结点只可能存在于左子树之中，于是把搜索范围缩小到左子树，把左子树的根结点当作新的当前结点重复比较。反之，如果待查值大于根结点的值，则把搜索范围缩小到右子树。这个过程每向下走一层，就把待搜索的范围近乎减半，比较次数最多不超过树的高度。
查找失败同样有明确判定：当查找一路向下最终指向空子树，即走到某结点的空孩子位置上仍未找到目标值时，即可断定该关键字不在树中。这个"空子树"正是后续插入新结点的落点，插入的本质就是先执行一次失败的查找，再把新结点安放在失败位置上。
二叉排序树查找的时间复杂度与树的高度直接相关。在理想情况下，树是平衡的，左右子树高度大致相当，树的高度约为以二为底结点个数的对数，此时查找的时间复杂度为对数级别，效率与折半查找相当。但在最坏情况下，如果结点按照有序序列依次插入，树会退化成一棵单链形态，所有结点都只有左孩子或者都只有右孩子，树的高度退化为结点个数，查找的时间复杂度也随之退化为线性级别。因此，二叉排序树的查找效率并不稳定，它的性能下限取决于树的形态是否平衡，这正是后续引出平衡二叉树这一概念的伏笔。
插入操作是构建一棵二叉排序树的基本手段。二叉排序树通常不是一次性整体生成的，而是一个结点一个结点地插入进来的，每一次插入都必须遵守左小右大的规则，并保证插入之后整棵树仍然是二叉排序树。理解插入规则之后，再理解整棵树的构造过程，就会水到渠成。
插入一个新结点时，首先按照查找的思路，从根结点出发，把新结点的关键字与当前结点比较，若小于则转向左子树，若大于则转向右子树，持续这个过程直到抵达一个空的孩子位置。当某个结点的某个孩子位置为空时，就把新结点安放在这个空位置上，插入完成。这条规则保证了新结点总是作为叶子结点被插入，也就是说，新插入的结点永远不会成为某个已有结点的双亲，它只会占据某个叶子下方原本空缺的位置。这一点是理解二叉排序树构造过程的关键。
一个重要推论是，插入操作绝不改变已有结点的相对父子关系，只是在查找失败的位置上补上一个新叶子，因此代价很低，只需沿一条从根到叶的路径比较并挂上结点，时间复杂度同样由树的高度决定。
二叉排序树的构造，本质是从空树开始，依次将给定关键字序列中的每个元素按插入规则逐一插入。第一个插入的值成为根结点，此后每个值沿根到叶的路径找到落点。需要强调的是，同一组关键字因插入顺序不同，最终得到的树形态、高度都可能不同，查找效率也因此存在差异，这一现象是理解平衡问题的重要入口。
二叉排序树最著名、也最常被考察的性质，就是中序遍历的有序性。对一棵二叉排序树进行中序遍历，得到的结点关键字序列恰好是一个递增的有序序列。这个性质可以从递归定义直接推得：中序遍历的顺序是左子树、根、右子树，而根据二叉排序树的定义，左子树所有值小于根，右子树所有值大于根，因此按照左、根、右的顺序访问，必然先输出较小的值，再输出中间值，最后输出较大的值，层层递归之后，最终输出序列整体呈现递增有序。反过来，如果一棵二叉树的中序遍历结果是有序递增的，那么它一定是一棵二叉排序树。中序遍历有序性既是二叉排序树的判定方法，也是将二叉排序树转化为有序线性序列的便捷手段，是命题人极为偏爱的出题点。
删除是二叉排序树三种基本运算中最复杂的一种，也是考试中分值密度最高、出错率最高的部分。查找和插入的规则相对单一，而删除则必须分情况讨论，因为被删结点在树中所处的位置不同，删除之后维护二叉排序树性质所需的处理方式也不同。总体上，删除操作可以分为三种情形，分别对应被删结点拥有零个、一个和两个孩子的不同场景。
第一种情形是被删结点是叶子结点，也就是既没有左孩子也没有右孩子。此时删除最为简单，只需要把它的双亲结点中指向它的那个指针置为空即可。由于叶子结点不承载任何后代，删除它不会牵动树中其他任何结点，二叉排序树的性质也不会受到任何破坏。这是删除操作中最省事的一种情况。
第二种情形是被删结点只有一个孩子，可能是只有左孩子，也可能是只有右孩子。此时不能简单地把结点摘掉，因为它的孩子还需要继续留在树中。正确的做法是让被删结点的双亲直接接管它的唯一孩子，也就是把双亲中原本指向被删结点的指针，改为直接指向被删结点的那个唯一孩子。这样，被删结点被摘除的同时，它的子树被整体提升上来，填补了空缺。由于被删结点只有一棵子树，提升之后左小右大的性质依然成立，整棵树依旧是一棵合法的二叉排序树。
第三种情形最为复杂，也是考试的绝对重点。当被删结点同时拥有左孩子和右孩子时，不能简单地摘除它，因为两个子树都需要妥善安置，而任何直接提升其中一棵子树的做法，都会破坏二叉排序树的整体有序性。标准的处理思路是"替代法"，即不真正删掉这个结点的存储位置，而是找一个合适的替身结点，用替身结点的值覆盖被删结点的值，然后把删除任务转化为删除那个替身结点。替身结点的选取有两个经典方案，二者效果等价，考生可根据题目要求任选其
本篇完！