›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Cấu trúc cây - Đậu Ngọc Hà Dương

pptx 141 trang Gia Huy 16/05/2022 3021
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Cấu trúc cây - Đậu Ngọc Hà Dương", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxbai_giang_cau_truc_du_lieu_va_giai_thuat_cau_truc_cay_dau_ng.pptx

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Cấu trúc cây - Đậu Ngọc Hà Dương

  1. Giảng viên: Đậu Ngọc Hà Dương
  2. 2 Khái niệm Phép duyệt cây và Biểu diễn cây Cây nhị phân và Cây nhị phân tìm kiếm Cây AVL Cây AA Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  3. 3 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  4. 4  Tree  Search tree  Binary search tree  Balanced tree  AVL tree  AA tree  Red-Black tree  Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  5. 5 a b c d e f g h i j k l m n o p q Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  6. 6 Sơ đồ tổ chức Cây thư mục Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  7. 7 Cây (cây có gốc) được xác định đệ quy như sau: 1. Tập hợp gồm 1 đỉnh là một cây. Cây này có gốc là đỉnh duy nhất của nó. 2. Gọi T1, T2, Tk (k ≥ 1) là các cây không cắt nhau có gốc tương ứng r1, r2, rk. Giả sử r là một đỉnh mới không thuộc các cây Ti. Khi đó, tập hợp T gồm đỉnh r và các cây Ti tạo thành một cây mới với gốc r. Các cây T1, T2, Tk được gọi là cây con của gốc r. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  8. 8 Nút gốc r1 r2 rk T1 T2 Tk Cây con Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  9. 9  node: đỉnh  root: gốc cây  leaf: lá  inner node/internal node: đỉnh trong  parent: đỉnh cha  child: đỉnh con  path: đường đi Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  10. 10 Nút gốc r1 r2 rk k1 k2 T1 T2 Tk k3 k4 k5 Cây con Nút lá Đường đi k Cấu trúc dữ liệu và giải thuật - HCMUS 2011 6
  11. 11  degree/order: bậc  Bậc của node: Số con của node  Bậc của cây: bậc lớn nhất trong số các con  depth/level: độ sâu/mức  Mức (độ sâu)của node: Chiều dài của đường đi từ node gốc đến node đó cộng thêm 1.  height: chiều cao  Chiều cao cây: ◼ Cây rỗng: 0 ◼ Cây khác rỗng: Mức lớn nhất giữa các node của cây Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  12. 12 Bậc = k Nút gốc Bậc = 2 Độ cao = 4 r1 r2 rk k1 k2 T1 T2 Tk k3 k4 k5 Cây con Nút lá Đường đi k Cấu trúc dữ liệu và giải thuật - HCMUS 2011 6
  13. 13 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  14. 14  Đảm bảo đến mỗi node trên cây chính xác một lần một cách có hệ thống.  Nhiều thao tác xử lý trên cây cần phải sử dụng đến phép duyệt cây.  Các phép cơ bản:  Duyệt trước (Pre-order)  Duyệt giữa (In-order)  Duyệt sau (Post-order) Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  15. 15 Parent(a)? Parent(b) = a Eldest- Tìm cha một đỉnh. Child(c) = g • Parent(x) Tìm đỉnh con trái nhất. b c • EldestChild(x) Tìm đỉnh kề phải. d e f g h • NextSibling(x) NextSibling(g) = h i NextSibling(h)? Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  16. 16 Duyệt theo chiều sâu Duyệt trước Duyệt giữa b c e f g h Duyệt sau i j k Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  17. 17 Pre-order Post-order void Preorder(NODE A) void Postorder(NODE A) { { NODE B; NODE B; Visit(A); B = EldestChild(A); B = EldestChild(A); while (B != ) { while (B != ) { Postorder(B); Preorder(B); B = NextSibling(B); B = NextSibling(B); } } Visit(A); } } Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  18. 18 In-Order void Inorder(NODE A) { NODE B; B = EldestChild(A); if (B != ) { Inorder(B); B = NextSibling(B); } Visit(A); while (B != ) { Inorder(B); B = NextSibling(B); } } Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  19. 19 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  20. 20 info child id next 1 a 2 3 2 b 4 5 3 c 6 7 8 4 d 5 e 9 10 6 f b c 7 g 11 8 h d e f g h 9 i 10 j 11 k i j k Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  21. 21 A Root B C D E F G H I J K Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  22. 22 Info Eldest Child Next Sibling 1 a 2 0 2 b 4 3 3 c 6 0 4 d 0 5 b c 5 e 9 0 6 f 0 7 7 g 11 8 d e f g h 8 h 0 0 9 i 0 10 10 j 0 0 i j k 11 k 0 0 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  23. 23 A Root B C D E F G H I J K Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  24. 24 Info Parent 1 a 0 2 b 1 3 c 1 4 d 2 b c 5 e 2 6 f 3 7 g 3 d e f g h 8 h 3 9 i 5 10 j 5 i j k 11 k 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  25. 25 Binary tree Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  26. 26  Là cây mà mỗi đỉnh có bậc tối đa bằng 2.  Các cây con được b c gọi là cây con trái và cây con phải. d e f g  Có toàn bộ các thao tác cơ bản của cây. h i j struct NODE { Data key; NODE *pLeft; NODE *pRight; }; Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  27. 27  Cây tổ chức thi đấu  Cây biểu thức số học  Lưu trữ và tìm kiếm * + thông tin. 4 - 1 sin 3 4 30 Cây biểu thức: 4 * (3 – 4) + (1 + sin(30)) Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  28. 28  Cây nhị phân tìm kiếm là cây nhị phân thỏa mãn các điều kiện sau: 1. Khóa của các đỉnh thuộc cây con trái nhỏ hơn khóa gốc. 2. Khóa của gốc nhỏ hơn khóa các đỉnh thuộc cây con phải. 3. Cây con trái và cây con phải của gốc cũng là cây nhị phân tìm kiếm. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  29. 29 4 10 2 6 9 23 5 7 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  30. 30  Đặc điểm:  Có thứ tự  Không có phần tử trùng  Dễ dàng tạo dữ liệu sắp xếp, và tìm kiếm Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  31. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  32. 32  Thêm phần tử (khóa)  Tìm kiếm phần tử (khóa)  Xóa phần tử (khóa)  Sắp xếp  Duyệt cây  Quay cây Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  33. 33  Bước 1: Bắt đầu từ gốc  Bước 2: So sánh dữ liệu (khóa) cần thêm với dữ liệu (khóa) của node hiện hành.  Nếu bằng nhau => Đã tồn tại. Kết thúc  Nếu nhỏ hơn => Đi qua nhánh trái, Tiếp bước 2.  Nếu lớn hơn => Đi qua nhánh phải, Tiếp bước 2.  Bước 3: Không thể đi tiếp nữa => Tạo node mới với dữ liệu (khóa) cần thêm. Kết thúc Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  34. 34  Bước 1: Bắt đầu từ gốc  Bước 2: So sánh dữ liệu (khóa) cần tìm với dữ liệu (khóa) của node hiện hành.  Nếu bằng nhau => Tìm thấy. Kết thúc  Nếu nhỏ hơn => Đi qua nhánh trái, Tiếp bước 2.  Nếu lớn hơn => Đi qua nhánh phải, Tiếp bước 2.  Bước 3: Không thể đi tiếp nữa => Không tìm thấy. Kết thúc. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  35. 35  Tìm đến node chứa dữ liệu (khóa) cần xóa.  Xét các trường hợp:  Node lá  Node chỉ có 1 con  Node có 2 con: dùng phần tử thế mạng để xóa thế. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  36. 36  Cho cây nhị phân tìm kiếm  Thứ tự duyệt các node 8 19 nếu sử dụng Duyệt giữa? 1 9 16  Nêu nhận xét 13 18  Có thể dễ dàng tạo dữ liệu sắp xếp nếu dùng phép duyệt giữa 14 1 8 9 13 14 15 16 18 19 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  37. 37  Duyệt trước 4 2 20 1 3 25 23 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  38. 38  Duyệt giữa 4 2 20 1 3 25 23 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  39. 39  Duyệt sau 4 2 20 1 3 25 23 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  40. 40 P Quay trái cây P P Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  41. 41 Quay trái cây P P 18 35 8 35 18 50 20 50 8 20 55 55 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  42. 42 Quay phải cây P P P Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  43. 43 Quay phải cây P P 50 40 40 55 37 50 37 45 65 36 45 55 65 36 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  44. 44  Đối với phép tìm kiếm:  Trường hợp tốt nhất: mỗi nút (trừ nút lá) đều có 2 con: O(log2n) (chính là chiều cao của cây).  Trường hợp xấu nhất: cây trở thành danh sách liên kết: O(n).  Trường hợp trung bình là bao nhiêu? O(log2n) Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  45. 45  Tạo cây nhị phân tìm kiếm theo thứ tự nhập như sau: 1, 8, 9, 12, 14, 15, 16, 18, 19 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  46. 46  Tạo cây nhị phân tìm kiếm theo thứ tự nhập như sau: 1, 8, 9, 12, 14, 15, 16, 18, 19 1 8 9 12 14 15 16 18 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 19
  47. 47 AVL tree Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  48. 48  Do G.M. Adelsen Velskii và E.M. Lendis đưa ra vào năm 1962, đặt tên là cây AVL. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  49. 49  Cây cân bằng AVL là cây nhị phân tìm kiếm mà tại mỗi đỉnh của cây, độ cao của cây con trái và cây con phải không chênh lệch quá 1. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  50. 50  Ví dụ : 12 12 8 18 8 18 5 11 17 5 11 17 4 7 4 7 Cây AVL? 2 Cây AVL? Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  51. 51  Việc xây dựng cây cân bằng dựa trên cây nhị phân tìm kiếm, chỉ bổ sung thêm 1 giá trị cho biết sự cân bằng của các cây con như thế nào.  Cách làm gợi ý: struct NODE { Data key; NODE *pLeft, *pRight; int bal; };  Trong đó giá trị bal (balance, cân bằng) có thể là: 0: cân bằng; 1: lệch trái; 2: lệch phải Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  52. 52  Mất cân bằng trái-trái (L-L)  Mất cân bằng trái-phải (L-R)  Mất cân bằng phải-phải (R-R)  Mất cân bằng phải-trái (R-L) Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  53. 53  Mất cân bằng trái-trái (L-L) 12 18 5 17 4 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  54. 54  Mất cân bằng trái-phải (L-R) 12 18 5 17 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  55. 55  Mất cân bằng phải-phải (R-R) 12 8 5 11 22 25 4 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  56. 56  Mất cân bằng phải-trái (R-L) 12 8 5 11 22 4 7 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  57. 57  Giả sử tại một node cây xảy ra mất cân bằng bên phải (cây con phải chênh lệch với cây con trái hơn một đơn vị):  Mất cân bằng phải-phải (RR) ◼ Quay trái  Mất cân bằng phải-trái (R-L) ◼ Quay phải ◼ Quay trái Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  58. 58  P mất cân bằng phải-phải (RR): P Quay trái cây P P Q h+1 h h h+1 h h Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  59. 59  P mất cân bằng phải-phải (RR): Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  60. 60  P mất cân bằng phải-phải (RR): Quay trái cây P P 18 35 Q 8 35 18 50 20 50 8 20 55 55 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  61. 61  P mất cân bằng phải-trái (RL):  Bước 1: quay phải Q P  Bước 2: quay trái cây P Q h h h-1 h Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  62. 62  P mất cân bằng phải-trái (RL):  Bước 1: quay phải cây Q P Quay phải cây Q P Q Q h h h h h- 1 h h-1 h Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  63. 63  P mất cân bằng phải-trái (RL):  Bước 2: quay trái cây P P Quay trái cây P P Q h h h h- 1 h h h- 1 h Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  64. 64  P mất cân bằng phải-trái (RL) – Bước 1: P Quay phải cây Q 35 35 Q 40 18 50 18 8 20 40 55 8 20 37 50 37 45 65 36 45 55 36 65 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  65. 65  P mất cân bằng phải-trái (RL) - Bước 2: P Quay trái cây P 35 40 Q 18 40 35 50 37 50 45 55 8 20 18 37 36 45 55 8 20 36 65 65 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  66. 66  Khi một node cây xảy ra mất cân bằng bên trái (cây con trái chênh lệch với cây con phải hơn một đơn vị): (thực hiện đối xứng với trường hợp mất cân bằng bên phải)  Mất cân bằng trái-trái (LL) ◼ Quay phải  Mất cân bằng trái-trái (L-R) ◼ Quay trái ◼ Quay phải Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  67. 67 Theo Wikipedia Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  68. 68  Thực hiện hoàn toàn tương tự cây nhị phân tìm kiếm. 4 10 2 6 9 23 5 7 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  69. 69  Thực hiện tương tự với việc thêm phần tử của cây nhị phân tìm kiếm.  Nếu xảy ra việc mất cân bằng thì xử lý bằng các trường hợp mất cân bằng đã biết. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  70. 70  Thực hiện tương tự cây nhị phân tìm kiếm: xét 3 trường hợp, và tìm phần tử thế mạng nếu cần.  Sau khi xóa, nếu cây mất cân bằng, thực hiện cân bằng cây.  Lưu ý: việc cân bằng sau khi hủy có thể xảy ra dây chuyền. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  71. 71  Ví dụ: xóa 35 Phần tử thế mạng là 36 40 40 35 50 36 50 18 37 45 55 18 37 45 55 8 20 36 65 8 20 65 Cây vẫn cân bằng nên không phải hiệu chỉnh Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  72. 72  Xóa phần tử 45 40 40 36 50 36 50 18 37 45 55 18 37 55 8 20 65 8 20 65 Node 50 bị lệch phải !!! Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  73. 73  Xóa phần tử 45: cân bằng lại cây Quay trái tại node 50 40 40 55 36 50 36 50 65 18 37 55 18 37 8 20 65 8 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  74. 74 AA tree Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  75. 75  Được đặt tên theo tác giả Arne Anderson (Thụy Điển).  Công trình được công bố năm 1993 (Balanced Search Trees Made Simple). Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  76. 76  Mức của node  Liên kết ngang Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  77. 77  Mức của node:  Số liên kết trái từ node đó đến node NULL. ◼ Mức của NULL là 0. ◼ Mức của node lá là 1. Mức 2 15 Mức 1 5 10 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  78. 78  Liên kết ngang:  Liên kết giữa node cha và node con có cùng mức. 15 5 10 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  79. 79  Cây AA là cây nhị phân tìm kiếm thỏa mãn các tính chất sau: [1] Mức của node con trái bắt buộc phải nhỏ hơn mức của node cha. [2] Mức của node con bên phải nhỏ hơn hoặc bằng mức của node cha. Liên kết ngang bắt buộc hướng sang phải. [3] Mức của node cháu bên phải bắt buộc nhỏ hơn mức của node ông. Không tồn tại 2 liên kết ngang liên tiếp. [4] Mọi node có mức lớn hơn 1 phải có 2 node con. [5] Nếu một node không có liên kết ngang phải thì cả hai node con của nó phải cùng mức. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  80. 80 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 Mức của các node? Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  81. 81 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 So sánh mức của node con trái với mức của node cha trực tiếp của nó? Các cặp node: 15 và 30, 5 và 15, 50 và 70, 35 và 50, 55 và 60, 80 và 85 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  82. 82 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 Các liên kết ngang? Hướng của liên kết ngang? Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  83. 83 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 Có tồn tại 2 liên kết ngang liên tiếp? Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  84. 84 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 Mọi node có mức lớn hơn 1 đều có 2 node con? Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  85. 85 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 So sánh mức của các node con của các node: 15, 70, 60, 85? Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  86. 86  Skew  Split Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  87. 87  Skew:  Dùng để loại bỏ liên kết ngang trái. P X P X A B C A B C Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  88. 88  Split:  Dùng để loại bỏ 2 liên kết ngang liên tiếp P X P G X G A B C D A B C D Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  89. 89  Skew: dùng để loại bỏ liên kết ngang bên trái.  Split: dùng để loại bỏ 2 liên kết ngang (phải) liên tiếp.  Biến đổi theo thứ tự Skew -> Split (nếu có).  Khi thực hiện thao tác Split, node giữa được tăng thêm một mức. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  90. 90  Duyệt cây, Tìm kiếm:  Tương tự cây nhị phân tìm kiếm  Thêm phần tử  Xóa phần tử Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  91. 91  Thực hiện tương tự trên cây nhị phân tìm kiếm.  Phần tử được thêm vào luôn ở mức 1.  Sau khi thêm, thực hiện các thao tác Skew và/hoặc Split để đảm bảo tính chất của cây. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  92. 92  Vẽ cây AA theo thứ tự nhập sau đây: 4, 7, 6, 3, 5, 9, 15, 27, 8, 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  93. 93 6 4 9 27 3 5 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  94. 94  Hãy vẽ cây AA theo thứ tự nhập sau đây:  40, 8, 27, 15, 9, 5, 3, 6, 7, 4 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  95. 95 9 27 5 7 3 4 6 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  96. 96  Nếu không phải là node lá (mức của node là 1), tìm phần tử thế mạng:  Phần tử lớn nhất bên nhánh trái (node lá).  Xóa node lá:  Giảm mức của node cha nếu mức của node lá nhỏ hơn.  Thực hiện các thao tác Skew, Split cần thiết Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  97. 97  Xóa phần tử 8 6 4 9 27 3 5 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  98. 98  Xóa phần tử 8 6 4 9 27 3 5 7 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  99. 99  Xóa phần tử 5 6 4 9 27 3 5 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  100. 100  Xóa phần tử 5 6 4 9 27 Giảm mức của 4 3 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  101. 101  Xóa phần tử 5 6 3 4 9 27 Skew tại 4 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  102. 102  Xóa phần tử 5 Giảm mức 6 3 4 9 27 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  103. 103  Xóa phần tử 5 6 9 27 3 4 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  104. 104  Xóa phần tử 5 Split tại 6 6 9 27 3 4 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  105. 105  Xóa phần tử 5 9 6 27 3 4 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  106. 106 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  107. 107 1. Xây dựng giải thuật xóa một đỉnh với khóa cho trước ra khỏi cây nhị phân tìm kiếm. 2. Hãy chứng tỏ rằng trường hợp tìm kiếm trung bình cho cây nhị phân tìm kiếm là O(log2n)? Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  108. 108 3. Biểu diễn tình trạng cây nhị phân tìm kiếm sau khi thực hiện các thao tác sau:  Lần lượt thêm các node theo trình tự: M G B K S P D C A H L F X N T W R.  Xóa M.  Xóa S.  Cho biết kết quả sau khi duyệt cây theo các trình tự giữa, trước và sau. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  109. 109 4. Xây dựng giải thuật thực hiện các thao tác sau trên cây nhị phân tìm kiếm: - Đếm số node lá. - Tính độ cao cây. - Tính độ cao của 1 node trong cây. - Xuất ra các node có cùng độ cao. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  110. 110 5. Biểu diễn tình trạng cây cân bằng AVL/cây AA sau khi thực hiện các thao tác sau:  Lần lượt thêm các node theo trình tự: 13 7 2 11 19 16 4 3 1 8 12 6 24 14 20 23 18  Xóa 13.  Xóa 19 Lưu ý: cho biết các trường hợp mất cân bằng. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  111. 111 6. Hãy vẽ cây AVL với 12 nút có chiều cao cực đại trong tất cả các cây AVL 12 nút. 7. Tìm 1 dãy N khoá sao cho khi lần lượt dùng thuật toán thêm vào cây AVL sẽ phải thực hiện mỗi thao tác cân bằng (LL, LR, RL, RR) lại ít nhất 1 lần. Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  112. 112 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  113. 113 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  114. 114  Vẽ cây AA theo thứ tự nhập sau đây: 4, 7, 6, 3, 5, 9, 15, 27, 8, 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  115. 115 4 Thêm 4 Chuẩn bị: Thêm 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  116. 116 4 7 Thêm 7 Chuẩn bị: Thêm 6 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  117. 117 4 7 6 Thêm 6 Quan sát các liên kết mới thêm Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  118. 118 4 6 7 Thêm 6 Quay phải nút 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  119. 119 4 6 7 Kết quả sau khi quay phải nút 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  120. 120 4 6 7 Hai liên kết ngang liên tiếp Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  121. 121 6 4 7 Chuẩn bị: Thêm 3 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  122. 122 6 4 7 3 6 3 4 7 Thêm 3 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  123. 123 6 3 4 7 Chuẩn bị: Thêm 5 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  124. 124 6 3 4 7 5 Thêm 5 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  125. 125 6 3 4 5 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  126. 126 6 4 7 3 5 Mức hiện hành của 4, 6? Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  127. 127 4 6 3 5 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  128. 128 4 6 3 5 7 Chuẩn bị: Thêm 9 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  129. 129 4 6 3 5 7 9 Thêm 9 Chuẩn bị: Thêm 15 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  130. 130 4 6 3 5 7 9 15 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  131. 131 4 6 3 5 7 9 15 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  132. 132 4 6 3 5 9 7 15 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  133. 133 4 6 9 3 5 7 15 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  134. 134 6 4 9 3 5 7 15 Chuẩn bị: Thêm 27 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  135. 135 6 4 9 3 5 7 15 27 Thêm 27 Chuẩn bị: Thêm 8 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  136. 136 6 4 9 3 5 7 15 8 27 Thêm 8 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  137. 137 6 4 9 3 5 7 8 15 27 Chuẩn bị: Thêm 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  138. 138 6 4 9 3 5 7 8 15 27 40 Thêm 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  139. 139 6 4 9 3 5 7 8 15 27 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  140. 140 6 4 9 3 5 7 8 27 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011
  141. 141 6 4 9 27 3 5 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011