1 ～ 15 のキーを扱っているとしましょう。通常の BST の最悪の場合のパフォーマンスを得るには、次のように昇順または降順でキーを挿入します。
1、2、3、4、5、6、7、8、9、10、11、12、13、14、15
次に、BST は本質的にリンクされたリストになります。
BST の最良のケースでは、次の順序でキーを挿入します。次に挿入されるキーが挿入される全範囲の半分になるように配置されているため、最初は 15/2 = 8、次に 8 になります。 /2 = 4 など...
8、4、12、2、6、10、14、1、3、5、7、9、11、13、15
その場合、BST は最適な高さ 3 のバランスの取れたツリーになります。
赤黒木の最良のケースは、BST の最良のケースでも構築できます。しかし、赤黒い木の最悪のケースをどのように構築すればよいのでしょうか? BSTの最悪のケースと同じですか？最悪のケースをもたらす特定のパターンはありますか?