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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:40

Thêm vào BST

Báo xấu

31
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật: Cấu trúc cây" trình bày các nội dung: 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. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

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ấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 1
3 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 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 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 2
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 2015 6 Sơ đồ tổ chức Cây thư mục Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 3
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 2015 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 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 4
9  node: đỉnh  parent (của node n): node cha của node n. Node phía trên trực tiếp của node n trong cây.  child (của node n): node con của node n. Node phía dưới trực tiếp của node n trong cây.  root: gốc cây. Node duy nhất không có node cha  leaf: node lá. Node không có node con.  path: đường đi Cấu trúc dữ liệu và giải thuật - HCMUS 2015 10  siblings: các node cùng node cha.  ancestor (của node n): node trên đường đi từ node gốc đến node n.  descendant (của node n): node trên đường đi từ node n đến node lá.  subtree (của node n): cây con. Cây bao gồm 1 node con của node n và các node “hậu duệ” của node này. Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 5
11 Nút gốc r1 r2 rk k1 k2 T1 T2 Tk k3 k4 k5 Cây con Nút lá Đường đi k6 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 12  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 node của cây.  depth/level: độ sâu/mức  Mức (độ sâu) của node:  Nếu node n là node gốc:  level(n) = 1  Nếu node n không phải là node gốc:  level(n) = 1 + level(parent(n)). Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 6
13  height: chiều cao. Số lượng node trên đường đi dài nhất từ node gốc đến node lá.  Chiều cao cây:  Nếu cây T rỗng: height(T) = 0  Nếu cây T khác rỗng: height (T) = max{level(Ni)}, NiT  Chiều cao cây:  Nếu cây T rỗng: height(T) = 0  Nếu cây T khác rỗng: height(T) = 1 + max{height(Ti)}, Ti là cây con của T Cấu trúc dữ liệu và giải thuật - HCMUS 2015 14 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 k6 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 7
15 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 16  Đả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 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 8
17 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 2015 18 Duyệt theo chiều sâu Duyệt trước • abdeijcfgkh Duyệt giữa b c • dbiejafckgh d e f g h Duyệt sau • dijebfkghca i j k Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 9
19 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 2015 20 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 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 10
21 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 22 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 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 11
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 2015 24 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 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 12
25 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 2015 26 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 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 13
27 Binary tree Cấu trúc dữ liệu và giải thuật - HCMUS 2015 28  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 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 14
29  Cây nhị phân hoàn chỉnh (complete binary tree)  Cây nhị phân có chiều cao là h thì có đầy đủ các node từ mức 1 đến mức h-1. Các node ở mức h sẽ được lấp từ trái sang phải.  Cây nhị phân đầy đủ (full binary tree)  Cây nhị phân có chiều cao là h thì tất cả các node nằm ở mức từ 1 đến h-1 đều có 2 node con. Cấu trúc dữ liệu và giải thuật - HCMUS 2015 30 a b c b c d e f g d e f g h i j Cây nhị phân hoàn chỉnh Cây nhị phân đầy đủ Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 15
31  Heap là một cây nhị phân hoàn chỉnh:  Max-heap: Node cha có giá trị lớn hơn hoặc bằng node con.  Min-heap: Node cha có giá trị nhỏ hơn hoặc bằng node con. Cấu trúc dữ liệu và giải thuật - HCMUS 2015 32  Chiều cao tối thiểu của một cây nhị phân gồm N node?  Chiều cao tối đa của một cây nhị phân gồm N node? Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 16
33  Số node tối thiểu trên cây nhị phân có chiều cao h?  Số node tối đa trên cây nhị phân có chiều cao h? Cấu trúc dữ liệu và giải thuật - HCMUS 2015 34  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 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 17
35  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 node gốc lớn hơn tất cả khóa của các node thuộc cây con trái. 2. Khóa của node gốc nhỏ hơn tất cả khóa của các node thuộc cây con phải. 3. Cây con trái và cây con phải của node gốc là cây nhị phân tìm kiếm. Cấu trúc dữ liệu và giải thuật - HCMUS 2015 36 4 10 2 6 9 23 5 7 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 18
37  Đặ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 2015 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 19
39  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 2015 40  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 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 20