二叉排序树

定义

二叉排序树 (Binary Sort Tree, BST)，又称二叉查找树 (Binary Search Tree)，是一棵具有下列性质的二叉树：

核心特性：对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

查找操作是二叉排序树的基础。从根结点开始，沿着一条路径进行查找。

插入操作是向二叉排序树中添加一个新元素，同时保持其二叉排序树的性质。

插入过程：
1. 从根结点开始，执行与查找类似的过程，为待插入的关键字 key 寻找插入位置。
2. 如果树为空，则新结点作为根结点。
3. 如果树不为空，查找过程必将因遇到空指针而失败。该空指针的位置就是新结点的插入位置。
4. 将新结点作为叶子结点插入。
特点：新插入的结点一定是叶子结点。

构造一棵二叉排序树，就是从一个空树开始，依次将待插入的元素序列中的每个元素通过插入操作加入树中。

构造过程：给定一个关键字序列 (k_1, k_2, ..., k_n)，从一棵空树开始，依次执行 Insert(k_i) 操作，直到所有关键字都插入树中。
重要性质：对于同一个关键字序列，不同的插入顺序可能得到不同形态的二叉排序树。
- 例如，序列 (45, 24, 53, 12, 37, 93) 会生成一棵相对平衡的树。
- 而序列 (12, 24, 37, 45, 53, 93) 会生成一棵单支树（右斜树），查找效率退化为顺序查找。

删除操作是二叉排序树中最复杂的操作，需要根据待删除结点 p 的子树情况分三种情况讨论：

p 是叶子结点：
- 直接删除该结点，并将其父结点的相应指针域置为 NULL。这是最简单的情况。
p 只有左子树或只有右子树：
- 删除结点 p，并将其唯一的子树（左子树或右子树）直接链接到 p 的父结点上，替代 p 的位置。
p 既有左子树又有右子树：
- 这是最复杂的情况。为保持二叉排序树的性质，不能直接删除 p。
- 方法：在 p 的子树中找到一个可以替代 p 的结点，用该替代结点的值覆盖 p 的值，然后删除那个替代结点。
- 替代结点的选择（二选一）：
  - 中序前驱：p 的左子树中值最大的结点。
  - 中序后继：p 的右子树中值最小的结点。
- 以中序后继为例的删除步骤： a. 找到 p 的右子树中最小的结点 s（即从 p 的右孩子出发，一直向左走到尽头）。 b. 将 s 的值赋给 p。 c. 此时问题转化为删除结点 s。由于 s 是其所在子树的最小结点，它最多只有一个右孩子（不可能有左孩子）。因此，删除 s 的问题就转化为了上述情况 1 或 2。

二叉排序树的查找、插入、删除等操作的效率都取决于树的高度（或深度）h。

平均情况：当关键字序列是随机的时，生成的二叉排序树趋向于平衡，其高度 $h \approx lo g_{2} n$ 。此时，各项操作的效率都接近 $O (lo g n)$ 。
最坏情况：当关键字序列本身有序或逆序时，生成的二叉排序树会退化成线性链表（单支树），其高度 $h = n$ 。此时，各项操作的效率退化为 $O (n)$ ，与顺序查找无异。

为了解决最坏情况下的性能问题，引入了平衡二叉树（Balanced Binary Tree），如 AVL 树和红黑树，它们通过在插入和删除后进行调整来确保树的高度始终保持在 $O (lo g n)$ 的量级。

由 n 个互不相同的结点所能构成的二叉排序树的形态个数，是一个与卡特兰数 (Catalan Number) 相关的问题。

推导思路：
1. 设 $h (n)$ 为用 n 个结点可以构造出的不同二叉排序树的个数。
2. 从 n 个结点中（不妨设为 1, 2, …, n）任取一个结点 $i$ 作为根结点。
3. 根据二叉排序树的定义，小于 $i$ 的 $i - 1$ 个结点必须构成左子树，大于 $i$ 的 $n - i$ 个结点必须构成右子树。
4. 左子树有 $h (i - 1)$ 种形态，右子树有 $h (n - i)$ 种形态。根据乘法原理，以 $i$ 为根的二叉排序树有 $h (i - 1) \times h (n - i)$ 种形态。
5. 由于根结点 $i$ 可以是 1, 2, …, n 中的任意一个，根据加法原理，总的形态数是所有情况的总和。
递推公式：

h (n) = i = 1 \sum n h (i - 1) h (n - i)

其中，规定 $h(0) = 1$（表示空树有一种形态）。

$h (n) = C_{n} = \frac{1}{n + 1} (n 2 n) = \frac{( 2 n )!}{( n + 1 )! n !}$