二叉搜索树平衡的旋转(在AVL树)

Question

我想知道，最终平衡二叉搜索树是否只有一种可能的结果?有时我得到不同的最终平衡树取决于我旋转的位置

Answer 1

No。有几种自平衡类型的树，最流行的是AVL和红黑。如果你把相同的数据放在这些树中，结果树将是不同的，但平衡。

说到AVL树，我举个简单的例子:

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

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