binary-search-tree - 通过旋转平衡二叉搜索树（在 AVL 树上）

Question

我想知道，最终平衡的二叉搜索树是否只有一个可能的结果？有时我会得到不同的最终平衡树，具体取决于我在哪里进行旋转。

Answer 1

不，有几种自平衡类型的树，最流行的是 AVL 和 Red-Black。如果您将相同的数据放在这些树中，则生成的树将不同，但平衡。

如果谈到 AVL 树，我将仅举一个简单的例子：

   2     |      4     |      3     
 1   4   |    2   5   |    2   4   
    3 5  |   1 3      |   1     5  

它们都是平衡的 AVL 树，可以通过不同的操作顺序创建。但是如果你用完全相同的数据重复相同的操作顺序，结果树应该是相同的，因为在 AVL 树算法中没有任何概率。