黒の高さが k の赤黒ツリーの内部ノードの最小数は 2 k -1 で、次の図の 1 つです。
黒の高さが k の内部ノードの最大数は 2 2k -1 で、黒の高さが 2 の場合、2 4 - 1 = 15になるはずです。ただし、次の画像を検討してください。
内部ノードの数は 7 です。何が間違っていますか?
黒の高さが k の赤黒ツリーの内部ノードの最小数は 2 k -1 で、次の図の 1 つです。
黒の高さが k の内部ノードの最大数は 2 2k -1 で、黒の高さが 2 の場合、2 4 - 1 = 15になるはずです。ただし、次の画像を検討してください。
内部ノードの数は 7 です。何が間違っていますか?
問題は、黒の高さを誤解していることです。赤黒ツリーのノードの黒の高さは、現在のノードから現在のノードを数えないリーフまでの黒のノードの数です。(これはすべてのルートで同じ値になります)。したがって、すべての赤いノードに 2 つの黒い葉を追加するだけで、黒の高さが 2 で内部ノードが 15 の赤黒ツリーが得られます。
(また、赤黒ツリーでは、すべての赤のノードに 2 つの黒の子があるため、赤のノードは葉にはなりません。)
上記の説明を読んだ後、赤の属性を持つルートを追加すると、追加する 2 番目のノードは再び赤になり、赤の違反になります。ノードの再構築後、再びルートが黒で子が赤になると仮定します。(2^2k)-1 の最大内部ノードを取得できない可能性があります。ここで何かが足りないのですか?つい最近rbtに取り組み始めました...
ここに示すツリーには、実際には 15 個の内部ノードがあります。最後のレイヤーの赤のノードの NIL 黒の子が欠落しており、実際には外部ノード (キーのないノード) と呼ばれます。ツリーのブラックハイトは 2 です。ブラックハイト k のツリーの内部ノードの最大数の実際の式は 4^(k)-1 です。この場合、15 であることがわかります。
赤黒の木では、外部ノード[ヌルノード]は常に黒ですが、2番目のツリーの質問では外部ノードについて言及していないため、カウントを7として取得していますが、外部ノード[ヌルノード]について言及し、内部ノードを数えてみると、15 であることがわかります。
「黒い葉」(黒いノード)を考慮していないようです-最後のレベルの赤いノードごとに2つのNILノード。NIL ノードを葉と見なすと、最後のレベルの赤のノードは合計 15 の内部ノードとしてカウントされます。