Binární stromy __&7y, +#Q&DMX! ,a0MNZ0C0Wgn, _gOMS@^#00MQQm jNN,BMQAQ0QKAM6 400N0#DQ#M00AQMg 400&@Q#000&�&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ů
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;
else
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;
else
insert_case2(n);
}
Insert (2.případ)
Předek● černý (4, 5 platí)● Červený (4 platí, 5 neplatí)
void insert_case2(node n) {
if (n->parent->color == BLACK)
return; /* porad plati */
else
insert_case3(n);
}
Insert (3.případ)
void insert_case3(node n) {
if (uncle(n) != NULL && uncle(n)->color == RED) {
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insert_case1(grandparent(n));
}
else
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)
void insert_case4(node n) {
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) {
n->parent->color = BLACK;
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
● 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;
else
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;
else
delete_case1(child);
}
}
Delete (1.případ)
void delete_case1(node n) {
if (n->parent == NULL)
return;
else
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_left(n->parent);
else
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);
}
else
delete_case4(n);
}
Delete (4.případ)
● N, S černí, P červenávoid delete_case4(node n) {
if (n->parent->color == RED &&
sibling(n)->color == BLACK &&
sibling(n)->left->color == BLACK &&
sibling(n)->right->color == BLACK)
{
sibling(n)->color = RED;
n->parent->color = BLACK;
}
else
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)->color == BLACK &&
sibling(n)->left->color == RED &&
sibling(n)->right->color == BLACK)
{
sibling(n)->color = RED;
sibling(n)->left->color = BLACK;
rotate_right(sibling(n));
}
else if (n == n->parent->right &&
sibling(n)->color == BLACK &&
sibling(n)->right->color == RED &&
sibling(n)->left->color == BLACK)
{
sibling(n)->color = RED;
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;
n->parent->color = BLACK;
if (n == n->parent->left) {
/* Here, sibling(n)->color == BLACK &&
sibling(n)->right->color == RED */
sibling(n)->right->color = BLACK;
rotate_left(n->parent);
}
else
{
/* 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
