Red Black tree

transcript

Binární stromy __&7y, +#Q&DMX! ,a0MNZ0C0Wgn, _gOMS@^#00MQQm jNN,BMQAQ0QKAM6 400N0#DQ#M00AQMg 400&@Q#000&&#00&o (0Wp0M#QFWD00M#0p0v +?m4Q#00MK00M&B0BB#M6, ,0#k0DAWW@&L0QQ"MmJW&#& }Z#BNN0&QD0ZFMK#&A1d$,' #B00GMQD#Mjk#P#Q#Fhb$Wb .dWKqD#M0W5SK&1$_0Q&*Q0#, +pK00K0N&eQQNMN&~EBmHRQ&#A, _q#pMM&0N00#NN0M&b0mq#"~Mgmy^ ~5,jg&ND"aD0Q04WbAWN*#0Ngx*Gc `p&jBmM0$~DH0DA,0QCA0&hJb0KQ#N6 90O$^0"NpNN0N#N0#N7M&B0X~b0MN&EK ]N#u#MS#0#$Hg#WM#0NKMNQl0&0&_VQQM# _*#?#MN0Ne#MNN##DKBM#Q0QQN%AL###~\r #A#4$Xp#&g0pNqLj0q#0MNN#BC=$l(O#pMQ ``~#'#0mg&2#&F*S9BMg)fR&pag"#y3M5"* &!~0' RDXEyT##9#&""#\2~`~ " ~0B#Q0, ` +9[7*?

Miroslav Hrúz, hruzm1[at]fel.cvut.cz, 25.11.2005

Typy BVS

● Výškově(hloubkově) vyvážený BVS (self-balaced binary search tree)– AA tree, AVL tree– red-black tree, splay tree– B-tree, scapegoat tree

● “treap” (zkratka pro tree heap)● dancing tree (opak self-balanced)

Red-black tree

1. Uzel: černý nebo červený

2. Kořen: černý, 3. všechny listy: černé

4. Oba potomci červeného jsou černí

5. Všechny cesty od uzlu do listů obsahují stejný počet černých prvků

Red-black treeProč?● Speciální případ hloubkově vyváženého stromu● Nejdelší cesta max. 2x delší než nejkratší● D(n) O(log(n)), n..počet elementů● I(n) O(log(n))● S(n) O(log(n))Využití:● Implementace asociativních polí, setů● Perzistence dat, vyvážen z definice

Patero příkázání

1. Uzel: černý nebo červený2. Kořen: černý.3. všechny listy: černé4. Oba potomci červeného jsou černí5. Všechny cesty od uzlu do jeho listů obsahují

stejný počet černých prvků

Insert

InsertKomplikace:● Vlastnost 3 platí vždy● Vlastnost 4 je narušena pouze:

– Přidáním červeného prvku– Přebarvením černého na červený– rotací

● Vlastnost 5 je naručena:– Přidáním černého prvku– Přebarvením červeného na černý– rotací

Insert

node grandparent(node n) { //predek predka

return n->parent->parent;

node uncle(node n) { //bratr predka

if (n->parent == grandparent(n)->left)

return grandparent(n)->right;

return grandparent(n)->left;

Insert (1.případ)

Předek neexistuje: přidáme do stromu element a obarvýme ho načerno

void insert_case1(node n) {

if (n->parent == NULL)

n->color = BLACK;

insert_case2(n);

Insert (2.případ)

Předek● černý (4, 5 platí)● Červený (4 platí, 5 neplatí)

if (n->parent->color == BLACK)

return; /* porad plati */

insert_case3(n);

Insert (3.případ)

if (uncle(n) != NULL && uncle(n)->color == RED) {

n->parent->color = BLACK;

uncle(n)->color = BLACK;

grandparent(n)->color = RED;

insert_case1(grandparent(n));

insert_case4(n);

Insert (4.případ)

● Pro zbývající případy: P je nalevo od G● P červený, U černý● N bude pravý potomek P● levá rotace N k P● Zatím není r-bt

Insert (4.případ)

if (n == n->parent->right && n->parent == grandparent(n)->left) {

rotate_left(n->parent);

n = n->left;

} else if (n == n->parent->left && n->parent == grandparent(n)->right) {

rotate_right(n->parent);

n = n->right;

insert_case5(n);

Insert (5.případ)

● P je červený, U je černý● N je levý potomek P● P je levý potomek G...

Insert (5.případ)

● Pravá rotace P k G● Výměna barev P a Gvoid insert_case5(node n) {

grandparent(n)->color = RED;

if (n == n->parent->left && n->parent == grandparent(n)->left) {

rotate_right(grandparent(n));

} else {

/* Here, n == n->parent->right && n->parent == grandparent(n)->right */

rotate_left(grandparent(n));

Delete[:dylít:]

Delete

● Normální BVT● Mažeme node, který má oba potomky, najdeme

max z L podstromu, min z P podstromu

N nová pozice elemS (sibling) bratr NP rodic NSl, Sr – potomci S

Delete

node sibling(node n) {

if (n == n->parent->left)

return n->parent->right;

return n->parent->left;

void delete_one_child(node n) {

/* N ma jednoho nenuloveho potomka */

node child = (is_leaf(n->right)) ? n->left : n->right;

replace_node(n, child);

if (n->color == BLACK) {

if (child->color == RED)

child->color = BLACK;

delete_case1(child);

Delete (1.případ)

void delete_case1(node n) {

if (n->parent == NULL)

return;

delete_case2(n);

Delete (2.případ)

● Předpoklad: N je levý potomek P● S červený, P, S obrátí barvy● S levá rotace k P, přesun S místo Pvoid delete_case2(node n) {

if (sibling(n)->color == RED) {

n->parent->color = RED;

sibling(n)->color = BLACK;

if (n == n->parent->left)

rotate_right(n->parent);

delete_case3(n);

Delete (3.případ)

● N, P, S jsou černí, S obarvíme na červeno, P pryčvoid delete_case3(node n) {

if (n->parent->color == BLACK &&

sibling(n)->color == BLACK &&

sibling(n)->left->color == BLACK &&

sibling(n)->right->color == BLACK)

sibling(n)->color = RED;

delete_case1(n->parent);

delete_case4(n);

Delete (4.případ)

● N, S černí, P červenávoid delete_case4(node n) {

if (n->parent->color == RED &&

sibling(n)->left->color == BLACK &&

delete_case5(n);

● Prohodíme barvy u S, P

Delete (5.případ)

● S černá, Sl červená, Sr černá● N je levý potomek P● Pravá rotace S, ● Sl černý, S červená● N má červené S napravo● -> 6.případ●

Delete (5.případ)void delete_case5(node n) {

if (n == n->parent->left &&

sibling(n)->left->color == RED &&

sibling(n)->left->color = BLACK;

rotate_right(sibling(n));

else if (n == n->parent->right &&

sibling(n)->right->color == RED &&

sibling(n)->left->color == BLACK)

sibling(n)->right->color = BLACK;

rotate_left(sibling(n));

delete_case6(n);

Delete (6.případ)

● S černý, Sr červený● N levý potomek P● Levá rotace P● S rodič N, Sr černýKudy může jít když ne z N?● Přes S, Sr● Přes S, P●

Delete (6.případ)void delete_case6(node n) {

sibling(n)->color = n->parent->color;

if (n == n->parent->left) {

/* Here, sibling(n)->color == BLACK &&

sibling(n)->right->color == RED */

sibling(n)->right->color = BLACK;

/* Here, sibling(n)->color == BLACK &&

sibling(n)->left->color == RED */

sibling(n)->left->color = BLACK;

rotate_right(n->parent); }}

Otázky??

All your base are belong to us

Red Black tree

Education