Chương 4: Cây

Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 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 2 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 3 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 4 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 5 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 6 Biểu diễn cây  Bằng đồ thị / A D C F B G E I H J A B D C G H E F I J K 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 giản đồ A B C F D G J E H I Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 8 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 ( B ( E, F( I, J, K) ), C ( G,H ), D ) ) / A D C F B G E I H J A B D C G H E F I J K Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 9 Biểu diễn cây  Bằng phương pháp Indentatio / A C F D G J B E H I / A D C F B G E I H J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 10 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) K L E F B G C M H I J D A Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 11 Các thuật ngữ  Đường đi (path) / A D C F B G E I H J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 12 Các thuật ngữ  Mức của nút và chiều cao của cây 1 2 3 4 5 Root Chiều cao của cây: 5 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 13 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 D C F B G E I H J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 14 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 15 Cây nhị phân  Định nghĩa Cây con trái Cây con phải Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 16 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 17 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 18 Cây nhị phân hoàn chỉnh / A D C B G E I G J 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 19 Cây nhị phân đầy đủ / A D C B E I 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 20 Cây nhị phân gần đầy / A D C B G E I G J 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 21 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 22 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 A D C B E I 0 1 2 3 4 5 6 R A E D I B C V[0] V[1] V[6] V[4] V[5] V[2] V[3] Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 23 Sử dụng liên kết R A B C D E G G Root Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 24 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 25 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 26 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 27 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 28 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 29 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 30 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 D C F B G E I H J R A C F D G J B E H I Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 31 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 32 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 A D C F B G E I H J F C A G J D R B H E I Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 33 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 34 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 D C F B G E I H J F C J G D A H I E B R Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 35 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 36 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 trái nhỏ hơn nút gốc  Các nút trên cây con phải lớn hơn nút gốc 44 18 37 13 5 88 23 93 98 90 30 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 37 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 38 Thêm một phần tử Thêm X= 50 44 18 88 13 37 59 108 15 23 40 55 71 X > 44 X < 88 X < 59 50 X < 55 root Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 39 Tìm một nút có khóa cho trước Tìm X = 55 44 18 88 13 37 59 108 15 23 40 55 71 X >44 X < 88 X < 59 root 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  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 41 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á 44 18 88 13 37 59 108 15 23 40 55 71 Xóa: X = 40 root Đơn giản : Xóa nút X, vì nó không móc nối đến nút nào khác 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 trái root 44 18 88 13 37 59 108 15 23 55 71 Xóa X=37 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 43 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 44 18 88 13 37 59 108 15 40 55 71 Xóa X=37 root Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 44 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 15 44 18 88 13 37 59 108 15 23 40 55 71 Xóa nút X=18 30 root Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 45 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 46 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 47 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 48 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 49 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 50 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 51 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 52 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 53 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 54 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 55 Q&A