3.2.11

上次更新:2019-06-29
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

树的高度为树中深度最大的点的深度。
因此 N 个结点最多只能构造出高度为 N-1 的树来,并不能构成高度为 N 的树。

如果将题目变为用 N 个结点构造高度为 N-1 的二叉搜索树。
这样的树即为二叉搜索树的最坏情况,除唯一的叶子结点之外,每个结点有且只有一个子树。
于是除根结点外,每个结点都有两种选择,要么在左,要么在右。
因此共有 $ 2 ^ {n - 1} $ 种形状。

接下来证明,对于某一种确定的最坏情况,在 N 个元素各不相同的情况下,输入顺序是唯一的。
证明:
就 1 2 3 这三个元素而言,构造这样一棵树:

  2
1   3

可以有 2 1 3 和 2 3 1 两种序列,因为在插入 2 之后可以选择的位置有两个
但最坏情况下的二叉搜索树不存在具有两个子结点的结点,因此输入顺序是唯一的。

反证:
也可以这样考虑,假设序列 A 可以构造出一棵最坏情况下的二叉树,插入顺序为 $ x_1 \dots x_n $
假设存在与 A 顺序不同的序列 B,它构造出的二叉树与 A 的相同。
由于 A 和 B 的元素相同,因此 A 必然可以通过有限次元素交换得到 B。
根据最坏情况下的二叉搜索树的性质,A 中的元素 $ x_n $ 必然满足 $ x_1 \dots x_{n - 1} $ 的所有关系。
例如,假设 $ x_1 > x_2 $, 则 $ x_3 $ 也必然满足 $ x_1 > x_3 $,即后面的元素必然满足前面元素的关系。
于是 A 存在关系序列 $ r_1 \dots r_{n - 1} $,只有满足这样序列的输入才能构造出对应的二叉树。
(可以将 $ r $ 理解为大于号或者小于号,由于元素各不相同,因此不存在等号)
显然 A 中的任意两个元素交换会导致至少一个 $ r $ 倒置,除非进行逆向交换,否则这种倒置不可能消除。
(大于号和小于号是不满足交换律的)
因此 A 和 B 必定相同,得证。

于是每一种最坏情况下的形状都唯一对应一种输入序列,共有 $ 2 ^ {n - 1} $ 种构造方式。

上一题 下一题