特定のデータセットに対して複数の有効なBSTを持つことは可能ですか？

Question

1から10までの数字のように、バイナリ検索ツリーに一連のデータがあると、複数の平衡バイナリ検索ツリーが存在する可能性はありますか？

または、そのデータセットに固有のバランスBSTが1つだけありますか？

おかげ

Answer 1

それはすべて使用されている特定のバイナリツリーデータ構造、挿入アルゴリズム、バランスの基準と挿入の順序に依存するが、はい - それがために、複数の同等の、有効なバランスの取れた分探索木を持つことが可能です与えられた一連の値。

一方、これが有効なAVL Treeで、数字1~10：

例えば、これは、数字1~10が昇順に挿入された有効Red/Black Treeあります

明らかに、木々がまったく同じではありません - しかし、注文AN：レッド/ブラックツリーと同じ順序で正確に挿入されました両方のバランシングプロパティが保持されます。