[メモ]赤と黒のツリーの挿入と削除
5880 ワード
今日は赤と黒の木を見て、ポイントは赤と黒の木の挿入と削除です
赤と黒のツリープロパティ1)ノードが赤または黒
2)ルートノードが黒
3)すべてのリーフノード(NILノード)が黒
4)ノードが赤である場合、そのサブノードは必ず黒である
5)いずれかのノードからそのリーフノードへのすべての単純パスパケットは同じ数の黒いノードを含む
ルートからリーフノードの最短パスの場合、すべてのノードが赤ルートからリーフノードの最長パスの場合、1つの赤ノードの黒いノード間隔パスの1つのノードには、key、left、right、color、parent赤黒樹の性質:ルートからノード点までの最長の可能経路が最短の可能経路の2倍以下1本のn個の内ノードの赤黒樹の高さは2 lg(n+1)までであるため、複雑度は2 lg(n+1)AVL樹が赤黒樹より厳しく、すべての左右サブ樹の高さの差は1を超えてはならず、そのクエリ複雑度は赤黒樹より低くなる.
赤黒樹の左回り、右回りleft-Rotate(T,x)は、xとxの右の子を「軸」とし、xを元のx右の子の左の子に変える
right-Rotate(T,x)はxとxの左の子を軸にxを元のxの左の子の右の子に変える
疑似コード:
スピンコードは左スピンと似ています
赤と黒のツリーの挿入操作
ノードを挿入するには、2つのステップに分けて、1)挿入点を探して、赤いノードを挿入して、2)赤と黒の木を調整して、赤と黒の木の特性に合致させます
手順1:挿入点を探し、ノードを挿入
手順2:赤と黒のツリーを調整し、主に上の偽コードのrb_を完成するtree_Fixup(T,N)
挿入した各ノードを赤に設定します(黒に設定すると、赤と黒のツリーの黒の高さが変化し、より多くの回転操作が発生します).
挿入する赤いノードをx、その親ノードをp、その親ノードの兄弟ノード、すなわち叔父ノードをs、祖父ノードをg、
0)ノードxがルートノードであれば赤を黒に変更するだけで停止
ルートノードでない場合:
0)親ノードpが黒の場合、条件を満たし、調整せず、停止する
親ノードpが赤色である場合、「連続する赤色ノードが現れない」という性質を満たさず、さらに調整する必要がある(3つの場合)
1)叔父ノードsも赤色であれば、親ノードpと叔父ノードsの色を直接調整して赤から黒に、祖父ノードgを黒から赤に変更することができる(祖父ノードは必然的に黒であり、親ノードが赤であるため!)、色を直接変換した後、xを祖父ノードgに遡り、祖父ノードgをxに設定し、これから最初の調整(ループが必要)を続けます(さっき祖父ノードが赤くなったので、赤黒木の性質に違反する可能性があります)
(G点からの調整を継続)
2)叔父ノードsが黒であれば,以下の2つのケースに分けられる.
2 A)ノードxが親ノードsの右子である場合、left-rotate(T,p)を親ノードpを軸として左旋回し、x,p,gの3つのノードを1本の線上(これはcase 2 B)に配置し、case 2 A)の問題をcase 2 Bに変換する必要があり、case 2 Bの調整を継続する必要がある)
(case 2 Bに変換)
2 B)ノードxが親ノードsの左の子である場合、通俗的に「ノードx,p,gが一線上にある」と言うのであれば先に変色し、親ノードと祖父ノードを変色してから右回転right-Rotate(T,G)を行い、祖父ノードGを軸として右回転することで、赤黒木の性質を完全に満たすことができるので、case 2 Bについては変換が完了した後、調整を終了することができる
(まず変色し、親ノードpが黒になり、祖父ノードgが赤になり、その後右回りになり、調整完了)
もちろんこれは,親ノードが祖父ノードの左サブツリーである場合,親ノードが祖父ノードの右サブツリーである場合に類似した処理である.
赤と黒のツリーの削除操作
削除操作も2つのステップに分かれています.1)ノードを削除します.2)赤と黒のツリーを調整します(挿入操作の調整に対して少し複雑です)
ステップ1,ノードを削除し,後続ノードを見つけ,以下のような状況に分ける.
Case 1)削除するノードが1つしかない場合、またはノードがない場合(nilリーフノードを除く)、削除するノードを一意のサブノードに置き換えます(削除ノードが左の子供の場合、その子供ノードは親ノードの左のサブツリーに掛けられ、右の子供も同じです.
Case 2)削除するノードに2つの子ノードがある場合,このノードを直接削除することはできない.右のサブツリーの「最左下」ノードを探し、Nに設定する必要があります.(このノードには右の子供が1人しかいないか、子供がいないと推定できますが、なぜですか.子供が2人いると、このノードが最左下のノードではない可能性がありますので)、削除するノードをこのNで置き換える必要があります.(注意は置き換えであり、削除ではなく、元の削除するノードの色を残す)、後は「実際には」その後継の最左下ノードNを削除し、同時にこのノードNを赤黒樹調整する(右の子供が1人しかいないか、子供がいないため、上記のcase 1の場合に対応する)
ぎじふごう
ステップ2では、「実際に削除」するノードについて、黒であれば調整する必要があります.黒が削除されたため、このノードの下のサブツリーの黒の高さは1減少し、赤と黒のツリーの任意のパスの黒の高さが一致する特性を満たしません.
削除ノードが赤であれば、赤と黒の木全体の性質に影響を与えないので、何の調整もしなくてもいいです.
削除ノードが黒である場合は、上記の理由により、赤黒ツリーの各パスの黒の高さが一致するように調整する必要があり、4つの状況に分けて分析する必要があります.
次に我々の議論は,削除されたノードが黒であることに基づいて,後で補完するノードをN,Nの親ノードをP,兄弟ノードをSとする.
0)補ったノードN(元削除ノードの子ノード)が赤であれば、そのまま赤を黒にすればよい
1)Nが黒であれば(元に削除されたノードと後に付けられた子ノードが黒である)、この1本に黒のノードが1つ少なくなり、調整が必要となる
以下の議論は、補完された息子ノードが黒であることに基づいている.
Case 1 A)ノードNの兄弟ノードSが赤色であれば、まず親ノードを黒から赤に変える(元のノードは黒に違いない.右の子は赤だから!)、兄弟ノードSは赤から黒に変わり、兄弟ノードSと親ノードPを軸として左回転操作left_rotate(T,P)は、親ノードPを軸として左回りを行い、これにより赤兄弟ノードSの左(黒)の子供がノードNの兄弟ノードとなり、ノードNの兄弟ノードが赤のSから黒のSノードの左の子供になる(これにより後の1 B,1 C,1 Dにいくつかのcaseがある)
(親ノードと兄弟ノードを先に変色してから左回転しcase 1 B,1 C,1 Dに向ける)
Case 1 B)ノードNの兄弟ノードSが黒であり、ノードSの右の子が黒であり、Sの左の子も黒である
***)同時にSの親ノードPが黒であれば、直接Sを赤にすればよい.これにより、兄弟の1本の黒の高さが1減少し、検査ノードNを親ノードPに移動してバランス調整を継続する必要がある
***)同時にSの親ノードPを赤にすると、Sを赤にし、親ノードPを黒にすると、Nという黒の高さに1が加算され、赤と黒の特性が満たされ、バランス調整が不要となり、停止する
(親ノードが黒の場合、兄弟ノードSのみとなり、さらに調整)
(親ノードが赤の場合、Sが赤、Pが黒になると、調整を続ける必要はありません.親ノードは左の子ツリーの黒の高さを増やし、赤と黒の性質を満たし、停止するためです)
Case 1 C)ノードNの兄弟ノードSが黒であり、Sの右の子が黒であるが、Sの左の子が赤である場合.
このように変色が必要となり、Sの左の子を赤から黒に、Sを黒から赤に、そしてSの左の子とSを右旋回right-rotate(T,S)してSを軸として、後のcase 1 Dになるように右旋回し、すなわちNの兄弟ノードSを黒に、Sの右の子を赤にする場合、Case 1 Dの処理を継続する
(変色、そして右回り、Case 1 Dになった場合)
Case 1 D)ノードNの兄弟ノードSが黒であり、Sの右の子が赤であれば、左の子が黒であれ赤であれ;
親ノードPを黒に変更し、黒の兄弟ノードを元の親ノードの色(元の親ノードの色であることに注意)に変更し、Sの赤の右の子を黒に変更し、親ノードPと兄弟ノードSを左に回転操作する必要があります.ここで元の親ノードは黒に変更され、削除された黒のノードの黒の高さを「埋める」ことになります.同時に右の木も元の黒の高さを保っているので、これ以上調整する必要はありません.
(兄弟ノードSが元の親ノードPの色になることに注意し、黒でも赤でも変色し、左旋回した後、調整を停止することができます.遠い親ノードが黒くなるため、黒いノードを削除してカットした黒の高さを埋めています)
削除ノードが右サブツリーの場合は、相対的に変換するだけです.
参照先:
これはとても良い赤と黒の木の講義です.
http://wenku.baidu.com/view/673d3e6eb84ae45c3b358c29.html?from=rec&pos=2&weight=28&lastweight=18&count=5
赤と黒のツリープロパティ1)ノードが赤または黒
2)ルートノードが黒
3)すべてのリーフノード(NILノード)が黒
4)ノードが赤である場合、そのサブノードは必ず黒である
5)いずれかのノードからそのリーフノードへのすべての単純パスパケットは同じ数の黒いノードを含む
ルートからリーフノードの最短パスの場合、すべてのノードが赤ルートからリーフノードの最長パスの場合、1つの赤ノードの黒いノード間隔パスの1つのノードには、key、left、right、color、parent赤黒樹の性質:ルートからノード点までの最長の可能経路が最短の可能経路の2倍以下1本のn個の内ノードの赤黒樹の高さは2 lg(n+1)までであるため、複雑度は2 lg(n+1)AVL樹が赤黒樹より厳しく、すべての左右サブ樹の高さの差は1を超えてはならず、そのクエリ複雑度は赤黒樹より低くなる.
赤黒樹の左回り、右回りleft-Rotate(T,x)は、xとxの右の子を「軸」とし、xを元のx右の子の左の子に変える
right-Rotate(T,x)はxとxの左の子を軸にxを元のxの左の子の右の子に変える
疑似コード:
Left-Rotate(T,x)
{
y = x -> right; //
x->right = y -> left;//
if( y->left )
y->left->parent = x; // ，
y->parent = x->parent; // y x
if (x -> parent == nil)
root[T] = y; // x
else{
if (x == x->parent->left) //y x
x->parent->left = y;
else
x->parent->right = y;
}
y->left = x; // x y
x->parent = y; // x
}スピンコードは左スピンと似ています
赤と黒のツリーの挿入操作
ノードを挿入するには、2つのステップに分けて、1)挿入点を探して、赤いノードを挿入して、2)赤と黒の木を調整して、赤と黒の木の特性に合致させます
手順1:挿入点を探し、ノードを挿入
rb_tree_insert(T,N)
{
y = nil[T]; //
x=root[T];
while(x != nil[T])
{
y = x;
if(key(N) < key(x))
x = x->left;
else
x = x->right;
}
// y
if(y == nil[T]) //y ，
{ root[T] = N; color[N] = BLACK; // }
else{
if (key(N) < key(y))
y->left = N;
else
y->right = N;
N->left = N->right = nil[T]; //
color[N]=RED; //
if (color[y] == RED) // ， Fixup ， ，
{ rb_tree_insert_Fixup(T,N); }
}
}手順2:赤と黒のツリーを調整し、主に上の偽コードのrb_を完成するtree_Fixup(T,N)
挿入した各ノードを赤に設定します(黒に設定すると、赤と黒のツリーの黒の高さが変化し、より多くの回転操作が発生します).
挿入する赤いノードをx、その親ノードをp、その親ノードの兄弟ノード、すなわち叔父ノードをs、祖父ノードをg、
0)ノードxがルートノードであれば赤を黒に変更するだけで停止
ルートノードでない場合:
0)親ノードpが黒の場合、条件を満たし、調整せず、停止する
親ノードpが赤色である場合、「連続する赤色ノードが現れない」という性質を満たさず、さらに調整する必要がある(3つの場合)
1)叔父ノードsも赤色であれば、親ノードpと叔父ノードsの色を直接調整して赤から黒に、祖父ノードgを黒から赤に変更することができる(祖父ノードは必然的に黒であり、親ノードが赤であるため!)、色を直接変換した後、xを祖父ノードgに遡り、祖父ノードgをxに設定し、これから最初の調整(ループが必要)を続けます(さっき祖父ノードが赤くなったので、赤黒木の性質に違反する可能性があります)
(G点からの調整を継続)
2)叔父ノードsが黒であれば,以下の2つのケースに分けられる.
2 A)ノードxが親ノードsの右子である場合、left-rotate(T,p)を親ノードpを軸として左旋回し、x,p,gの3つのノードを1本の線上(これはcase 2 B)に配置し、case 2 A)の問題をcase 2 Bに変換する必要があり、case 2 Bの調整を継続する必要がある)
(case 2 Bに変換)
2 B)ノードxが親ノードsの左の子である場合、通俗的に「ノードx,p,gが一線上にある」と言うのであれば先に変色し、親ノードと祖父ノードを変色してから右回転right-Rotate(T,G)を行い、祖父ノードGを軸として右回転することで、赤黒木の性質を完全に満たすことができるので、case 2 Bについては変換が完了した後、調整を終了することができる
(まず変色し、親ノードpが黒になり、祖父ノードgが赤になり、その後右回りになり、調整完了)
もちろんこれは,親ノードが祖父ノードの左サブツリーである場合,親ノードが祖父ノードの右サブツリーである場合に類似した処理である.
赤と黒のツリーの削除操作
削除操作も2つのステップに分かれています.1)ノードを削除します.2)赤と黒のツリーを調整します(挿入操作の調整に対して少し複雑です)
ステップ1,ノードを削除し,後続ノードを見つけ,以下のような状況に分ける.
Case 1)削除するノードが1つしかない場合、またはノードがない場合(nilリーフノードを除く)、削除するノードを一意のサブノードに置き換えます(削除ノードが左の子供の場合、その子供ノードは親ノードの左のサブツリーに掛けられ、右の子供も同じです.
Case 2)削除するノードに2つの子ノードがある場合,このノードを直接削除することはできない.右のサブツリーの「最左下」ノードを探し、Nに設定する必要があります.(このノードには右の子供が1人しかいないか、子供がいないと推定できますが、なぜですか.子供が2人いると、このノードが最左下のノードではない可能性がありますので)、削除するノードをこのNで置き換える必要があります.(注意は置き換えであり、削除ではなく、元の削除するノードの色を残す)、後は「実際には」その後継の最左下ノードNを削除し、同時にこのノードNを赤黒樹調整する(右の子供が1人しかいないか、子供がいないため、上記のcase 1の場合に対応する)
ぎじふごう
rb_tree_delete(T,z)
{
// y
if (z -> left == nil || z -> right == nil)
y = z;
else
y = tree_Successor(T,z); // x ， x ” “
if( y->left != nil)
x = y->left; //x " "
else
x = y->right; // y->left y->right ， y
if( x != nil)
x -> parent = y->parent;
if (y->parent == nil) //
root[T] = x;
else{
if (y == y->parent->left) //
y->parent->left = x;
else
y->parent->right=x;
}
//
if (y != z)
{
copy(y,z); //copy y z， z
}
if (y -> color == BLACK) // ” “ ， balance ，
rb_tree_delete_Fixup(T, y);
return y;
}
ステップ2では、「実際に削除」するノードについて、黒であれば調整する必要があります.黒が削除されたため、このノードの下のサブツリーの黒の高さは1減少し、赤と黒のツリーの任意のパスの黒の高さが一致する特性を満たしません.
削除ノードが赤であれば、赤と黒の木全体の性質に影響を与えないので、何の調整もしなくてもいいです.
削除ノードが黒である場合は、上記の理由により、赤黒ツリーの各パスの黒の高さが一致するように調整する必要があり、4つの状況に分けて分析する必要があります.
次に我々の議論は,削除されたノードが黒であることに基づいて,後で補完するノードをN,Nの親ノードをP,兄弟ノードをSとする.
0)補ったノードN(元削除ノードの子ノード)が赤であれば、そのまま赤を黒にすればよい
1)Nが黒であれば(元に削除されたノードと後に付けられた子ノードが黒である)、この1本に黒のノードが1つ少なくなり、調整が必要となる
以下の議論は、補完された息子ノードが黒であることに基づいている.
Case 1 A)ノードNの兄弟ノードSが赤色であれば、まず親ノードを黒から赤に変える(元のノードは黒に違いない.右の子は赤だから!)、兄弟ノードSは赤から黒に変わり、兄弟ノードSと親ノードPを軸として左回転操作left_rotate(T,P)は、親ノードPを軸として左回りを行い、これにより赤兄弟ノードSの左(黒)の子供がノードNの兄弟ノードとなり、ノードNの兄弟ノードが赤のSから黒のSノードの左の子供になる(これにより後の1 B,1 C,1 Dにいくつかのcaseがある)
(親ノードと兄弟ノードを先に変色してから左回転しcase 1 B,1 C,1 Dに向ける)
Case 1 B)ノードNの兄弟ノードSが黒であり、ノードSの右の子が黒であり、Sの左の子も黒である
***)同時にSの親ノードPが黒であれば、直接Sを赤にすればよい.これにより、兄弟の1本の黒の高さが1減少し、検査ノードNを親ノードPに移動してバランス調整を継続する必要がある
***)同時にSの親ノードPを赤にすると、Sを赤にし、親ノードPを黒にすると、Nという黒の高さに1が加算され、赤と黒の特性が満たされ、バランス調整が不要となり、停止する
(親ノードが黒の場合、兄弟ノードSのみとなり、さらに調整)
(親ノードが赤の場合、Sが赤、Pが黒になると、調整を続ける必要はありません.親ノードは左の子ツリーの黒の高さを増やし、赤と黒の性質を満たし、停止するためです)
Case 1 C)ノードNの兄弟ノードSが黒であり、Sの右の子が黒であるが、Sの左の子が赤である場合.
このように変色が必要となり、Sの左の子を赤から黒に、Sを黒から赤に、そしてSの左の子とSを右旋回right-rotate(T,S)してSを軸として、後のcase 1 Dになるように右旋回し、すなわちNの兄弟ノードSを黒に、Sの右の子を赤にする場合、Case 1 Dの処理を継続する
(変色、そして右回り、Case 1 Dになった場合)
Case 1 D)ノードNの兄弟ノードSが黒であり、Sの右の子が赤であれば、左の子が黒であれ赤であれ;
親ノードPを黒に変更し、黒の兄弟ノードを元の親ノードの色(元の親ノードの色であることに注意)に変更し、Sの赤の右の子を黒に変更し、親ノードPと兄弟ノードSを左に回転操作する必要があります.ここで元の親ノードは黒に変更され、削除された黒のノードの黒の高さを「埋める」ことになります.同時に右の木も元の黒の高さを保っているので、これ以上調整する必要はありません.
(兄弟ノードSが元の親ノードPの色になることに注意し、黒でも赤でも変色し、左旋回した後、調整を停止することができます.遠い親ノードが黒くなるため、黒いノードを削除してカットした黒の高さを埋めています)
削除ノードが右サブツリーの場合は、相対的に変換するだけです.
参照先:
これはとても良い赤と黒の木の講義です.
http://wenku.baidu.com/view/673d3e6eb84ae45c3b358c29.html?from=rec&pos=2&weight=28&lastweight=18&count=5