Bai8 caynhiphan
- 1. C畉u tr炭c d畛 li畛u v thu畉t to叩n T狸m ki畉m C叩c c但y c但n b畉ng 畛ng kh叩c v c但y 畛 - en (Red-Black and Other Dynamically BalancedTrees)
- 2. T狸m ki畉m Vi畉ng thm (Re-visited) C但y nh畛 ph但n O(log n) n畉u n坦 l c但y c但n b畉ng C但y nh畛 ph但n 董n gi畉n t畛t cho c叩c m畉ng t挑nh T畉n xu畉t th畉p (preferably zero) cho insertions/deletions Nh動ng b畛 d畛 li畛u c畛a t担i c坦 th畛 thay 畛i! B畛 d畛 li畛u 畛ng C畉n thi畉t ph畉i t畉o ra c但y c但n b畉ng 畉u ti棚n, ki畛m tra m畛t vi ho畉t 畛ng c畛a c但y c董 b畉n. H畛u 鱈ch trong m畛t vi c叩ch!
- 3. C但y du l畛ch Du l畛ch = vi畉ng thm t畉t c畉 c叩c node c畛a c但y Ba ch畛n l畛a c董 b畉n Th畛 t畛 tr動畛c G畛c C但y con tr叩i C但y con ph畉i x A + x + B C x D E F L R L L R
- 4. C但y du l畛ch Du l畛ch = vi畉ng thm t畉t c畉 c叩c node c畛a c但y Ba ch畛 l畛a c董 b畉n Th畛 t畛 gi畛a C但y con tr叩i G畛c C但y con ph畉i A x B + C x D x E + F L R L 11
- 5. C但y du l畛ch Du l畛ch = Vi畉ng thm c叩c node c畛a c但y Ba ch畛n l畛a c董 b畉n Th畛 t畛 sau C但y con tr叩i C但y con ph畉i G畛c A B C + D E x x F + x L R L 11
- 6. C但y du l畛ch Th畛 t畛 sau C但y con tr叩i C但y con ph畉i G畛c C担ng th畛c 畉o C担ng th畛c 畉i s畛 = C但y du l畛ch no? (A (((BC+)(DEx) x) F +)x ) 11 (A x(((B+C) x(DxE))+F))
- 7. C但y T狸m ki畉m C但y t狸m ki畉m nh畛 ph但n T畉o m畛t danh s叩ch s畉p x畉p theo th畛 t畛 gi畛a Th動 t畛 : A D E G H K L M N O P T V
- 8. C但y T狸m ki畉m C但y t狸m ki畉m nh畛 ph但n B畉o qu畉n th畛 t畛 Quan s叩t th畉y r畉ng: bi畉n 畛i ny b畉o qu畉n c但y t狸m ki畉m
- 9. C但y- t狸m ki畉m C但y t狸m ki畉m nh畛 ph但n B畉o qu畉n th畛 t畛 Quan s叩t th畉y r畉ng: bi畉n 畛i ny b畉o qu畉n c但y t狸m ki畉m Ch炭ng t担i th畛c hi畛n m畛t g坦c quay 畛i v畛i c但y con v畛 c叩c node T v O.
- 10. C但y - Xoay C但y t狸m ki畉m nh畛 ph但n G坦c quay c坦 th畛 th畛c hi畛n theo hu畛ng tr叩i ho畉c ph畉i (left- or right-rotations) Cho c畉 hai c但y: Du l畛ch theo th畛 t畛 gi畛a(inorder) l A x B y C
- 11. C但y - Xoay C但y t狸m ki畉m nh畛 ph但n G坦c quay c坦 th畛 th畛c hi畛n theo hu畛ng tr叩i ho畉c ph畉i (left- or right-rotations) Ch炭 箪 r畉ng: Vi畛c xoay c畉n thi畉t ph畉i di chuy畛n B t畛 con ph畉i c畛a x 畉n con tr叩i c畛a y
- 12. C但y -C叩c c但y 畛 en M畛t c但y Red-Black C但y t狸m ki畉m nh畛 ph但n M畛i node c坦 m畉u red ho畉c black M畛t c但y nh畛 ph但n th担ng th動畛ng v畛i c叩c node 動畛c t担 mu t畉o thnh c但y 畛- en
- 13. C但y C但y 畛 en M畛t c但y 畛 en (A Red-Black Tree) T畉t c畉 c叩c node l 畛 ho畉c en C叩c l叩 l en (BLACK) Khi b畉n t狸m hi畛u o畉n code rb-tree, b畉n s畉 g畉p c叩c node g叩c (black) 動畛c b畛 xung nh動 c叩c l叩. Ch炭ng kh担ng ch畛a d畛 li畛u. C叩c node g叩c (black)
- 14. C但y C但y 畛 en M畛t c但y 畛 en (A Red-Black Tree) T畉t c畉 c叩c node l 畛 ho畉c en C叩c l叩 l en (BLACK) N畉u m畛t node l RED, th狸 c畉 hai con c畛a n坦 l BLACK i畛u ny c坦 ngh挑a: kh担ng c坦 M畛t nh叩nh no t畛n t畉i hai node 畛 k畉 li畛n nhau. (Nh動ng b畉t c畛 c叩c node BLACK no c滴ng c坦 th畛 k畉 li畛n nhau.)
- 15. C但y C但y 畛 en M畛t c但y 畛 en (A Red-Black Tree) T畉t c畉 c叩c node l 畛 ho畉c en C叩c l叩 l en (BLACK) N畉u m畛t node l RED, th狸 c畉 hai con c畛a n坦 l BLACK M畛i nh叩nh t畛 m畛t node 畉n m畛t l叩 ch畛a c湛ng s畛 l動畛ng c叩c node BLACK T鱈nh t畛 g畛c(root), c坦 3 node BLACK tr棚n t畉t c畉 c叩c 動畛ng
- 16. C但y C但y 畛 en M畛t c但y 畛 en (A Red-Black Tree) T畉t c畉 c叩c node l 畛 ho畉c en C叩c l叩 l en (BLACK) N畉u m畛t node l RED, th狸 c畉 hai con c畛a n坦 l BLACK M畛i nh叩nh t畛 m畛t node 畉n m畛t l叩 ch畛a c湛ng s畛 l動畛ng c叩c node BLACK Chi畛u di c畛a nh叩nh ny ch鱈nh l Chi畛u cao c叩c node en c畛a c但y
- 17. C但y C但y 畛 en Lemma M畛t RB-Tree v畛i n node c坦 height 2 log(n+1) Proof .. See Cormen B畉n ch畉t, height 2 black height Th畛i gian t狸m ki畉m O( log n )
- 18. Gi畛ng nh動 m畛t C但y nh畛 ph但n, B畛 xung th棚m hai Thu畛c t鱈nh 叩nh D畉u C但y C但y 畛 en C畉u tr炭c d畛 li畛u Nh動 ch炭ng t担i 達 bi畉t, C叩c node trong c但y red-black c畉n bi畉t cha m畉 c畛a ch炭ng, Do 坦, ch炭ng t担i c畉n c畉u tr炭c d畛 li畛u ny struct t_red_black_node { enum { red, black } colour; void *item; struct t_red_black_node *left, *right, *parent; }
- 19. C但y - Insertion Ch竪n th棚m m畛t new node Y棚u c畉u m畛t re-balance c畛a c但y rb_insert( Tree T, node x ) { /* Insert in the tree in the usual way */ tree_insert( T, x ); /* Now restore the red-black property */ x->colour = red; while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; Nh達n c畛a node x Ch竪n node 4 T担 mu red
- 20. C但y - Insertion rb_insert( Tree T, node x ) { /* Insert in the tree in the usual way */ tree_insert( T, x ); /* Now restore the red-black property */ x->colour = red; while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; Trong khi ch動a i t畛i root v cha c畛a x l red x->parent
- 21. C但y - Insertion rb_insert( Tree T, node x ) { /* Insert in the tree in the usual way */ tree_insert( T, x ); /* Now restore the red-black property */ x->colour = red; while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; N畉u x n畉m 畛 b棚n tr叩i 担ng c畛a n坦 x->parent x->parent->parent
- 22. Trees - Insertion /* Now restore the red-black property */ x->colour = red; while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; y l b叩c ph畉i c畛a x x->parent x->parent->parent b叩c ph畉i
- 23. Trees - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; x->parent x->parent->parent B叩c ph畉i N畉u b叩c l red, 畛i m畉u c畛a y, 担ng v cha.
- 24. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent;
- 25. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; Cha c畛a x l畉i n畉m b棚n tr叩i, 叩nh d畉u b叩c c畛a x Nh動ng b叩c l black t畉i th畛i i畛m ny New x
- 26. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); .. Nh動ng b叩c l black t畉i th畛i i畛m ny v x n畉m b棚n ph畉i Cha c畛a n坦
- 27. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); .. V狸 th畉 chuy畛n x l棚n v quay x nh動 m畛t g畛c ...
- 28. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x );
- 29. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); .. Nh動ng cha c畛a x v畉n l red ...
- 30. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); .. B叩c l black .. .. v x chuy畛n v畛 tr叩i cha c畛a n坦 b叩c
- 31. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); else { /* case 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); } .. V狸 th畉 ch炭g ta c坦 tr動畛ng h畛p Cu畛i c湛ng ..
- 32. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); else { /* case 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); } .. 畛i m畉u V quay ..
- 33. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); else { /* case 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); }
- 34. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); else { /* case 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); } B但y gi畛, 但y l c但y red-black .. V狸 th畉, ch炭ng ta k畉t th炭c!
- 35. C但y - Insertion while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); else { /* case 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); } } else .... C叩c tr動畛ng h畛p l t動董ng 動董ng khi cha n畉m 畛 b棚n Ph畉i c畛a 担ng!
- 36. C但y Red-black Ph但n t鱈ch Addition Insertion So s叩nh O(log n) Fix-up V畛i t動ng giai o畉n, x di chuy畛n trong c但y t畛i m畛t m畛c 畛nh c畛a n坦 O(log n) Overall O(log n) Deletion c滴ng O(log n)
- 37. C但y 畛 en C叩i g狸 b畉n c畉n bi畉t? C叩c y棚u c畉u b畉n c畉n n畉m: Thu畉t to叩n t畛n t畉i c坦 li棚n quan 畛nh ngh挑a th畉 no l c但y 畛 en Khi no s畛 d畛ng n坦 ie Nh畛ng bi to叩n no, n坦 c坦 th畛 gi畉i 叩p? 畛 ph畛c t畉p c畛a n坦 N坦 ho畉t 畛ng nh動 th畉 no N董i n, n坦 c坦 th畛 畛ng d畛ng Lm th畉 no 畛 chuy畛n n坦 vo 畛ng d畛ng c畛a b畉n.