二叉排序树，又称二叉查找树、二叉搜索树，英文缩写 BST，是软件设计师与数据库系统工程师两门科目共同考查的基础数据结构。它的正式定义可从递归角度给出：二叉排序树要么是空树，要么满足三个条件——若左子树不空，则左子树上所有结点的关键字均小于根结点；若右子树不空，则右子树上所有结点的关键字均大于根结点；左右子树本身也各自构成二叉排序树。
这个定义里最容易被忽略、也最容易被命题人设陷阱的，是"所有结点"这个限定词。它要求的不是"左孩子比根小、右孩子比根大"这种局部关系，而是整棵左子树任意结点的关键字都必须小于根，整棵右子树任意结点的关键字都必须大于根，即全局有序约束。很多考生看到"某结点左孩子小于它、右孩子大于它，就一定是二叉排序树"这样的判断题时会想当然判对，实际是错的，因为它只验证了父子两层。正确做法是遍历验证：以根为界，左子树全落在小于根的开区间，右子树全落在大于根的开区间，且约束递归传递到每一层。
二叉排序树在教材里占据一席之地，在于它把"顺序存储的随机访问"和"链式存储的动态增删"做了折中。数组能随机访问、可二分查找达到对数级，但增删要移动大量元素；链表增删灵活，但查找只能顺序扫描。二叉排序树用链式结构保留增删的低成本，又通过"左小右大"的有序约束让查找沿从根到叶的路径逐步缩小范围，理想情况下把查找、插入、删除都压到对数级。理解这一点，也就理解了它为何和平衡二叉树、红黑树产生关联——因为它本身不保证平衡，退化后对数级性能会跌落回线性级。
二叉排序树的查找是核心，插入和删除都要先调用查找。查找从根结点开始，把待查关键字与当前结点比较，相等则命中；若待查值小于当前结点，则转向左孩子；大于则转向右孩子。如此反复，直到在某结点处相等命中，或指针落到空结点、说明查找失败。这一过程在结构上等价于从根到叶走一条唯一路径，每一层排除一半候选子树，因此查找时间复杂度取决于树的深度而非结点总数。
这里有个关键底层事实：二叉排序树的查找与有序顺序表上的二分查找在决策逻辑上完全同构。二分查找每次取区间中点、据比较结果舍弃一半区间；二叉排序树每次取当前子树根、据比较结果舍弃左或右子树。二者区别仅在于"中点"如何确定——二分查找的中点由下标直接算出、天然均衡；二叉排序树的根是插入时形成的、并不天然居中。正是这一点差别决定了两种结构在不同形态下的性能分叉：形态接近平衡时查找深度约对数级，与二分查找相当；退化成斜树时查找变成一条链、深度线性级，与顺序查找无异。
插入比查找多一个"落点"概念。插入新关键字时，仍从根出发执行与查找相同的比较过程，但这次不要求命中，而是要走到查找失败的终点——那个本该存在却缺失的空位置。这个空位置就是新结点唯一正确的插入位置。为什么唯一？因为有序约束决定了任何关键字在这棵树里都有一个确定的下落区间，从根到叶每一步都被约束收窄，最终只会落到一个确定的空指针上。挂到别处，都会破坏"左小右大"的全局有序性。
这个"唯一落点"机制也解释了重要性质：给定相同插入序列，树形态确定；给定不同插入序列，即使元素集合相同，树形态也可能截然不同。例如依次插入升序序列，每次新元素都比当前所有结点大、都落在最右下空位，整棵树就长成向右倾斜的链，严格满足定义却已丢失对数级性能。这一现象是理解其全部缺点的钥匙，也是 AVL、红黑树等平衡结构出现的直接动因。
删除是三个操作里最复杂的，因为删结点后必须维持整棵树的全局有序，而落点唯一性在删除时并不像插入那样直接。删除按被删结点的孩子数量分三种情况：一是叶子结点，直接删除即可；二是只有一棵子树，用唯一孩子顶替其位置、子树整体上升一层，有序性不受破坏；三是同时拥有左右子树，这才是真正需要动脑的情形——不能直接删掉，否则左右两棵子树会失去连接点。
第三种情况的经典处理有两种、本质等价：用中序前驱顶替，即取左子树里关键字最大的结点复制其值再删除该前驱；或用中序后继顶替，即取右子树里关键字最小的结点复制其值再删除该后继。两者可行，是因为中序前驱与后继分别是"小于被删结点的最大者"和"大于被删结点的最小者"，放到被删结点位置恰好保持左右有序区间不被破坏。理解了中序遍历的排序性质，也就理解了删除第三种情况的道理。
二叉排序树最漂亮的性质，是它的中序遍历结果是一个严格递增的有序序列。中序遍历按"左子树、根、右子树"次序递归访问，由于左子树所有结点都小于根、右子树所有结点都大于根，递归展开后得到的访问顺序天然从小到大排列。反过来也成立：若一棵二叉树的中序遍历结果有序，那么它要么是二叉排序树，要么在结构上与之等价。正因如此，二叉排序树常被用作"动态有序集合"载体，既能像有序表一样快速定位前驱、后继，又能像链表一样高效增删。
中序遍历有序性在考试中的直接价值，体现在一个高频结论上：二叉排序树中关键字最小的结点一定位于整棵树最左下，即从根出发一路向左走到头，其左孩子指针必然为空；最大的结点一定位于最右下，右孩子指针为空。这个结论常被包装成"排序二叉树中最小元素结点的特征是左子树指针为空"这样的选择题，其来源正是中序遍历的递增性——最小元素最先被中序访问，即整棵树最左下的结点。
评价查找效率的核心指标是平均查找长度，即等概率假设下查找成功所需比较次数的期望值。对结点数确定的二叉排序树，它直接由形态决定：深度越小、越接近满二叉树，越接近对数级；深度越大、越接近斜树，越接近线性级。同样一批关键字，插入顺序不同，平均查找长度可相差悬殊。
这一事实把二叉排序树引向最大软肋——形态不可控。它的定义对平衡没有任何约束，插入顺序一旦接近有序，树就迅速恶化成链。为克服这个缺陷，人们引入平衡二叉树：一棵二叉排序树若满足"任意结点左右子树高度差不超过一
本篇完！