Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 3: Cấu trúc cây

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 3: Cấu trúc cây

1. Giảng viên: Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến 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 ©FIT-HCMUS 1
2. 3 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 ©FIT-HCMUS 2
3. 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 Sơ đồ tổ chức Cây thư mục Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 3
4. 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 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 ©FIT-HCMUS 4
5. 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 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 ©FIT-HCMUS 5
6. 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 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 ©FIT-HCMUS 6
7. 13 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 ©FIT-HCMUS 7
8. 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 Duyệt theo chiều sâu Duyệt trước • a b d e i j c f g k h Duyệt giữa b c • d b i e j a f c k g h d e f g h Duyệt sau • d i j e b f k g h c a i j k Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 8
9. 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 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 ©FIT-HCMUS 9
10. 19 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 ©FIT-HCMUS 10
11. 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 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 ©FIT-HCMUS 11
12. 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 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 ©FIT-HCMUS 12
13. 25 Binary tree Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 ©FIT-HCMUS 13
14. 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  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 ©FIT-HCMUS 14
15. 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  Đặ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 ©FIT-HCMUS 15
16. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 ©FIT-HCMUS 16
17. 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  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 ©FIT-HCMUS 17
18. 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  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 ©FIT-HCMUS 18
19. 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  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 ©FIT-HCMUS 19
20. 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 P Quay trái cây P P Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 20
21. 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 Quay phải cây P P P Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 21
22. 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  Đố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 ©FIT-HCMUS 22
23. 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  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 ©FIT-HCMUS 23