Left-leaning Red-black tree

Bài toán

Cài đặt Left-leaning Red-black tree hỗ trợ các thao tác sau

- Chèn một cặp khoá/giá trị

- Tìm kiếm giá trị của một khoá

Độ phức tạp

- Chèn: O(logn)

- Tìm kiếm: O(logn)

Code này của Nguyễn Tiến Trung Kiên

http://pastebin.com/ec58EM2i

(73 dòng, tương đối ngắn)

Tham khảo

http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

Nhận xét

Đơn giản hơn nhiều so với Red-Black tree

    #include <stdio.h>    #include <iostream>    #include <algorithm>     using namespace std;           struct node *Nil, *Root;           struct node {             int Key, Value;             node *ll, *rr;             bool Red;             node (int AKey, int AValue, bool IsRed)                     { Key=AKey; Value=AValue; Red=IsRed; ll=rr=Nil; }             int get(int AKey) {                     if (Key==AKey || this==Nil) return Value;                     return (AKey<Key ? ll : rr)->get(AKey);             }             void flip_color()                     { Red^=1; ll->Red^=1; rr->Red^=1; }     };           void init(){             Root = Nil = new node(-1, -1, 0);             Nil->ll = Nil->rr = Nil;     }           node* rotate_left(node* x) {             node *y = x->rr;             x->rr=y->ll; y->ll=x;             y->Red=x->Red; x->Red=true;             return y;     }           node* rotate_right(node* x) {             node *y=x->ll;             x->ll=y->rr; y->rr=x;             y->Red=x->Red; x->Red=true;             return y;     }           node* insert(node* x, int Key, int Value) {             if (x==Nil)                     return new node(Key, Value, true);             if (x->ll->Red && x->rr->Red)                     x->flip_color();                         if (Key==x->Key)                     x->Value = Value;             else if (Key < x->Key)                     x->ll = insert(x->ll, Key, Value);             else                     x->rr = insert(x->rr, Key, Value);                                 if (x->rr->Red)                     x=rotate_left(x);             if (x->ll->Red && x->ll->ll->Red)                     x=rotate_right(x);             return x;     }           ostream& operator << (ostream& cout, node* x){             if (x==Nil) return cout;             return cout << "(" << x->ll << x->Key << x->rr << ")";     }           main(){             init();             int x;             while (cin >> x){                     Root = insert(Root, x, 1);                     cout << Root << endl;             }     }