Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Cây - Nguyễn Thị Khiêm Hòa

Chương 4: Cây Giảng viên: Ths. Nguyễn Thị Khiêm Hòa Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM Nội dung  Định nghĩa và các khái niệm  Cây nhị phân  Cây nhị phân tìm kiếm  Cây tổng quát Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 2 Mục tiêu  Trang bị khái niệm và ứng dụng trên Cây  Cài đặt các thuật toán trên cây, đặc biệt là cây nhị phân tìm kiếm. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 3 Khái niệm  Cây là tập hữu hạn các nút (Tree node):  Có một nút gốc (root)  Các nút còn lại phân hoạch thành n tập riêng biệt T1, T2, , Tn, với Ti là một cây  Giữa các nút có quan hệ phân cấp (hierarchical relationship) “cha con”.  Cây không có nút là cây rỗng (null tree). Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 4 Biểu diễn cây  Bằng đồ thị  Bằng giản đồ  Bằng danh sách (các dấu ngoặc lồng nhau)  Bằng phương pháp Identatio Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 5 Biểu diễn cây  Bằng đồ thị A / B C D A B C D E E F G H F G H I I J K J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 6 Biểu diễn cây  Bằng giản đồ D B A J G H I E C F Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 7 Biểu diễn cây  Bằng danh sách (các dấu ngoặc lồng nhau) (/( A (C (F), D (G ( J ) ) ) ), (B (E ( H, I ) ) ) ) A / A B B C D C D E E F G H F G H I J I J K Khoa Công nghệ Thông( tinA - (Đại B học ( Ngân E, hàngF( TP.HCMI, J, K) ), C ( G,H ), D ) ) 8 Biểu diễn cây  Bằng phương pháp Indentatio / A C / F A B D G C D E J B F G H I E H J I Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 9 Các thuật ngữ  Bậc của nút và bậc của cây  Nút gốc, Nút lá và nút nhánh  Nút cha (Parent), nút con (children) A B C D E F G H I J K L M Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 10 Các thuật ngữ  Đường đi (path) / A B C D E F G H I J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 11 Các thuật ngữ  Mức của nút và chiều cao của cây Root 1 2 Chiều cao 3 của cây: 5 4 5 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 12 Các thuật ngữ  Tổ tiên (ancestors) của một nút  Con cháu (Descendant) của một nút:  Các con của cùng một cha gọi là anh em ruột (siblings) / A B C D E F G H I J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 13 Cây có thứ tự và Rừng  Cây có thứ tự (ordered tree)  Một cây gọi là có thứ tự khi ta thay đổi vị trí của các cây con, ta nhận được một cây mới  Rừng (forest)  Tập hợp hữu hạn các cây phân biệt  Nếu bỏ đi nút gốc của một cây, ta sẽ thu được một rừng gồm nhiều cây phân biệt Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 14 Cây nhị phân  Định nghĩa Cây con Cây con trái phải Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 15 Cây nhị phân  Cây nhị phân biểu diễn biểu thức toán học Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 16 Tính chất của cây nhị phân  Số nút tối đa mức i trong cây 2i-1  Số nút tối đa trong cây là 2h-1 (h chiều cao của cây)  Chiều cao của cây h  log2N (N là số nút trong cây). 1 2 3 4 5 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 17 Cây nhị phân hoàn chỉnh / A B C D I E G J G Các nút ứng với các mức trừ mức cuối đều đạt tối đa, ở mức cuối, các nút đều đạt về phía trái Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 18 Cây nhị phân đầy đủ / A B C D I E Các nút đạt tối đa ở cả mọi mức Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 19 Cây nhị phân gần đầy / A B C D I E J G G Các nút ứng với các mức trừ mức cuối đều đạt tối đa, ở mức cuối, các nút không dạt đều về phía trái Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 20 Tổ chức lưu trữ cây nhị phân  Sử dụng mảng một chiều (lưu trữ kế tiếp)  Đánh số thứ tự từ gốc, tại mỗi mức, đánh số các nút từ trái sang phải, từ mức thấp đến mức cao  Sử dụng liên kết  Quản lý cây thông qua nút gốc (root)  Mỗi nút cấp phát động, bao gồm dữ liệu và địa chỉ hai cây con pLeft, pRight, liên kết tới cây con trái và cây con phải  Nút lá có hai liên kết trái phải đều rỗng Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 21 Lưu trữ kế tiếp cây nhị phân  Con của nút thứ i là nút thứ 2i+1 và 2i+2  Cha của nút thứ j là nút [(j-1)/2] R 0 1 2 A B 3 4 5 6 C D I E R A B C D I E V[0] V[1] V[2] V[3] V[4] V[5] V[6] Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 22 Sử dụng liên kết Root R A B C D E G G Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 23 Sử dụng liên kết  Cấu tạo của nút  Tạo lập bằng cách cấp phát bộ nhớ động  Mỗi nút gồm có các thông tin:  Dữ liệu (data)  Địa chỉ 2 cây con pLeft, pRight liên kết đến nút con trái và nút con phải Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 24 Cây nhị phân public class Node: IComparable > where T: IComparable { private T data; private Node left; private Node right; public Node(T data) { this.data = data; this.left = this.right = null; } //Đóng gói DL //các phương thức } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 25 Cây nhị phân //Đóng gói dữ liệu: Properties public T Data { get{ return this.data;} set{ this.data = value;} } public Node Left { get { return this.left; } } public Node Right { get { return this.right; } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 26 Cây nhị phân //các phương thức dùng để so sánh sắp xếp public int CompareTo(Node rhs) { return data.CompareTo(rhs.data); } public bool Equals(Node rhs) { return this.data.Equals(rhs.data); } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 27 Cây nhị phân public class BinTree where T: IComparable { private Node root; public BinTree() { this.root = null; } //các phương thức } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 28 Phép duyệt cây nhị phân (Binary Tree Traversing)  Định nghĩa  Là phép xử lý các nút trên cây, mỗi nút một lần  Duyệt cây theo thứ tự trước (preorder)  Duyệt cây theo thứ tự giữa (inorder)  Duyệt cây theo thứ tự sau (postorder) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 29 Phép duyệt cây nhị phân (Binary Tree Traversing)  Duyệt cây theo thứ tự trước (NLR)- Đệ qui  Thăm gốc  Duyệt cây con trái theo thứ tự trước  Duyệt cây con phải theo thứ tự trước R A B R A C F D G J B E H I C D E F G H II J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 30 Cây nhị phân //In danh sách public void PrintTree(Node root) { if(root != null) { Console.Write("{0} ", root.data); PrintTree(root.left); PrintTree(root.right); } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 31 Phép duyệt cây nhị phân (Binary Tree Traversing)  Duyệt cây theo thứ tự giữa (LNR)- Đệ qui  Duyệt cây con trái theo thứ tự giữa  Thăm gốc  Duyệt cây con phải theo thứ tự giữa R F C A G J D R B H E I A B C D E F G HH II J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 32 Cây nhị phân //In danh sách public void PrintTree(Node root) { if(root != null) { PrintTree(root.left); Console.Write("{0} ", root.data); PrintTree(root.right); } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 33 Phép duyệt cây nhị phân (Binary Tree Traversing)  Duyệt cây theo thứ tự sau (LRN)- Đệ qui  Duyệt cây con trái theo thứ tự sau  Duyệt cây con phải theo thứ tự sau  Thăm gốc R A B C D E F G H II J Khoa Công nghệF ThôngC tin - JĐại họcG Ngân hàngD TP.HCMA H I E B R 34 Cây nhị phân //In danh sách public void PrintTree(Node root) { if(root != null) { PrintTree(root.left); PrintTree(root.right); Console.Write("{0} ", root.data); } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 35 Cây nhị phân tìm kiếm (BST_Binary Search Tree)  Định nghĩa  Cây nhị phân  Mỗi nút có 1 khóa duy nhất  Các nút trên cây con 44 trái nhỏ hơn nút gốc  Các nút trên cây con 18 88 phải lớn hơn nút gốc 13 37 93 5 23 90 98 Khoa Công nghệ Thông tin - Đại học Ngân hàng30 TP.HCM 36 Thao tác trên cây nhị phân tìm kiếm  Thêm vào phần tử  Tìm nút  Xóa một nút  Tìm nút có khóa nhỏ nhất  Tìm nút có khóa lớn nhất  Giải phóng cây Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 37 Thêm một phần tử root Thêm X= 50 44 X > 44 18 X < 88 88 13 37 59 108 X < 59 15 23 40 55 71 X < 55 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 50 38 Tìm một nút có khóa cho trước Tìm X = 55 root 44 X >44 18 88 X < 88 13 37 59 108 X < 59 15 23 40 55 71 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 39 Xóa một nút trên cây nhị phân tìm kiếm  Xóa một nút trên cây nhị phân tìm kiếm, có ba trường hợp:  Nút cần xóa là nút lá.  Nút cần xóa chỉ có 1 con (trái hoặc phải).  Nút cần xóa có đủ cả 2 con Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 40 Xóa một nút trên cây nhị phân tìm kiếm  Trường hợp 1 :Nút cần xóa là nút lá root 44 Xóa: X = 40 Đơn giản : 18 88 Xóa nút X, vì nó không móc nối đến nút 13 37 59 108 nào khác 15 23 40 55 71 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 41 Xóa một nút trên cây nhị phân tìm kiếm  Trường hợp 2: Nút cần xóa có một cây con trái root 44 Xóa X=37 18 88 13 37 59 108 15 23 55 71 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 42 Xóa một nút trên cây nhị phân tìm kiếm  Trường hợp 2: Nút cần xóa có một cây con phải root 44 Xóa X=37 18 88 108 13 37 59 15 Khoa Công nghệ Thông tin40 - Đại học Ngân hàng TP.HCM55 71 43 Xóa một nút trên cây nhị phân tìm kiếm  Trường hợp 3 : Nút cần xóa có hai cây con trái và phải 44 root Xóa nút X=18 18 88 15 13 37 59 108 15 23 40 55 71 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 30 44 Cây M_phân (M_ary)  Định nghĩa  Cây m phân là cây mà mỗi nút có tối đa m nút con (cây con)  Biểu diễn cây m phân bằng liên kết động  Mỗi nút có m+1 trường, với m mối nối  Với cây m phân đầy đủ, có n(m-1)+1 mối liên kết NULL  Cây m phân đầy đủ có chiều cao logmN (N:số nút) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 45 Cây M phân  Phép duyệt cây tổng quát LNR(T)  Nếu T rỗng, dừng  Ngược lại, T1,,Tn là cây con gốc T  LNR(T1), T1 cây con thứ nhất của gốc T  Thăm gốc của T  Duyệt cây con T2,,Tn của T theo thứ tự giữa Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 46 Cây M_phân  Phép duyệt cây tổng quát LRN(T)  Nếu T rỗng, dừng  Ngược lại, T1,,Tn là cây con gốc T  LNR(T1), T1 cây con thứ nhất của gốc T  Duyệt cây con T2,,Tn của T theo thứ tự giữa  Thăm gốc của T Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 47 Cây M_phân  Duyệt cây theo mức  Duyệt cây theo chiều rộng  Ý tưởng  Tổ chức thành một hàng đợi  Đưa nút gốc vào hàng đợi  Lặp . Lấy một nút ra khỏi hàng đợi . Duyệt nút T . Đưa các nút con của T (nếu có) vào hàng đợi Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 48 Cây M_phân tìm kiếm  Tương tự cây nhị phân tìm kiếm trong đó mỗi nút có thể có m nút con.  M càng lớn thì bậc của cây càng thấp.  Cây m phân tìm kiếm cân bằng: B_cây Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 49 B_Cây  B-Tree bậc M là cây M-Phân tìm kiếm có các tính chất:  Mỗi node (ngoại trừ gốc) có ít nhất M/2 node con.  Node gốc (nếu không phải nút lá) có ít nhất 2 nút con.  Mọi nút lá đều nằm cùng một mức.  Các khóa và cây con duợc sắp xếp theo cây tìm kiếm. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 50 B_Cây_Ứng dụng  Hạn chế số thao tác đọc mỗi lần tìm kiếm trên cây  Thích hợp cho việc tìm kiếm trên bộ nhớ ngoài  Chiều cao cây = logMN  chiều cao cây giảm rất nhanh. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 51 B Cây_Tìm kiếm  Tương tự cây nhị phân tìm kiếm Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 52 B Cây_Thêm nút vào cây  Ý tưởng: Tìm vị trí thích hợp để thêm vào cây. Nút thêm vào sẽ là nút lá.  Nếu nút lá chưa đầy  thêm vào  Nếu đầy: phân đôi nút lá  Chuyển phần tử giữa lên nút cha  Hai bên của nút lá thành hai nhánh con  Việc phân đôi có thể lan truyền. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 53 B Cây_Thêm nút vào cây  Thực hiện thêm các nút sau vào B_cây bậc 5: 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 Kết quả: Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 54 Q&A Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 55