algorithm - 最小化二叉搜索树的高度

Question

如果我试图最小化二叉搜索树的高度，这些是正确的步骤吗？：

1) 从树中生成一个排序数组 2) 通过将排序后的元素按顺序添加到树中来重构树

Answer 1

将已排序的列表添加到简单的非平衡二叉搜索树将为二叉搜索树构建理论上的最坏情况。最低值的节点是根，每个节点都被添加到列表中紧接在它前面的节点的“右侧”，并且您创建一个最大深度的树，在 O(n) 时间内搜索而不是 O(lg n ）。您实际上只是在构建一个过于复杂的链表。

Answer 2

对元素进行排序后，通过将中间元素定义为根节点来重建树，然后分别从中间元素之前和之后的元素递归地构建左子树和右子树。

Answer 3

我认为如果您在尝试通过 插入排序元素之前重建树结构，那么inorder您提供的解决方案将是正确的。

1. 重建树。就像一堆。
2. 通过 inorder 插入已排序的元素

例如，如果原始树是这样的：

                 (5)
           (3)         (6)
      (2)      (4)
  (1)

1. 像这样重建树：

              ()
       ()            ()
   ()      ()   ()
   

2. inorder通过1、2、3、4、5、6插入已排序的元素

               (4)
        (2)             (6)
   (1)      (3)    (5)
   

Answer 4

我想您可以访问树并且可以“手动”更改它。我认为您的平衡问题可以这样解决（伪代码）：

depth(node)
{
    if node is null, return 0;
    l = depth(left child);
    r = depth(right child);
    diff = (r - l);
    if (diff < -1) rotate right (as often as you need);
    else if (diff > 1) rotate left (as often as you need);
    return the new maximum depth of both subtrees +1;
}

我必须承认，我对此不太确定，但想法是您不需要临时数组，因为遍历树并应用正确的旋转应该可以。