algorithm - RB-Tree をリストにできないのはなぜですか?

Question

rb ツリーに問題があります。ウィキペディアによると、rb-tree は次に従う必要があります。

1. ノードは赤または黒のいずれかです。
2. 根元は黒。(この規則はいくつかの定義で使用され、他の定義では使用されません。ルートは常に赤から黒に変更できますが、必ずしもその逆であるとは限らないため、この規則は分析にほとんど影響しません。)
3. 葉はすべて黒い。
4. すべての赤のノードの子は両方とも黒です。
5. 特定のノードからその子孫の葉のいずれかへのすべての単純なパスには、同じ数の黒いノードが含まれます。

ご存知のように、rb-tree はバランスを取る必要があり、高さは O(log(n)) です。しかし、増加する一連の数字 (1、2、3、4、5...) を挿入すると、理論的には、リストのように見え、すべての O(n) の高さを持つツリーが得られます。これは、上記の rb ツリーのプロパティと矛盾しません。それで、どこが間違っていますか??

ありがとう。

Answer 1

記事の少し下に：

挿入は、二分探索木の挿入と同じようにノードを追加し、それを赤に着色することから始まります。

Answer 2

あなたの例はプロパティ番号 5 と矛盾するため、有効な赤黒木ではありません。

私たちが持っているツリーは次のとおりです。

b(1, nil, b(2, nil, b(3, nil, b(4, nil, b(5, nil, nil)))))

したがって、最後の 2 つの葉 ( node の子5) に到達するには、5 つの黒いノード (それぞれ で表されるb) にアクセスする必要があり、ノードの下の葉に到達するには、44 つの黒いノードにアクセスする必要があります。ルートからこの子孫のいくつかへの単純なパスには、異なる数の黒いノードが含まれているため、プロパティ 5 が無効になります。