algorithm - 对于给定的一组数据，是否可以有多个有效的 BST？

Question

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

还是该组数据只有一个独特的平衡 BST？

谢谢

Answer 1

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

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

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

显然，这些树并不完全相同——但排序和平衡属性对两者都适用。