binary-tree - 排序二叉搜索树

Question

当尝试将一组数字排序到二叉搜索树中时，是否总是有一种方法可以对它们进行排序，从而使树的高度最短，换句话说，效率最高？

Answer 1

通过将一个元素作为树的根并在其周围排列所有其他数字，可以将一组数字转换为 BST。我可以看到以下与该理论相矛盾的情况：

选择一个根会导致一棵高度树，h左子树比右子树“高”。选择另一个根会导致不同的树，也有 height h，右子树比左子树“高”。

另一个简单的例子涉及交换两个不直接相关的连续元素的插入顺序，因此不会影响彼此在树中的位置。

通过反例来反驳。

让集S = {0, 1, 2, 3}。按以下顺序将元素插入二叉搜索树：1, 0, 2, 3

  1
 / \
0   2
     \
      3

按以下顺序将元素插入二叉搜索树：1, 2, 0, 3

  1
 / \
0   2
     \
      3

因为这两个树的插入顺序不同，但都具有最小高度，所以只有一个插入顺序提供最小高度的二叉搜索树的说法是错误的。

如果您关心的是树上元素的实际顺序，请按以下顺序插入集合的元素：2, 1, 0, 3

    2
   / \
  1   3
 /
0

同样，这棵树与前面的树具有相同的高度，因此表明树中项目的不同排序也可以产生最小高度的树。

---

（旁白）

您始终可以通过首先对集合的元素进行排序来构建最小高度树，然后不断细分已排序的集合以确保平衡和完全填充每一行。

• 取集合的中值元素。在偶数个元素的情况下，取两个“中间”元素中较大的一个。这将成为树的根。
• 取中位数以下的所有元素。这将成为根的左子树。
• 取中位数以上的所有元素。这将成为根的右子树。
• 从这些集合中递归地创建左右子树。

这应该确保你有一个完整的二叉树，它总是最小的高度。