Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu nâng cao (Advanced data structures) - Nguyễn Tri Tuấn

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu nâng cao (Advanced data structures) - Nguyễn Tri Tuấn

1. Data Structure & Algorithm Các cấu trúc dữ liệu nâng cao (Advanced data structures) Nguyễn Tri Tuấn Khoa CNTT – ĐH.KHTN.Tp.HCM Email: nttuan@ fit.hcmuns.edu.vn Advanced data structures Review Giới thiệu Cây Đỏ – Đen(Red BlackTree) AA –Tree Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM2 1
2. Review ªĐộ cao của cây nhị phân tìm kiếm (BST) cân bằng cĩN nodes là O(log N) ªCây cân bằng cĩchi phíthấp ªCĩnhiều cách xây dựng cây nhị phân tìm kiếm cân bằng: AVL tree Red-Black tree AA tree Splay tree Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM3 Giới thiệu ªCác thuật ngữ thường dùng: Red Black tree AA tree BST AVL tree Splay tree / Top-down splay tree Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM4 2
3. Advanced data structures Review Giới thiệu Cây Đỏ – Đen(Red BlackTree) AA –Tree Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM5 Red Black Tree ªĐịnh nghĩa ªCấu trúc lưu trữ ªCác tính chất ªCác thao tác cơ bản ªĐánh giá Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM6 3
4. Red Black Tree (tt) ªĐịnh nghĩa: Red-Black tree làmột cây nhị phân tìm kiếm (BST) tuân thủ các quy tắc sau: Mọi node phải là đỏ hoặc đen Node gốc là đen Các node ngồi (external node; NULL node) phải luơn luơn đen Nếu một node là đỏ, những node con của nĩphải là đen Mọi đường dẫn từ gốc đến node ngồi phải cĩcùng số lượng node đen Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM7 Red Black Tree (tt) H = 4 16 B = 2 H = 3 H = 2 B = 2 10 20 B = 2 H = 2 H = 2 H = 1 H = 1 8 12 19 23 B = 1 H = 1 B = 1 B = 1 B = 1 B = 1 2 9 11 Định nghĩa Red-Black tree Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM8 4
5. Red Black Tree (tt) ªChiều cao đen (black height – hb(x)): làsố node đen trên đường đi từ node x đến node ngồi (khơng bao gồm x) ªTừ quy tắc [4] àkhơng thể tồn tại node cha và node con cùng đỏ. Khi cây đỏ đen vi phạm qui tắc này gọi làhiện tượng xung đột đỏ-đỏ Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM9 Red Black Tree (tt) ªCấu trúc lưu trữ: Thơng tin lưu trữ tại Node (key) Địa chỉ node gốc của cây con bên trái (* pLeft) Địa chỉ node gốc của cây con bên phải (* pRight) Địa chỉ của node cha (* pParent) Thuộc tính màu của node (color) Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM10 5
6. Red Black Tree (tt) typedef enum {BLACK, RED} NodeColor; typedef intDataType;// Kiểu dữ liệu typedef struct NodeTag { DataTypekey;// Dữ liệu struct NodeTag *pLeft; struct NodeTag *pRight; struct NodeTag *pParent; NodeColor color; } RBNode; Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM11 Red Black Tree (tt) ªCác tính chất: Tính chất 1: h: chiều cao của cây hb: chiều cao đen h <= 2*hb Tính chất 2: Cây đỏ đen cĩN node thì h <= 2*log(N+1) Tính chất 3: thời gian tìm kiếm O(log N) (Chứng minh tính chất [1] và[2]: bài tập) Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM12 6
7. Red Black Tree (tt) ªCác thao tác cơ bản: Tìm kiếm & duyệt cây: giống BST Thêm node mới (insert node) Xĩa node (delete node) Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM13 Red Black Tree (tt) ªInsert node: Thực hiện giống như cây BST Node mới thêm luơn luơn cĩmàu đỏ Nếu xảy ra vi phạm qui tắc à điều chỉnh cây Demo chương trình Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM14 7
8. Red Black Tree (tt) ª Insert node: (tt) những qui tắc cĩthể bị vi phạm Mọi node phải là đỏ hoặc đen à OK Node gốc là đen à not OK ! Nếu node mới làroot Các node ngồi (NULL) phải luơn luơn đen à OK Nếu một node là đỏ, những node con của nĩphải là đen à not OK ! vìcĩthể parent[z] = RED à 2 node liên tiếp màu đỏ Mọi đường dẫn từ gốc đến nút láphải cĩcùng số lượng node đen à OK vìkhơng làm thay đổi số node đen Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM15 Red Black Tree (tt) RB_Insert_Node(T, z) // T: cây; z: node mới y ← NULL; x ← root[T]; while x ¹ NULL {// đi đến nút lá y ← x// y: node cha của x if (key[z] < key[x]) x ← left[x]; else x ← right[x]; } parent[z] ← y;// thêm node z vào cây if (y == NULL) root[T] ← z;// làcon của node y else if (key[z] < key[y]) left[y] ← z; else right[y] ← z; left[z] ← NULL right[z] ← NULL color[z] ← RED// node mới z cĩmàu đỏ RB_Insert_FixUp(T, z)// điều chỉnh cây Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM16 8
9. Red Black Tree (tt) Vi phạm qui tắc [4] (con của node đỏ phải là node đen) à trường hợp 2 nút anh/em màu đỏ à điều chỉnh bằng cách đảo màu Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM17 Vi phạm qui tắc [4] (con của node đỏ phải là node đen) à điều chỉnh bằng cách xoay cây (Right-Rotation) Xoay cây (Left- Rotation) và đảo màu Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM18 9
10. Red Black Tree (tt) ªPhép đảo màu: Nếu thao tác thêm node làm xuất hiện tình trạng một node đen cĩ hai node con đỏ, chúng ta đổi các node con thành đen vànode cha thành đỏ (trừ khi node cha lànode gốc, nĩvẫn giữ màu đen). Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM19 Red Black Tree (tt) ªPhép xoay cây: Khi thêm hoặc xốnode, nếu vi phạm qui tắc [4] (một node con vànode cha khơng thể đồng màu đỏ) à thực hiện phép xoay cây Cĩ2 phép xoay cây: Xoay trái (Left-Rotation) Xoay phải (Right-Rotation) Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM20 10
11. Red Black Tree (tt) ªXoay trái (Left-Rotation): Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM21 Red Black Tree (tt) Vídụphép xoay trái Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM22 11
12. Red Black Tree (tt) RB_Left_Rotate(T, x) y ← right[x]; right[x] ← left[y]; if (left[y] ¹ NULL) parent[left[y]] ← x; parent[y] ← parent[x]; if (parent[x] == NULL) root[T] ← y; else if (x == left[parent[x]]) left[parent[x]] ← y; else right[parent[x]] ← y; left[y] ← x; parent[x] ← y; Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM23 Red Black Tree (tt) ªXoay phải (Right-Rotation): ªRB_Right_Rotate(T, x): tương tự hàm xoay trái (tự xây dựng) Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM24 12
13. Red Black Tree (tt) ªTổng hợp (RB_Insert_FixUp(T, z)): Trường hợp 1: node y (“chú”của z) màu đỏ color[parent[z]] ℜ black color[y] ℜ black color[parent[parent[z]]] ℜ red z = parent[parent[z]] Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM25 Red Black Tree (tt) ªTổng hợp (RB_Insert_FixUp): (tt) Trường hợp 2: node y (“ơng”của z) màu đen, z là node con bên trái color[parent[z]] ℜ black color[parent[parent[z]]] ℜ red RIGHT-ROTATE(T, parent[parent[z]]) Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM26 13
14. Red Black Tree (tt) ªTổng hợp (RB_Insert_FixUp): (tt) Trường hợp 3: node y (“ơng”của z) màu đen, z là node con bên phải Case 3 Case 2 z ℜ parent[z] LEFT-ROTATE(T, z) Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM27 Red Black Tree (tt) Thêm4 11 Case 1 11 Case 3 2 14 2 14 y z 1 7 15 1 7 15 5 8 y 5 8 z 4 4 11 Case 2 7 7 14 y z z 2 11 2 8 15 1 5 8 14 1 5 4 15 4 Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM28 14
15. Red Black Tree (tt) ªTổng hợp (RB_Insert_FixUp): (tt) Ta cũng cĩ 3 trường hợp tương tự [1’], [2’], [3’] khi “cha của z”nằm bên phải “ơng của z” Case [2’] Case [1’] Case [3’] Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM29 Red Black Tree (tt) RB_Insert_FixUp(T, z) while (color[parent[z]] == RED) { // “cha”của z nằm bên trái “ơng”của z if (parent[z] == left[parent[parent[z]]]) { y ← right[parent[parent[z]]]; if (color[y] == RED) “Case 1”; else { if (z == right[parent[z]]) “Case 3”; “Case 2”; } } else // tương tự khi “cha”của z nằm bên phải color[root[T]] ← BLACK Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM30 15
16. Red Black Tree (tt) ªĐánh giáthao tác Insert node: Chi phíthêm phần tử mới (z): O(log N) Chi phícủa RB_Insert_FixUp: O(log N) Chi phítổng cộng: O(log N) Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM31 Red Black Tree (tt) ªDelete node: Cách thức xĩa 1 node: giống như BST Demo chương trình Nếu node bị xốcĩmàu đỏ: khơng gây ra vi phạm Mọi node phải là đỏ hoặc đen à OK Node gốc là đen à OK Các node lá(NULL) phải luơn luơn đen à OK Nếu một node là đỏ, những node con của nĩphải là đen à OK vìkhơng tạo ra 2 node liên tiếp màu đỏ Mọi đường dẫn từ gốc đến nút láphải cĩcùng số lượng node đen à OK vìkhơng làm thay đổi số node đen Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM32 16
17. Red Black Tree (tt) ª Delete node: (tt) Nếu node bị xốcĩmàu đen: cĩthể gây ra vi phạm Mọi node phải là đỏ hoặc đen à OK Node gốc là đen à not OK ! Vìcĩthể xĩa root vàthay bằng node đỏ Các node lá(NULL) phải luơn luơn đen à OK Nếu một node là đỏ, những node con của nĩphải là đen à not OK ! Vìcĩthể tạo ra 2 node liên tiếp màu đỏ Mọi đường dẫn từ gốc đến nút láphải cĩcùng số lượng node đen à not OK ! Vìlàm giảm đổi số node đen Xem chi tiết “Data structure & Analysis in C”, p. 465 Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM33 Red Black Tree (tt) ªĐánh giá: Ưu điểm: Chi phítìm kiếm O(log N) Insert O(log N) Delete O(log N) Minimum O(log N) Maximum O(log N) Hạn chế: Phải lưu trữ thuộc tính màu (color) vàcon trỏ đến nút cha (pParent) Chi phíchèn vàxĩa cao hơn BST vìphải thực hiện đổi màu vàphép quay Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM34 17
18. Advanced data structures Review Giới thiệu Cây Đỏ – Đen(Red BlackTree) AA –Tree Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM35 AA -Tree ªMinh họa ªCác khái niệm ªĐịnh nghĩa ªCấu trúc lưu trữ ªCác thao tác cơ bản ªĐánh giá Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM36 18
19. AA –Tree (tt) Liên kết ngang Liên kết Liên kết con trái con phải 30 70 15 50 60 85 80 90 5 10 20 35 40 55 65 Minh họa cấu trúc cây AA Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM37 AA –Tree (tt) ªCác khái niệm: Mức (Level) của một node Liên kết ngang (Horizontal link) Xoay phải (Right rotation –Skew) Xoay trái (Left rotation –Split) Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM38 19
20. AA –Tree (tt) ªCác khái niệm: (tt) Mức (Level) của một node: làsốliên kết trái từ node đĩ đến NULL Mức của node NULL là0 Mức của node lálà1 Mức2 A B Mức1 C D E Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM39 AA –Tree (tt) ªCác khái niệm:(tt) Liên kết ngang (Horizontal link): làliên kết giữa một node vànode con của node đĩ ở cùng một mức Node con Node cha ở cùng mức A B C D E Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM40 20
21. AA –Tree (tt) ªCác khái niệm: (tt) Xoay phải (Skew): xĩa bỏ liên kết ngang bên trái Sử dụng để điều chỉnh cây X P X P A B C A B C Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM41 AA –Tree (tt) ªCác khái niệm: (tt) Xoay trái (Split): xốbỏ2 liên kết ngang liên tiếp bên phải Sử dụng để điều chỉnh cây R X R G X G A B A B Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM42 21
22. AA –Tree (tt) ªSkew cĩthể tạo ra nhiều liên kết ngang phải liên tiếp à sử dụng Split để điều chỉnh 3 5 10 Skew 5 Split 3 5 10 3 10 Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM43 AA –Tree (tt) ªĐịnh nghĩa: AA tree làmột cây nhị phân tìm kiếm (BST) tuân thủ các quy tắc sau: Liên kết ngang luơn hướng về bên phải Khơng cĩ2 liên kết ngang liên tiếp nhau Một node khơng phải lànode lásẽcĩ2 node con Nếu một node khơng cĩliên kết ngang phải thì2 node con của nĩ ở cùng mức Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM44 22
23. AA –Tree (tt) Liên kết ngang luơn hướng về Khơng cĩ2 Node khơng bên phải liên kết ngang phải lá à cĩ liên tiếp 2 con 30 70 15 50 60 85 80 90 5 10 20 35 40 55 65 2 node con cùng mức khi node cha khơng cĩ liên kết ngang Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM45 AA –Tree (tt) ªTính chất: Level của node con trái nhỏ hơn level của node cha 1 đơn vị Level của node con phải nhỏ hơn hay bằng level của node cha (nhưng khơng quá 1 đơn vị) Thêm một node luơn thực hiện ở mức lá Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM46 23
24. AA –Tree (tt) ªCấu trúc lưu trữ: typedef intDataType;// Kiểu dữ liệu typedef struct NodeTag { DataTypekey;// Dữ liệu struct NodeTag *pLeft; struct NodeTag *pRight; intlevel; // mức của node } AANode; Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM47 AA –Tree (tt) ªCác thao tác cơ bản: Khi thêm 1 node ở mức lá à node thêm vào bên trái à tạo ra một liên kết ngang bên trái à Skew Khi thêm 1 node ở mức lá à node thêm vào bên phải à tạo ra 2 liên kết ngang liên tiếp bên phải à Split 30 70 15 50 60 85 3 5 10 20 35 40 48 55 65 80 90 Skew Spit Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM48 24
25. AA –Tree (tt) ªCác thao tác cơ bản: (tt) Tìm một phần tử: hồn tồn giống cây BST 30 70 15 50 60 85 80 90 5 10 20 35 40 55 65 Tìm “55” Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM49 AA –Tree (tt) ªCác thao tác cơ bản: (tt) Thêm một node: 30 70 15 50 60 85 5 10 20 35 40 45 55 65 80 90 Cần Split Thêm “45” Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM50 25
26. AA –Tree (tt) ªCác thao tác cơ bản: (tt) Thêm một node: 30 70 15 40 50 60 85 5 10 20 35 45 55 65 80 90 Cần Skew Sau khi Split tại “35” Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM51 AA –Tree (tt) ªCác thao tác cơ bản: (tt) Thêm một node: Cần Split 30 70 15 40 50 60 85 5 10 20 35 45 55 65 80 90 Sau khi Skew tại “50” Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM52 26
27. AA –Tree (tt) ªCác thao tác cơ bản: (tt) Thêm một node: Cần Skew Cần Split 30 70 50 15 40 60 85 5 10 20 35 45 55 65 80 90 Sau khi Split tại “40” Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM53 AA –Tree (tt) ªCác thao tác cơ bản: (tt) Thêm một node: 50 30 70 15 40 60 85 5 10 20 35 45 55 65 80 90 Sau khi Skew tại “70”, vàSplit tại “30” à STOP ! Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM54 27
28. AA –Tree (tt) AANode* AA_Insert_Node(DataType x, AANode* t) { if(t == NULL){ t = new AANode; t->key = x; t->pLeft = t->pRight = NULL; t->level = 1; } else if(x key) t->pLeft = AA_Insert_Node(x, t->pLeft); else if(x > t->key) t->pRight = AA_Insert_Node(x, t->pRight); else return t; // trùng khĩa t = Skew(t); t = Split(t); return t; } Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM55 AA –Tree (tt) ªCác thao tác cơ bản: (tt) Thêm một node: VD. thêm “6” 4 10 2 8 12 1 3 5 7 9 11 13 6?? Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM56 28
29. AA –Tree (tt) ªCác thao tác cơ bản: (tt) Xĩa một node: Giảm mức 4 10 2 6 8 12 1 3 5 7 9 11 13 Xĩa “1” Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM57 AA –Tree (tt) ªCác thao tác cơ bản: (tt) Xĩa một node: Giảm mức 4 10 2 3 6 8 12 5 7 9 11 13 Sau khi giảm mức tại “2” Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM58 29
30. AA –Tree (tt) ªCác thao tác cơ bản: (tt) Xĩa một node: Cần Skew 4 10 6 8 12 2 3 5 7 9 11 13 Sau khi giảm mức tại “4”và“10” Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM59 AA –Tree (tt) ªCác thao tác cơ bản: (tt) Xĩa một node: Cần Skew 4 6 10 8 12 2 3 5 7 9 11 13 Sau khi Skew tại “10”, lần 1 Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM60 30
31. AA –Tree (tt) ªCác thao tác cơ bản: (tt) Xĩa một node: Cần Split 4 6 8 10 12 2 3 5 7 9 11 13 Sau khi Skew tại “10”, lần 2 Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM61 AA –Tree (tt) ªCác thao tác cơ bản: (tt) Xĩa một node: 6 Cần Split 4 8 10 12 2 3 5 7 9 11 13 Sau khi Split tại “4” Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM62 31
32. AA –Tree (tt) ªCác thao tác cơ bản: (tt) Xĩa một node: 6 10 4 8 12 2 3 5 7 9 11 13 Sau khi Split tại “8” à STOP ! Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM63 AA –Tree (tt) ªĐánh giá: Độ phức tạp O(log N) Dữ liệu đã sắp xếp khơng làm tăng độ cao của cây Cài đặt đơn giản hơn cây Red-Black Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM64 32
33. Thank you for your attention Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM65 QQ && AA Spring 2006Data Structure & Algorithm -Advanced data structures -Nguyen Tri Tuan, DH.KHTN Tp.HCM66 33