RED-BLACK TREE

balanced binary search tree

特長

各ノードに赤/黒のカラーが必要です

挿入された新しいノードは常に赤です

Root Property:root nodeはblack

外部属性:リーフ(NULL)ノードが黒

内部プロパティ:赤いノードのすべてのサブノードが黒

Depth Property:各ノードからleafへのパスの黒いノード数は常に同じでなければなりません
[red nodeのhight<=logN]

デュアルレッドソリューション<挿入>

G(할아버지노드) P(부모노드) U(삼촌노드) M(내 노드)

Restructuring ( U is black)

1.私(M)と両親(P)、おじいさん(G)は昇順で並んでいます

2.中間価格を必ず親にし、残りの2人を子供にしなければならない.

3.上昇した中間値を黒にし、この2人の子供を赤にします.
[原句]おじさん(U)の子供がいたら、貼ってあげます.

Recoloring (U is Red)

1.現在ノード(M)を挿入している親(P)とおじさん(U)は黒,おじいさんノード(G)は赤である.

2.おじいさん(G)がRootノードでなければ、DoubleRedは再び発生する可能性があります