Bai9 caycanbang
0 likes354 views
Ti li畛u m担 t畉 c畉u tr炭c d畛 li畛u c畛a c但y 畛-en v c但y AVL, bao g畛m c叩c thu畉t to叩n ch竪n, x坦a v t狸m ki畉m v畛i 畛 ph畛c t畉p O(log n). N坦 bn lu畉n v畛 c叩ch t叩i c但n b畉ng c但y, hi畛u su畉t c畛a c叩c c但y ny v 畛 c畉p t畛i c叩c c但y B v B+. C叩c c但y B+ 動畛c s畛 d畛ng trong c董 s畛 d畛 li畛u l畛n 畛 t畛i 動u h坦a vi畛c truy c畉p d畛 li畛u t畛 挑a.
Bai9 caycanbang
- 1. C畉u tr炭c d畛 li畛u v Thu畉t to叩n T狸m ki畉m C但y 畛- en v C叩c c但y c但n b畉ng 畛ng kh叩c
- 2. T坦m t畉t C但y 畛 - en (Red-Black) M畛t thu畉t to叩n ph畛c t畉p Cho O(log n) v畛i Th棚m(addition), X坦a(deletion) v T狸m(search) C叩c k畛 thu畉t ph畉n m畛m Bi畉t v畛 thu畉t to叩n Bi畉t khi no c坦 th畛 d湛ng ch炭ng Bi畉t v畛 hi畛u su畉t Bi畉t n董i c坦 th畛 叩p d畛ng 畛 th担ng minh 畛 d湛ng cho c叩c m叩y ph叩t minh... H畛 s畛 d畛ng l畉i b畛 m達 V狸 th畉 h畛 c畉n nhi畛u th畛i gian h董n cho Chuy畉n i, n, u畛ng, ... B畉t c畛 nh畛ng g狸 kh叩c m t担i s畉 cho vo 但y.
- 3. C但y AVL v c叩c c但y c但n b畉ng kh叩c C但y AVL Thu畉t gi畉i c但y c但n b畉ng 畉u ti棚n Kh叩m ph叩 b畛i: Adelson-Velskii v Landis T鱈nh ch畉t C但y nh畛 ph但n t狸m ki畉m 畛 cao con tr叩i v con ph畉i ch棚nh l畛ch nhi畛u nh畉t l 1 C叩c c但y con c滴ng l c但y AVL AVL Tree AVL Tree
- 4. C但y AVL Chi畛u cao 畛nh l箪 M畛t c但y AVL c坦 chi畛u cao h c坦 鱈t nh畉t Fh+3+1 node Ch畛ng minh 畛 Sh l k鱈ch c畛 c畛a c但y AVL nh畛 nh畉t v畛i chi畛u cao h R探 rng, S0 = 1 and S1 = 2 H董n n畛a, Sh = Sh-1 + Sh-2 + 1 M畛t c但y c坦 chi畛u cao c畛c ti畛u ph畉i bao g畛p nhi畛u c但y c坦 chi畛u cao nh畛 v畛i 畛 l畛ch t畛i a l 1 Do 坦 .. Sh = Fh+3+1
- 5. C但y AVL Chi畛u cao B但y gi畛, t畛ng qu叩t cho i, Fi+1 / Fi = , trong 坦 = 遜(1 + 5) ho畉c Fi c (遜(1 + 5))i Sh = Fh+3 + 1 = O( bh ) n Sh , v狸 th畉 n l ( bh ) v h logb n ho畉c h is O(log n)
- 6. C但y AVL Chi畛u cao B但y gi畛, t畛ng qu叩t cho i, Fi+1 / Fi = , trong 坦 = 遜(1 + 5) ho畉c Fi c (遜(1 + 5))i Sh = Fh+3 + 1 = O( bh ) n Sh , v狸 th畉 n l ( bh ) v h logb n ho畉c h l O(log n) Trong tr動畛ng h畛p ny, ch畛 ra h 1.44 logb (n+2) - 1.328 h kh担ng t畛i h董n 44% cao h董n so v畛i t畛i 動u
- 7. C但y AVL T叩i c但n b畉ng Ch竪n c叩c l叩 vo c但y non-AVL 4 tr動畛ng h畛p 1 v 4 l c叩c 畉nh 畛i x畛ng 2 v 3 l c叩c 畉nh 畛i x畛ng 1 2 3 4
- 8. C但y AVL T叩i c但n b畉ng Tr動畛ng h畛p 1 動畛c gi畉i b畛i ph辿p quay Tr動畛ng h畛p 4 l quay m畛t 畉nh 畛i x畛ng
- 9. C但y AVL T叩i c但n b畉ng Tr動畛ng h畛p 2 c畉n m畛t ph辿p quay k辿p (double) Tr動董ng h畛p 3 l ph辿p quay 畉nh 畛i x畛ng
- 10. C但y AVL C畉u tr炭c d畛 li畛u C叩c c但y AVL c坦 th畛 動畛c th畛c hi畛n v畛i m畛t c畛 畛 b叩o hi畛u tr畉ng th叩i c但n b畉ng Ch竪n (Insertion) Ch竪n m畛t node m畛i (gi畛ng b畉t c畛 c但y nh畛 ph但n no) Vi畛c c但n b畉ng l畉i c但y (duy畛t ng動畛c l棚n) c畉n thi畉t ph畛c h畛i c叩c t鱈nh ch畉t c畛a AVL typedef enum { LeftHeavy, Balanced, RightHeavy } BalanceFactor; struct AVL_node { BalanceFactor bf; void *item; struct AVL_node *left, *right; }
- 11. C叩c c但y 畛ng - Red-Black ho畉c AVL Ch竪n (Insertion) AVL : hai b動畛c th畛c hi畛n tr棚n c但y Duy畛t xu畛ng 畛 ch竪n th棚m node Duy畛t l棚n 畛 t叩i c但n b畉ng (re-balance) Red-Black : hai b動畛c th畛c hi畛n tr棚n c但y Duy畛t xu畛ng 畛 ch竪n th棚m node Duy畛t l棚n 畛 t叩i c但n b畉ng (re-balance) nh動ng Red-Black ph畛 bi畉n h董n??
- 12. C叩c c但y 畛ng C畉nh b叩o Ch竪n (Insertion) N畉u b畉n 畛c Cormen et al, Kh担ng c坦 m畛t l箪 do no 畛 th鱈ch m畛t c但y 畛- en Tuy nhi棚n, trong s叩ch c畛a Weiss M A Weiss, Algorithms, Data Structures and Problem Solving with C++, Addison-Wesley, 1996 B畉n t狸m th畉y r畉ng b畉n c坦 th畛 c但n b畉ng c但y red-black T畛ng k畉t l畉i ! T畉o m畛t c但y red-black nhi畛u hi畛u qu畉 h董n AVL N畉u m達 code l h畛p l箪!!!
- 13. C叩c c但y 畛ng C畉nh b叩o Ch竪n (Insertion) N畉u b畉n 畛c Cormen et al, Kh担ng c坦 m畛t l箪 do no 畛 th鱈ch m畛t c但y 畛- en Tuy nhi棚n, trong s叩ch c畛a Weiss M A Weiss, Algorithms, Data Structures and Problem Solving with C++, Addison-Wesley, 1996 B畉n t狸m th畉y r畉ng b畉n c坦 th畛 c但n b畉ng c但y red-black T畛ng k畉t l畉i ! T畉o m畛t c但y red-black nhi畛u hi畛u qu畉 h董n AVL N畉u m達 code l h畛p l箪!!! Y棚u c畉u: B畉n c畉n thi畉t 畛c c叩c ti li畛u!
- 14. C叩c c但y 畛ng C畉nh b叩o T畛ng k畉t cho ch竪n Insertion Khi b畉n i 畉n ph鱈a d動畛i c畛a m畛t c但y, n畉u b畉n t狸m th畉y m畛t node v畛i hai con red, t担 n坦 mu red v con c畛a n坦 mu black i畛u ny kh担ng bi畉n 畛i s畛 l動畛ng c叩c node en trong b畉t c畛 nh叩nh no N畉u cha c畛a node l m畉u red, m畛t ph辿p quay l c畉n thi畉t ... C坦 th畛 c畉n m畛t ph辿p quay 董n ho畉c quay k辿p
- 15. C但y Ch竪n (Insertion) Adding 4 ... Ph叩t hi畛n hai Con mu 畛 畛 但y Ho叩n v畛 mu cho nhau
- 16. C但y Ch竪n (Insertion) Adding 4 ... M畛t d達y node 畛, Vi ph畉m T鱈nh ch畉t red-black Quay
- 17. C但y Ch竪n (Insertion) Adding 4 ... Quay B畛 xung 4
- 18. C但y c但n b畉ng Ch動a c坦 nhi畛u bi畉n 畛i C董 b畉n c坦 c湛ng c叩c 箪 t動畛ng 2-3 Trees 2-3-4 Trees Tr動畛ng h畛p d畉c bi畛t c畛a c但y m-way! S畛 l動畛ng c叩c con cho m畛t node bi畉n thi棚n Th畛 t畛c th畛c hi畛n ph畛c t畉p h董n 2-3-4 trees Chi畉u v畛 c但y red-black C坦 l畉 h畛u d畛ng khi hi畛u m畛t c但y red-black
- 19. T畛ng k畉t C但y AVL 畉u ti棚n l c但y c但n b畉ng 畛ng Chi畛u cao thu畛c 44% so v畛i i畛u ki畛n thu畉n l畛i nh畉t T叩i c但n b畉ng v畛i c叩c g坦c quay O(log n) Hi畛u qu畉 th畉p h董n so v畛i c但y red-black 2-3, 2-3-4 trees m-way trees ch動a c坦 nhi畛u bi畉n 畛i 2-3-4 trees 動畛c chi畉u v畛 c但y red-black
- 20. C但y m nh叩nh (m-way trees) Ch畛 hai con cho m畛t node? R炭t g畛n 畛 s但u c畛a c但y 畉n O(logmn) v畛i m-way trees m con, m-1 kh坦a cho node m = 10 : 106 kh坦a trong 6 m畛c kh叩c 20 cho c但y nh畛 ph但n nh動ng ........
- 21. C但y m nh叩nh (m-way trees) Nh動ng b畉n ph畉i t狸m ki畉m m kh坦a trong m畛i node! 叩nh 畛i gi畛a s畛 m畛c v th畛i gian t狸m ki畉m! Ch畛 l m畛t s畛 hi畉u k畛?
- 22. C但y B(Block) (B-trees) T畉t c畉 c叩c l叩 n畉m tr棚n c湛ng m畛t m畛c T畉t c畉 c叩c node ngo畉i tr畛 g畛c v c叩c l叩 c坦: t nh畉t m/2 con Nhi畛u nh畉t m con C但y B+ (B+ trees) T畉t c畉 c叩c kh坦a trong c叩c node l gi畉 Ch畛 c叩c kh坦a trong c叩c l叩 nh畉n gi叩 tr畛 th畛c real Li棚n k畉t c叩c l叩 C坦 kh畉 nng duy畛t h畉t danh s叩ch theo th畛 t畛 gi畛a kh担ng c畉n th担ng qua c叩c node cao h董n. M畛i node ch畛a 鱈t nh畉t m畛t n畛a s畛 l動畛ng kh坦a
- 23. C但y B+ C但y B+ T畉t c畉 c叩c kh坦a trong c叩c node l gi畉 Ch畛 c叩c kh坦a trong c叩c l叩 nh畉n gi叩 tr畛 th畛c real C叩c b畉n ghi d畛 li畛u 動畛c gi畛 trong c叩c v湛ng ri棚ng
- 24. C但y B+ - Duy畛t theo th畛 t畛 gi畛a C但y B+ (B+ trees) Li棚n k畉t c叩c l叩 C坦 kh畉 nng duy畛t h畉t danh s叩ch theo th畛 t畛 gi畛a kh担ng c畉n th担ng qua c叩c node cao h董n.
- 25. C但y (B+) S畛 d畛ng S畛 d畛ng - C董 s畛 d畛 li畛u l畛n 畛c m畛t kh畛i 挑a ch畉m h董n nhi畛u so v畛i 畛c b畛 nh畛 ( ~ms vs ~ns ) 畉t t畛ng kh畛i c畛a c叩c kh坦a vo trong m畛t kh畛i 挑a Physical disc blocks
- 26. C但y B (B-trees) - Ch竪n Ch竪n (Insertion) T鱈nh ch畉t c但y B (B-tree): m畛t kh畛i c坦 鱈t nh畉t m畛t n畛a s畛 kh坦a Ch竪n vo trong kh畛i v畛i m kh坦a Trn kh畛i Ph但n t叩ch kh畛i 畉y m畛t kh坦a Ph但n t叩ch cha m畉 n畉u c畉n thi畉t N畉u g畛c b畛 t叩ch, c但y 動畛c 畉t 畛 m畛c s但u h董n
- 27. C但y B Ch竪n Ch竪n Ch竪n 9 Node b畛 trn, ph但n t叩ch n坦 畉y node gi畛a (8) G畛c b畛 trn, ph但n t叩ch n坦 畉y node gi畛a (6) Node g畛c m畛i h狸nh thnh Chi畛u cao tng 1
- 28. C但y B tr棚n 挑a C叩c kh畛i 挑a 512 - 8k bytes 100s of keys D湛ng t狸m ki畉m nh畛 ph但n cho c叩c kh畛i T畛ng qu叩t O( log n ) Lm h畛p v畛i ph畉n c畛ng ! Th畛 t畛c x坦a t動董ng t畛 (Deletion) Tuy nhi棚n, ph畉i h畛i nh畉p c叩c kh畛i (block) 畛 b畉o 畉m t鱈nh ch畉t B-tree (鱈t nh畉t b畉ng n畛a s畛 l動畛ng kh坦a)