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