Cấu trúc dữ liệu và giải thuật - Chương 5: Cấu trúc dữ liệu câu

Chương 5 Cấu trúc dữ liệu cây 5.1. Định nghĩa Câ là ột ấ t ú t đó b ồ á út đượy m c u r c rong ao g m c c n c liên kết với nhau theo hệ thống phân cấp, trong đó nút có cấp cao nhất được gọi là nút gốc và nút có cấp thấp nhất được gọi là các nút lá. 19/12/2008 2Cấu trúc dữ liệu 1 5.1. Định nghĩa 19/12/2008 3Cấu trúc dữ liệu 1 5.1. Định nghĩa • Thuật ngữ: - Nút cha (parents node) của một node là nút có cấp cao hơn nó một bậc. - Nút con (child node) của một node là nút có cấp nhỏ hơn nó một bậc. - Nút gốc (root) là nút không có nút cha. - Nút lá (leaf – leaves) là nút không có nút con. - Cấp của 1 nút (level of a node) là các liên kết để đi từ nút gốc đến nút đó. 19/12/2008 4Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 1 Khái niệm về cây nhị phân. . . ỗCây nhị phân là một cây mà m i nút có không quá 2 nút con 19/12/2008 5Cấu trúc dữ liệu 1 5 2 2 Cây nhị phân tìm kiếm 5.2. Cây nhị phân tìm kiếm . . . Cây nhị phân tìm kiếm là một cây nhị phân trong đó nút của nó được tổ chức để luôn thỏa tính chất sau đây “Giá trị của nút cha luôn lớn hơn giá trị tất cả nút con bên trái và nhỏ hơn giá trị của tất cả nút con bên phải”. 19/12/2008 6Cấu trúc dữ liệu 1 5 2 2 Cây nhị phân tìm kiếm 5.2. Cây nhị phân . . . 19/12/2008 7Cấu trúc dữ liệu 1 5 2 2 Cây nhị phân tìm kiếm 5.2. Cây nhị phân . . . Biểu diễn cây nhị phân tìm kiếm struct Node { int key; Node * left, * right; }; typedef Node *pNode; t t Ts ruc ree { pNode root; 19/12/2008 8Cấu trúc dữ liệu 1 }; 5 2 2 Cây nhị phân tìm kiếm 5.2. Cây nhị phân . . . Các thao tác trên cây nhị phân tìm kiếm Khởi tạo cây id iti l ( t)vo In a Tree & { t.root = NULL; } Kiểm tra cây rỗng int isEmpty (Tree t) { return (t root == NULL); 19/12/2008 9Cấu trúc dữ liệu 1 . } 5 2 2 Cây nhị phân tìm kiếm 5.2. Cây nhị phân . . . Các thao tác trên cây nhị phân tìm kiếm Thêm một nút vào cây Giả sử cần thêm 1 nút có khóa k vào cây t. - So sánh với nút gốc: nếu nhỏ hơn thì sang trái lớn hơn, thì sang phải. - So sánh với nút gốc của cây con bên trái (phải) và lặp lại quá trình trên cho đến khi tìm được vị trí thích hợp. 19/12/2008 10Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Các thao tác trên cây nhị phân tìm kiếm Thê ộ ú à âm m t n t v o c y int Ins (pNode &r, int k) { //if (!r) r==NULL { pNode p = new Node; p > key = k;- p -> left = p -> right = NULL; r = p; return 1; } if (r -> key == k)return 0; if (r -> key > k) return Ins (r->left,k); 19/12/2008 11Cấu trúc dữ liệu 1 else return Ins (r->right,k); } 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Các thao tác trên cây nhị phân tìm kiếm Thêm một nút vào cây i t t ( t i t k)n Inser Tree & , n { return Insert (t.root,k); } 19/12/2008 12Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Các thao tác trên cây nhị phân tìm kiếm Thêm một nút vào cây i t t ( t i t k)n Inser Tree & , n { return Ins (t.root,k); } 19/12/2008 13Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Các thao tác trên cây nhị phân tìm kiếm Tạo cây void CreateTree (Tree &t) { int k; do { cout>k; if (k!=-1) if (Insert(t k)), cout<<"Thanh cong"<<endl; else cout<<"Nut da co trong cay"<<endl; 19/12/2008 14Cấu trúc dữ liệu 1 }while (k!=-1); } 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Các thao tác trên cây nhị phân tìm kiếm Duyệt cây NLR (Node – Left – Right): 44 18 13 15 37 23 40 88 59 55 71 108 LNR (Left – Node – Right): 13 15 18 23 37 40 44 55 59 71 88 108 LRN (Left – Right – Node): 15 13 23 40 37 18 55 71 59 108 88 44 19/12/2008 15Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Các thao tác trên cây nhị phân tìm kiếm Duyệt cây void LNR (pNode r) { if (!r) return; lnr(r->left); coutkey<<" "; lnr(r->right); } void LNR(Tree t) { LNR(t t) 19/12/2008 16Cấu trúc dữ liệu 1 .roo ; } 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Các thao tác trên cây nhị phân tìm kiếm Tìm khóa k có trong cây hay không int Search(pNode r,int k) { if (!r) return 0; if (r->key == k) return 1; if (r->key > k) return Search(r->left,k); else return Search(r->right,k); } int Search(Tree t,int k) { 19/12/2008 17Cấu trúc dữ liệu 1 return Search(t.root,k); } 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Các thao tác trên cây nhị phân tìm kiếm Xóa một nút X - X là nút lá: chỉ đơn giản hủy X vì nó không móc nối đế hầ à khán p n tử n o c. 19/12/2008 18Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Các thao tác trên cây nhị phân tìm kiếm Xóa một nút X - X chỉ có 1 nút con: trước khi hủy X ta móc nối cha của ới d hấ óX v con uy n t của n . 19/12/2008 19Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Các thao tác trên cây nhị phân tìm kiếm Xóa một nút X - X có đủ cả 2 con: không thể hủy trực tiếp do X có đủ 2 ế ầcon⇒ hủy gián ti p. Thay vì hủy X, ta sẽ tìm một ph n tử thế mạng Y. Phần tử này có tối đa một con. Thông tin l t i Y ẽ đ h ể lê l t i X S đó út bịưu ạ s ược c uy n n ưu ạ . au , n hủy thật sự sẽ là Y giống như 2 trường hợp đầu. Vấn đề là phải chọn Y sao cho khi lưu Y vào vị trí của X cây, vẫn là CNPTK. Có 2 phần tử thỏa mãn yêu cầu: + Phần tử nhỏ nhất (trái nhất) trên cây con phải 19/12/2008 20Cấu trúc dữ liệu 1 . + Phần tử lớn nhất (phải nhất) trên cây con trái. 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Có thể dùng 15 để thế mạng 19/12/2008 21Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 2 Cây nhị phân tìm kiếm. . . Có thể dùng 15 để thế mạng 19/12/2008 22Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 3 Cây nhị phân cân bằng. . . Định nghĩa Cây cân bằng hoàn toàn là cây nhị phân tìm kiếm mà tại mỗi nút của nó, số nút của cây con trái chênh lệch kh á ới ố ú h iông qu một so v s n t của cây con p ả . Cây Cân Bằng Hoàn Toàn Cây CCBHT thì h ~ log2n 19/12/2008 23Cấu trúc dữ liệu 1 Cây nhị phân tìm kiếm cân bằng hoàn toàn 5.2. Cây nhị phân 5 2 3 Cây nhị phân cân bằng. . . Nhận xét •Một cây rất khó đạt được trạng thái cân bằng hoàn toàn và cũng rất dễ mất cân bằng vì khi thêm hay hủy các nút trên cây có thể ấ ằ ấ ấ ằlàm cây m t cân b ng (xác su t r t lớn), chi phí cân b ng lại cây lớn vì phải thao tác trên toàn bộ cây. • Trong trường hợp xấu nhất ta chỉ phải tìm qua log n phần tử (n2 là số nút trên cây). • Do CCBHT là một cấu trúc kém ổn định nên trong thực tế không thể sử dụng. Nhưng ưu điểm của nó lại rất quan trọng. Vì vậy, cần đưa ra một CTDL khác có đặc tính giống CCBHT nhưng ổn định h 19/12/2008 24Cấu trúc dữ liệu 1 ơn. 5.2. Cây nhị phân 5 2 3 Cây nhị phân cân bằng. . . CâyAVL (Adelson – Velskii – Landiis) Định nghĩa: Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi nút của nó độ cao của cây con trái và của cây con phải chênh lệch không quá một. Cây AVL 19/12/2008 25Cấu trúc dữ liệu 1 Cây nhị phân tìm kiếm cân bằng AVL 5.2. Cây nhị phân 5 2 3 Cây nhị phân cân bằng. . . CâyAVL (Adelson – Velskii – Landiis) Khai báo: struct Node { int key; int bal; //-1: lệch trái, 0: cân bằng, 1: lệch phải Node *left,*right; }; 19/12/2008 26Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 3 Cây nhị phân cân bằng. . . CâyAVL (Adelson – Velskii – Landiis) Khai báo: typedef Node *pNode; struct AVLTree { pNode root; }; 19/12/2008 27Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 3 Cây nhị phân cân bằng. . . CâyAVL (Adelson – Velskii – Landiis) Các trường hợp mất cân bằng: • Trường hợp 1: cây T lệch về bên trái (có 3 khả năng) 19/12/2008 28Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 3 Cây nhị phân cân bằng. . . CâyAVL (Adelson – Velskii – Landiis) Các trường hợp mất cân bằng: • Trường hợp 2: cây T lệch về bên phải (có 3 khả năng) 19/12/2008 29Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 3 Cây nhị phân cân bằng. . . CâyAVL (Adelson – Velskii – Landiis) Các trường hợp mất cân bằng: • Hướng giải quyết của 2 trường hợp là tương tự nhau nên ta chỉ giải quyết Trường hợp 1 19/12/2008 30Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 3 Cây nhị phân cân bằng. . . CâyAVL (Adelson – Velskii – Landiis) Các trường hợp mất cân bằng: 19/12/2008 31Cấu trúc dữ liệu 1 5.2. Cây nhị phân 5 2 3 Cây nhị phân cân bằng. . . CâyAVL (Adelson – Velskii – Landiis) Các trường hợp mất cân bằng: 19/12/2008 32Cấu trúc dữ liệu 1