最大限にバランスの取れていない赤黒木のファミリーを見つけ、そのファミリーの「それぞれの属性」を証明して、高さが 2log(n+1) に近い赤黒木の無限大ファミリーが存在することを証明する必要があります。
私の推測では、このファミリーは基本的に、srsr ... ノードのある 1 つのパスと、黒いノードで満たされた残りのすべての赤黒いツリーで構成されています。しかし、どうすればこれを証明できますか? そして、そのような家族がどのように見えるかを正式に書き留めるにはどうすればよいでしょうか?
ありがとうございました！
私の推測では、このファミリーは基本的に、srsr ... ノードのある 1 つのパスと、黒いノードで満たされた残りのすべての赤黒いツリーで構成されています。
それは合理的な推測です。
しかし、どうすればこれを証明できますか?
木の無限シーケンス T_0、T_1、T_2、T_3、... を記述します。すべての整数 n に対して、少なくとも n 個のノードを持つシーケンスにツリーが存在します。すべての i に対して、T_i の高さが少なくとも 2log(n_i+1) - C であるような定数 C が存在することを示します。ここで、n_i は T_i のノードの数です。(これは、「近い」というあいまいな用語の 1 つの可能な解釈です。)
そのような家族がどのように見えるかを正式に書き留めるにはどうすればよいですか?
誘導的に。例として真っ黒な木を作ります。ツリー T_0 は空です (基本ケース)。すべての整数 i > 0 に対して、ツリー T_i は、T_{i-1} に等しい左右のサブツリーを持つ黒いノードで構成されます (誘導ステップ)。次に、帰納法を使用してこれらの木に関する事実を証明できます。