对于给定的数据集,是否可以有多个有效的BST？

Question

给定二叉搜索树中的一组数据,如数字1到10,是否可能存在多个平衡二叉搜索树？

或者,对于那组数据,是否只有一个独特的平衡BST？

谢谢

Answer 1

这一切都取决于所使用的特定二叉树数据结构,插入算法,平衡标准和插入顺序,但是 - 对于给定的值序列,可能有多个等效且有效的平衡BST.

例如,这是一个有效的红/黑树,其中数字1-10按升序插入:

另一方面,这是一个有效的AVL树,其中数字1-10的插入顺序与红/黑树完全相同:

显然,树木并不完全相同 - 但两者的排序和平衡属性都是一致的.