13.3.5 二叉排序树

二叉排序树也叫二叉查找树。它把“比较大小”嵌入到树结构中：左子树关键字小于根，右子树关键字大于根，并且左右子树本身也都是二叉排序树。

定义

对任意节点 x：

位置	关键字关系
左子树所有节点	小于 x
右子树所有节点	大于 x
左、右子树	也分别是二叉排序树

flowchart TD
  R["23"] --> L["17"]
  R --> G["31"]
  L --> L1["11"]
  L --> L2["19"]
  G --> G1["27"]
  G --> G2["40"]

查找过程

查找关键字时，从根开始：

1. 等于根，查找成功。
2. 小于根，进入左子树。
3. 大于根，进入右子树。
4. 走到空位置，查找失败。

这和二分查找思想相似，但树的形态会影响效率。

插入过程

插入新关键字时，也按查找路径往下走，直到遇到空子树，把新节点放在那里。插入顺序不同，形成的树形可能不同。

插入序列特点	形成树形	查找效率
比较均衡	高度接近 ${\log }_{2}n$	较高
已有序输入	可能退化成单支树	最坏 $O(n)$

这就是后续平衡二叉树出现的原因：普通二叉排序树如果不控制高度，可能退化。

中序遍历得到有序序列

二叉排序树最重要性质是：中序遍历得到递增序列。

原因很直接：中序是“左根右”，而二叉排序树满足“左小根中右大”，所以访问顺序天然递增。

遍历	是否保证有序	原因
先序	不保证	根先出现，可能打乱大小顺序
中序	保证递增	左小、根、右大
后序	不保证	根最后出现
层序	通常不能作为排序输出	按层访问，不是按全局大小访问

课程在真题辨析中提醒：不能把“某一路径上关键字有序”当作普遍性质。根到叶子的路径可能先向右再向左，序列未必单调。

技术迭代：为什么需要平衡

结构	优点	缺点	后续改进
顺序表二分查找	查找快	插入删除要移动元素	用树保存动态集合
普通二叉排序树	插入删除较自然，查找可快	形态受插入顺序影响，可能退化	平衡二叉树控制高度
平衡二叉树/红黑树	高度受控，性能稳定	旋转维护复杂	工程中常用于有序集合/映射

二叉排序树不是被“淘汰”，而是作为基础思想被平衡树继承和改进。

本节例题

单选

对二叉排序树进行哪种遍历可以得到递增序列？

A先序遍历B中序遍历C后序遍历D层序遍历

自查清单

1. 能否根据关键字大小画出二叉排序树插入路径？
2. 能否解释为什么中序遍历有序？
3. 能否说明普通二叉排序树为什么可能退化？