ノードが145個ある赤色の黒いツリーで可能な最低限と最大数の赤いノードは何ですか？

赤黒木さらに4つの規則

によって制約される二分探索木の各ノードは、赤または黒のいずれかである
ルートはすべて赤色のノードが0又は2のいずれかを有していなければならない
黒であります黒人の子供たち
はnullをパスへのすべてのルートは、黒のノード

最小数と同じ数を持っている必要があります赤いノードの赤いノードを持つように強制する必要はありません。

各パスで赤と黒のノードをインターリーブし、実際の赤い葉の数をできるだけ多くすると、最大の赤いノードの数が得られます。この場合、各赤いノードには2つの子黒ノードがあり、ルートノードは黒でなければなりません。したがって=> n_black = 2 * n_red + 1 我々はまた、あなたがさらに支援が必要な場合はここで

は、いくつかのリンクですn_black + n_red = n（nはノードの私達の合計数である）ことを知っている：https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap13b.pdf

出典

2016-10-02 22:22:09 splay

、http://doctrina.org/maximum-height-of-red-black-tree.htmlを根は黒く、いいえ？それが赤だった場合、赤いノードはゼロにできませんでした。 – rici

根は黒ですはい – splay

ok、私はそれを修正しました。 – rici

ノードが145個ある赤色の黒いツリーで可能な最低限と最大数の赤いノードは何ですか？

答えて

関連する問題