Stl

赤黒木（C ++コードの実装+原則の紹介）



Red Black Tree



赤黒木

説明

この記事では、「アルゴリズムの概要>>赤黒木とMIT OCWコース6.046J」の第13章に従って、赤黒木の教育内容にC ++言語を使用しています（Neteaseオープンクラスには中国語の翻訳があります）このレッスンのバージョン）。本の赤黒木データ構造が実装されています。個人的な学習メモの記録です。コードに加えて、赤と黒の木の原理の解釈の他の部分はかなり荒く、学習のための参照値はあまりありません。黒い木を深く研究する必要がある学生は、他の資料を参照することができます。コード全体は記事の最後に添付されており、コアコードは約（270行以上）です。

赤黒木が満たす必要のある5つの特性
  1. すべてのポイントは赤/黒です
  2. ルートノードは黒です
  3. すべての葉のノードは黒です
  4. 赤いノードの場合、その息子ノードはすべて黒です
  5. 各ノードxについて、xノードからすべての葉の下のxまでの単純なパス上の黒いノードの数は同じです（数はノードの黒い高さであり、次のように記録されます）b h（x）bh（x））。
補題13.1

1つは持っていますn n内部ノードの赤黒木の高さは最大で2 l g（n + 1）2lg（n + 1）。



証明：

ルートノードx x、持ってるn≥（2 bh（x）− 1）+（2 bh（x）− 1）+1n≥（2 ^ {bh（x）} -1）+（2 ^ {bh（x）} -1） +1
n≥2bh（x）−1n≥2 ^ {bh（x）}-1
2×bh（x）≥h（x）2 times bh（x）≥h（x）//ルートからリーフノードへの単純なパスが赤と黒であると考えてください
h（x）≤2lg⁡（n + 1）h（x）≤2lg⁡（n + 1）

データ構造の定義

ノード* nilは、黒色の唯一の外部補助リーフノードです。
画像



const static bool RED = 0 const static bool BLACK = 1 struct Node { int val bool color //colour Node *left, *right, *p //Left, right child, parent node Node(const int &v,const bool &c=RED,Node *l=nullptr, Node *r=nullptr, Node *_p = nullptr) :val(v),color(c),left(l),right(r),p(_p){} } struct RBTree { Node *root //root Node *nil //external node, color: black RBTree() { nil = new Node(-1, BLACK, nil, nil, nil) root = nil } }
二分探索木の基本操作

画像
左回転左利き

void left_rotate(Node* x) //Left { Node *y = x->right x->right = y->left if(y->left != nil) { y->left->p = x } y->p = x->p if(x->p == nil) root = y else if(x->p->left == x) x->p->left = y else x->p->right = y x->p = y y->left = x }

右利きの右回転

void right_rotate(Node* x) //right spin { Node *y = x->left x->left = y->right if(y->right != nil) y->right->p = x y->p = x->p if(x->p == nil) root = y else if(x->p->left == x) x->p->left = y else x->p->right = y x->p = y y->right = x }

インサートインサート



Node* insert_bst(Node* &p, Node* &r, const int &v) { if(r == nil) //When the tree is empty { r = new Node(v, RED, nil, nil, p) if( p == nil ) root = r if(v > p->val) p->right = r else p->left = r } else //tree is not empty { if(v < r->val) return insert_bst(r, r->left, v) else return insert_bst(r, r->right, v) } return r }
赤黒木操作

RB-Insert = Insert + Insert Repair for Binary Search Tree（insert_fixup）
画像
画像
画像

void insert(const int &v) { Node* z = insert_bst(nil, root, v) / / The following is insert_fixup, divided into 3x2 = 6 cases, from a symmetrical perspective, there are only three. while(z->p->color==RED) { if(z->p->p->left == z->p) { if(z->p->p->right->color == RED) //A: CASE 1 { z->p->color = BLACK z->p->p->color = RED z->p->p->right->color = BLACK z = z->p->p } else { if(z->p->right == z) //A: CASE 2 { z = z->p left_rotate(z) } //A: CASE 3 z->p->color = BLACK z->p->p->color = RED right_rotate(z->p->p) } } else { if(z->p->p->left->color == RED) //B: CASE 1 { z->p->color = BLACK z->p->p->color = RED z->p->p->left->color = BLACK z = z->p->p } else { if(z->p->left == z) //B: CASE 2 { z = z->p right_rotate(z) } z->p->color = BLACK //B: CASE 3 z->p->p->color = RED left_rotate(z->p->p) } } } root->color = BLACK / / Set the color of the root to BLACK }

RB-削除削除=二分木削除+削除修正（delete_fixup）
二分木を削除するときは、削除したノードの色を記録する必要があります。
二分探索木の削除の4つのケース（教科書の書き方によれば、通常、3つのケースの削除について書く必要があります。）
画像
ヘルパー機能

Node* find_min(Node *r) { Node *p = r while(r!=nil) { p = r r = r->left } return p } void rb_transplant(Node* &u, Node* &v) { if( u->p == nil ) root = v else if( u == u->p->left ) u->p->left = v else u->p ->right = v v->p = u->p }

削除機能
赤黒木削除は4 * 2 = 8件あり、左右対称は4種類あります。
画像

void rb_delete(Node *z) { Node *y = z bool delcol = y->color Node *x = z if(z->left == nil) { x = z->right rb_transplant(z, z->right) } else if(z->right == nil) { x = z->left rb_transplant(z, z->left) } else { y = find_min(z->right) delcol = y->color x = y->right if(y->p == z) { x->p = y } else { rb_transplant(y, y->right) y->right = z->right y->right->p = y } rb_transplant(z, y) y->left = z->left y->left->p = y y->color = z->color } if(delcol == BLACK) rb_delete_fixup(x) }

修理機能

void rb_delete_fixup(Node *x) { while(x != root && x->color == BLACK) { if( x == x->p->left ) { Node *w = x->p->right if( w->color == RED ) //A: CASE 1 { w->color = BLACK x->p->color = RED left_rotate(x->p) w = x->p->right } if(w->left->color == BLACK and w->right->color == BLACK) //A: CASE 2 { w->color = RED x = x->p } else { if(w->right->color == BLACK ) //A: CASE 3 { w->left->color = BLACK w->color = RED right_rotate(w) w = x->p->right } w->color = x->p->color //A: CASE 4 x->p->color = BLACK w->right->color = BLACK left_rotate(x->p) x = root } } else { Node *w = x->p->left if(w->color == RED) //B: CASE 1 { w->color = BLACK x->p->color = RED right_rotate(x->p) w = x->p->left } if(w->right->color==BLACK && w->left->color==RED) //B: CASE 2 { w->color = RED x = x->p } else { if(w->left->color == BLACK) //B: CASE 3 { w->right->color = BLACK w->color = RED left_rotate(w) w = x->p->left } w->color = x->p->color //B: CASE 4 x->p->color = BLACK w->left->color = BLACK right_rotate(x->p) x = root } } } x->color = BLACK }
RB-すべてのコードをツリー化
#include using namespace std const static bool RED = 0 const static bool BLACK = 1 struct Node { int val bool color //colour Node *left, *right, *p //Left, right child, parent node Node(const int &v,const bool &c=RED,Node *l=nullptr, Node *r=nullptr, Node *_p = nullptr):val(v),color(c),left(l),right(r),p(_p){} } struct RBTree { Node *root //root Node *nil //external node, color: black RBTree() { nil = new Node(-1, BLACK, nil, nil, nil) root = nil } void left_rotate(Node* x) //Left { Node *y = x->right x->right = y->left if(y->left != nil) { y->left->p = x } y->p = x->p if(x->p == nil) root = y else if(x->p->left == x) x->p->left = y else x->p->right = y x->p = y y->left = x } void right_rotate(Node* x) //right spin { Node *y = x->left x->left = y->right if(y->right != nil) y->right->p = x y->p = x->p if(x->p == nil) root = y else if(x->p->left == x) x->p->left = y else x->p->right = y x->p = y y->right = x } Node* insert_bst(Node* &p, Node* &r, const int &v) { if(r == nil) //When the tree is empty { r = new Node(v, RED, nil, nil, p) if( p == nil ) root = r if(v > p->val) p->right = r else p->left = r } else //tree is not empty { if(v < r->val) return insert_bst(r, r->left, v) else return insert_bst(r, r->right, v) } return r } void insert(const int &v) { Node* z = insert_bst(nil, root, v) while(z->p->color==RED) { if(z->p->p->left == z->p) { if(z->p->p->right->color == RED) //A: CASE 1 { z->p->color = BLACK z->p->p->color = RED z->p->p->right->color = BLACK z = z->p->p } else { if(z->p->right == z) //A: CASE 2 { z = z->p left_rotate(z) } //A: CASE 3 z->p->color = BLACK z->p->p->color = RED right_rotate(z->p->p) } } else { if(z->p->p->left->color == RED) //B: CASE 1 { z->p->color = BLACK z->p->p->color = RED z->p->p->left->color = BLACK z = z->p->p } else { if(z->p->left == z) //B: CASE 2 { z = z->p right_rotate(z) } z->p->color = BLACK //B: CASE 3 z->p->p->color = RED left_rotate(z->p->p) } } } root->color = BLACK / / Set the color of the root to BLACK } Node* find_min(Node *r) { Node *p = r while(r!=nil) { p = r r = r->left } return p } Node* getNode(Node *r, const int &v) { if(r == nil) return nil if(r->val == v) return r else if( v < r->val ) return getNode(r->left, v) else return getNode(r->right, v) } Node* getNode(const int &v) { return getNode(root, v) } void rb_delete_fixup(Node *x) { while(x != root && x->color == BLACK) { if( x == x->p->left ) { Node *w = x->p->right if( w->color == RED ) //A: CASE 1 { w->color = BLACK x->p->color = RED left_rotate(x->p) w = x->p->right } if(w->left->color == BLACK and w->right->color == BLACK) //A: CASE 2 { w->color = RED x = x->p } else { if(w->right->color == BLACK ) //A: CASE 3 { w->left->color = BLACK w->color = RED right_rotate(w) w = x->p->right } w->color = x->p->color //A: CASE 4 x->p->color = BLACK w->right->color = BLACK left_rotate(x->p) x = root } } else { Node *w = x->p->left if(w->color == RED) //B: CASE 1 { w->color = BLACK x->p->color = RED right_rotate(x->p) w = x->p->left } if(w->right->color==BLACK && w->left->color==RED) //B: CASE 2 { w->color = RED x = x->p } else { if(w->left->color == BLACK) //B: CASE 3 { w->right->color = BLACK w->color = RED left_rotate(w) w = x->p->left } w->color = x->p->color //B: CASE 4 x->p->color = BLACK w->left->color = BLACK right_rotate(x->p) x = root } } } x->color = BLACK } void rb_transplant(Node* &u, Node* &v) { if( u->p == nil ) root = v else if( u == u->p->left ) u->p->left = v else u->p ->right = v v->p = u->p } void rb_delete(Node *z) { Node *y = z bool delcol = y->color Node *x = z if(z->left == nil) { x = z->right rb_transplant(z, z->right) } else if(z->right == nil) { x = z->left rb_transplant(z, z->left) } else { y = find_min(z->right) delcol = y->color x = y->right if(y->p == z) { x->p = y } else { rb_transplant(y, y->right) y->right = z->right y->right->p = y } rb_transplant(z, y) y->left = z->left y->left->p = y y->color = z->color } if(delcol == BLACK) rb_delete_fixup(x) } void rb_delete(const int &v) { Node *z = getNode(root, v) if(z == nil) return rb_delete(z) } void in_order(Node *r) r == nullptr) return in_order(r->left) cout << r->val << ' ' << r->color << endl in_order(r->right) void in_order() { cout << 'in: ' << endl in_order(root) } void pre_order(Node *r) void pre_order() { cout << 'pre:' << endl pre_order(root) } } int main() { freopen('bst.txt','r',stdin) int n cin >> n int v RBTree T for(int i=0i<ni++) { cin >> v T.insert(v) } T.in_order() T.pre_order() //test //for (int i = 0 i { cout << 'delete: ' << 8 << endl T.rb_delete(8) T.in_order() T.pre_order() } return 0 }
入力

8
4 7 6 9 8 1 2 3

運転結果

に：
十一
20
3 0
4 1
6 1
7 0
8 1
9 0
ために：
6 1
20
十一
4 1
3 0
8 1
7 0
9 0
削除：8
に：
十一
20
3 0
4 1
6 1
7 0
9 1
ために：
6 1
20
十一
4 1
3 0
9 1
7 0

参照

[1]。コーメン、トーマスH.、他。アルゴリズム入門、第3版、308〜337。 MIT Press、2009年。