构建一颗平衡二叉搜索树

Question

有一种方法可以构建平衡的二叉搜索树吗？

例如：

1 2 3 4 5 6 7 8 9

       5
      / \
     3   etc
    / \
   2   4
  /
 1

我认为有一种方法可以实现这一点，而不使用更复杂的自平衡树。否则我可以自己做，但可能已经有人做过了 :)

---

谢谢答复！这是最终的Python代码：

def _buildTree(self, keys):
    if not keys:
        return None

    middle = len(keys) // 2

    return Node(
        key=keys[middle],
        left=self._buildTree(keys[:middle]),
        right=self._buildTree(keys[middle + 1:])
        )

- Znarkus

Answer 1

对于每个子树：

• 找到子树的中间元素，并将其置于树的顶部。
• 找到中间元素之前的所有元素，并使用此算法递归地得到左子树。
• 找到中间元素之后的所有元素，并使用此算法递归地得到右子树。

如果您首先对元素进行排序（如示例中所示），则可以在常数时间内找到子树的中间元素。

这是一种构建一次性平衡树的简单算法。它不是自平衡树的算法。

以下是一些C＃源代码，您可以尝试自己使用：

public class Program
{
    class TreeNode
    {
        public int Value;
        public TreeNode Left;
        public TreeNode Right;
    }

    TreeNode constructBalancedTree(List<int> values, int min, int max)
    {
        if (min == max)
            return null;

        int median = min + (max - min) / 2;
        return new TreeNode
        {
            Value = values[median],
            Left = constructBalancedTree(values, min, median),
            Right = constructBalancedTree(values, median + 1, max)
        };
    }

    TreeNode constructBalancedTree(IEnumerable<int> values)
    {
        return constructBalancedTree(
            values.OrderBy(x => x).ToList(), 0, values.Count());
    }

    void Run()
    {
        TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1, 9));
        // displayTree(balancedTree); // TODO: implement this!
    }

    static void Main(string[] args)
    {
        new Program().Run();
    }
}

- Mark Byers

Answer 2

本文详细解释了以下内容：

树的重新平衡：最优时间和空间复杂度
http://www.eecs.umich.edu/~qstout/abs/CACM86.html

此外，还有：

一次性二叉搜索树平衡：Day/Stout/Warren (DSW)算法
http://penguin.ewu.edu/~trolfe/DSWpaper/

如果您想实时进行操作，您需要使用自平衡树。

如果您只想构建一个简单的树，而不必去平衡它，只需在将元素插入树之前随机排列它们即可。

- Robert Harvey

Answer 3

将您的数据中位数（或更准确地说，数组中最接近中位数的元素）作为树的根。然后递归执行此操作。

- user97370

---

中位数并不是很恰当的术语。首先，中位数在原始数据中可能不存在。例如，3和4的中位数是3.5。请参见http://en.wikipedia.org/wiki/Median。 - Mark Byers

你是对的。显然（从你参考的维基百科页面上看），这个词是medoid。我已经进行了编辑。 - user97370