二元搜索树通过旋转平衡（在AVL树上）

Question

我在想，最后的平衡二叉搜索树只有一个可能的结果吗？有时候我会根据旋转的位置得到不同的最终平衡树。

Answer 1

没有。有几种自平衡类型的树木，最受欢迎的是AVL和红黑。如果您将相同的数据放入这些树中，则生成的树会有所不同，但均衡。

如果谈到AVL树，我只是给简单的例子：

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

他们都是平衡的AVL树，可以通过操作不同的顺序创建。 但是，如果您重复相同数据的操作顺序，生成的树应该相同，因为AVL树算法中没有任何概率。