アルゴリズム導論第13章赤黒樹
2552 ワード
一、概念
1.定義と性質
(1)定義
赤黒樹の意味:(a)各結点を満たすか、赤いか、黒い(b)根の結点が黒い(c)各葉の結点(NIL)が黒い(d)1つの結点が赤い場合、その2人の息子が黒い(e)対の各結点であり、その結点からその子孫の結点までのすべての経路に同じ数の黒の結点を含む二叉検索樹を赤黒樹と呼ぶ.
黒の高さ定義:あるノードxから(ノードを含まない)1つのリーフノードに到達する任意の経路上の黒のノードの個数をxの黒の高さと呼ぶ.
(2)性質
赤と黒のツリーは、他のパスより2倍長いパスがないことを確認します.
n個の内結点を有する赤黒樹の高さは2 lg(n+1)までである.
2.構造
(1)赤黒樹の結点構造
3.赤と黒の木での操作
SEARCH
PREDECESSOR
MINIMUM
MAXIMUM
INSERT
DELETE
二、コード
ヘッダファイル
製品コード
テストコード
コードの説明:
1.NULLの代わりにNILをリーフノードとして使用すると、特殊な処理が少なくなります
2.ノードを削除し、deleteをremoveに変更します.キーワードとの衝突を避ける一方で、removeの意味が合っていると思います.
3.insertとremoveはnode*zの代わりにint keyをパラメータとして使うので、使いやすいと思います
三、練習
13.1赤黒樹の性質
13.1-1
黒の高さとは、ルートノードからリーフノードへの経路上の黒のノードの個数を指し、黒の高さを計算する場合、出発するノードは計算されず、リーフノードとはnilノードを指す
13.1-2
いいえ、性質に違反しているからです.
いいえ、性質に違反しているからです.
13.1-3
はい
13.1-4
http://zh.clrs-ans.wikia.com/index.php?title=13.1_%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E6%80%A7%E8%B4%A8&variant=zh-cn
葉の深さが黒の高さ
13.1~5 bh(x)は黒高さであり、rh(x)は赤高さと定義され、RBツリーの性質rh(x)<=bh(x)に基づいているが、各経路のbh(x)は等と考えられ、最長可能経路bh(x)+rh(x)、最短可能経路bh(x)であるため、最長は最短の2倍以上である.
13.1-6
最大:2^(2 k+1)-1
高少:2^(k)-1
13.1-7
比は最大2:1、奇数層のノードは赤、偶数層のノードは黒です.nは奇数である.
比の最小値は0で、すべてのノードが黒です.
13.2回転
13.3挿入
13.3-1
1階がいいですね
13.3-2以上のプログラムを実行すると結果が得られる
13.3-6
アルゴリズムの導論を参照-13.3-6
挿入する要素はzです.挿入されたプロシージャには、ルートノードからzへのパスが記録され、スタックで格納されます.では、zの親ノードはスタックトップ要素であり、zの祖父ノードはスタックの次トップ要素である.
アップ反復の過程で同時にスタックを出て、スタックを出る時間を制御して、正しくRB-INSERTを実現することができます
13.4削除
四、思考問題
13-1動的永続集合
アルゴリズム導論-13-1-持続動的集合を参照
13-2赤黒ツリーでの接続操作
アルゴリズム導論-13-2-赤黒樹上の接続操作を参照
1.定義と性質
(1)定義
赤黒樹の意味:(a)各結点を満たすか、赤いか、黒い(b)根の結点が黒い(c)各葉の結点(NIL)が黒い(d)1つの結点が赤い場合、その2人の息子が黒い(e)対の各結点であり、その結点からその子孫の結点までのすべての経路に同じ数の黒の結点を含む二叉検索樹を赤黒樹と呼ぶ.
黒の高さ定義:あるノードxから(ノードを含まない)1つのリーフノードに到達する任意の経路上の黒のノードの個数をxの黒の高さと呼ぶ.
(2)性質
赤と黒のツリーは、他のパスより2倍長いパスがないことを確認します.
n個の内結点を有する赤黒樹の高さは2 lg(n+1)までである.
2.構造
(1)赤黒樹の結点構造
struct node
{
node *left;
node *right;
node *p;
int key;
bool color;
};struct Red_Black_Tree
{
node *root;//
node *nil;//
};3.赤と黒の木での操作
SEARCH
PREDECESSOR
MINIMUM
MAXIMUM
INSERT
DELETE
二、コード
ヘッダファイル
製品コード
テストコード
コードの説明:
1.NULLの代わりにNILをリーフノードとして使用すると、特殊な処理が少なくなります
2.ノードを削除し、deleteをremoveに変更します.キーワードとの衝突を避ける一方で、removeの意味が合っていると思います.
3.insertとremoveはnode*zの代わりにint keyをパラメータとして使うので、使いやすいと思います
三、練習
13.1赤黒樹の性質
13.1-1
黒の高さとは、ルートノードからリーフノードへの経路上の黒のノードの個数を指し、黒の高さを計算する場合、出発するノードは計算されず、リーフノードとはnilノードを指す
13.1-2
いいえ、性質に違反しているからです.
いいえ、性質に違反しているからです.
13.1-3
はい
13.1-4
http://zh.clrs-ans.wikia.com/index.php?title=13.1_%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E6%80%A7%E8%B4%A8&variant=zh-cn
葉の深さが黒の高さ
13.1~5 bh(x)は黒高さであり、rh(x)は赤高さと定義され、RBツリーの性質rh(x)<=bh(x)に基づいているが、各経路のbh(x)は等と考えられ、最長可能経路bh(x)+rh(x)、最短可能経路bh(x)であるため、最長は最短の2倍以上である.
13.1-6
最大:2^(2 k+1)-1
高少:2^(k)-1
13.1-7
比は最大2:1、奇数層のノードは赤、偶数層のノードは黒です.nは奇数である.
比の最小値は0で、すべてのノードが黒です.
13.2回転
13.2-1，
RIGHT-ROTATE
1 y 13.3挿入
13.3-1
1階がいいですね
5 。 5， ， RB-INSERT 4 2 ， 。 （ RB-INSERT-FIXUP ： z ， 。 ： z ， z ， z ）， z ， z 。z ，（4:2）， z ， ， 5。13.3-2以上のプログラムを実行すると結果が得られる
13.3-6
アルゴリズムの導論を参照-13.3-6
挿入する要素はzです.挿入されたプロシージャには、ルートノードからzへのパスが記録され、スタックで格納されます.では、zの親ノードはスタックトップ要素であり、zの祖父ノードはスタックの次トップ要素である.
アップ反復の過程で同時にスタックを出て、スタックを出る時間を制御して、正しくRB-INSERTを実現することができます
13.4削除
13.4-3
13.4-4
（1） ， （ ）， ， nil
（2）x w ， w ， w
13.4-7
。
（1） ，
（2） ， 四、思考問題
13-1動的永続集合
アルゴリズム導論-13-1-持続動的集合を参照
13-2赤黒ツリーでの接続操作
アルゴリズム導論-13-2-赤黒樹上の接続操作を参照