Cấu trúc dữ liệu - Chương 6: Cấu trúc cây (Tree)

Cấu trúc cây (Tree) Chương 6 Cây nhiều nhánh4 Các khái niệm cơ bản1 Cây nhị phân tìm kiếm2 Cây nhị phân cân bằng3 Nội dung 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Ví dụ: bài toán đưa thư  Có một bức thư cần chuyển đến địa chỉ “Nguyễn Văn A, 10 Huỳnh Văn Nghệ, Biên hoà, Đồng Nai, Việt nam”  Trên thế giới hiện có khoảng 8 tỷ người  Làm thế nào để tìm ra người A nhanh nhất?  Dùng cấu trúc mảng ??  Dùng danh sách liên kết ?? Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Ví dụ: cây thư mục windows Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Ví dụ: cây biểu thức (a+b)/(c-d) Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Ví dụ: cây quyết định Các khái niệm cơ bản Nhiệt độ Có Đau đầu Bình thường Cao Rất cao Đau đầukhông không Có không có {e2} không{e5} có {e3} không {e6} {e1, e4} {e2, e5} {e3,e6} Đau đầu Nhiệt độ Cúm e1 Có Bình thường Không e2 Có Cao Có e3 Có Rất cao Có e4 Không Bình thường Không e5 Không Cao Không e6 Không Rất cao Không 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Định nghĩa  Một cây (Tree) là:  Một tập các phần tử, gọi là các nút (Node): p1,p2,…,pN  Nếu N=0, cây gọi là cây rỗng (NULL)  Nếu N>0: • Tồn tại duy nhất 1 nút pk gọi là gốc của cây • Các nút còn lại được chia thành m tập không giao nhau: T1, T2, …, Tm • Mỗi là 1 cây con của cây Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Ví dụ: cây nhiều nhánh Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Nút (Node): là 1 phần tử trong cây. Mỗi nút có thể chứa 1 dữ liệu bất kỳ  Nhánh (Branch): là đoạn nối giữa 2 nút  Nút cha (Parent node)  Nút con (Child node)  Nút anh em (Sibling nodes): là những nút có cùng nút cha Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Bậc của 1 nút pi: là số nút con của pi  Ví dụ trên : Bậc (a) = 4; Bậc (j) = 3; Bậc (g) = 2; Bậc (k) = 1; Bậc (c) = 0  Nút gốc (Root node): nút không có nút cha  Nút lá (Leaf node, hay nút ngoài – External node): là nút có bậc = 0 (không có nút con)  Nút nội (Internal node): là nút có nút cha và có nút con  Cây con (Subtree) Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Bậc của cây: là bậc lớn nhất của các nút trong cây  Bậc () = max {bậc (pi) / pi Î }  Bậc của cây ?  Đường đi (Path) giữa nút pi đến nút pj: là dãy các nút liên tiếp từ pi đến pj sao cho giữa hai nút kề nhau đều có nhánh  Path(a, d) ? Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Mức (Level):  Mức (p) = 0 nếu p = root  Mức (p) = 1 + Mức (Cha (p)) nếu p!=root  Chiều cao của cây (Height - hT): đường đi dài nhất từ nút gốc đến nút lá  hT = max {Path(root, pi) / pi là nút lá Î } Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các khái niệm cơ bản 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các khái niệm cơ bản  Cây đầy đủ (Full tree): là 1 cây thoả • Tất cả các nút lá đều nằm trên cùng 1 mức • Tất cả những nút khác có cùng bậc với cây • Mức h của cây đầy đủ bậc d có dh nút VD. mức h=2 của cây bậc 3 có bao nhiêu nút ? • h mức đầu tiên của cây đầy đủ bậc d có số nút là: 1 + d + d2 + d3 + … + dh-1 = (dh - 1)/(d – 1) 3 mức đầu tiên của cây đầy đủ bậc 3 có bao nhiêu nút ? 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các khái niệm cơ bản  Cây hoàn chỉnh (Complete tree) với h mức: là 1 cây thoả các điều kiện • Những nút từ mức 0 đến mức h-1 đều đầy đủ • Những nút ở mức h được thêm vào cây từ trái sang phải 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân  Cây nhị phân là cây có bậc = 2  Độ cao của cây nhị phân có N nút: • hT(max) = N • hT(min) = [logN] + 1 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân  Cấu trúc lưu trữ dùng mảng Định nghĩa các cấu trúc dữ liệu typedef struct NODE { int Data; int Left; // chỉ số nút con trái int Right; // chỉ số nút con phải } NODETYPE; // cấu trúc 1 node // cây nhị phân có N nút NODETYPE tree[N]; 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân  Cấu trúc lưu trữ dùng con trỏ Định nghĩa các cấu trúc dữ liệu typedef struct NODE { int Data; NODE *pLeft; // con trỏ đến nút con trái NODE *pRight; // con trỏ đến nút con phải } NODETYPE; // binary tree node typedef struct BIN_TREE { int Count; // Số nút trong cây NODETYPE *pRoot; // con trỏ đến nút gốc }; // binary tree 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân  Cấu trúc lưu trữ dùng con trỏ 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân  Có 3 cách duyệt cây: • Duyệt gốc trước (Pre-Order) NLR • Duyệt gốc giữa (In-Order) LNR • Duyệt gốc sau (Post-Order) LRN 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân  Duyệt gốc trước (Pre-Order) NLR void NLR(const NODETYPE *pCurr) { if (pCurr==NULL) return; “Xử lý nút gốc pCurr” NLR(pCurr->pLeft); NLR(pCurr->pRight); } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân  Duyệt gốc giữa (In-Order) LNR void LNR(const NODETYPE *pCurr) { if (pCurr==NULL) return; LNR(pCurr->pLeft); “Xử lý nút gốc pCurr” LNR(pCurr->pRight); } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân  Duyệt gốc sau (Post-Order) LRN void LRN(const NODETYPE *pCurr) { if (pCurr==NULL) return; LRN(pCurr->pLeft); LRN(pCurr->pRight); “Xử lý nút gốc pCurr” } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây 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 • Mỗi nút p của cây đều thỏa:  Tất cả các nút thuộc cây con trái (p->pLeft) đều có giá trị nhỏ hơn giá trị của p: q  p->pLeft: q->Data Data  Tất cả các nút thuộc cây con phải (p->pRight) đều có giá trị lớn hơn giá trị của p : q  p->pRight: q->Data > p->Data 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân tìm kiếm 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm  Khởi tạo cây rỗng void BSTCreate(BIN_TREE &t) { t.Count = 0; // Số nút trong cây t.pRoot = NULL; // Con trỏ đến nút gốc }  Kiểm tra cây rỗng int BSTIsEmpty(const BIN_TREE &t) { if (t.pRoot==NULL) return 1; return 0; } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm  Tìm kiếm một phần tử NODETYPE *BSTSearch(const NODETYPE *pCurr, int Key) { if (pCurr==NULL) return NULL; // Không tìm thấy if (pCurr->Data==Key) return pCurr; // Tìm thấy else if (pCurr->Data > Key) // Tìm trên cây con trái return BSTSearch(pCurr->pLeft, Key); else // Tìm trong cây con phải return BSTSearch(pCurr->pRight, Key); } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm  Xoá một phần tử • Thao tác xóa 1 phần tử:  Áp dụng giải thuật tìm kiếm để xác định nút chứa phần tử cần xóa  Nếu tìm thấy, xóa phần tử đó khỏi cây • Các trường hợp xảy ra:  Xóa 1 nút không có nút con  Xóa 1 nút có 1 nút con  Xóa 1 nút có 2 nút con 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm  Xoá một nút không có nút con 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm  Xoá một nút có một nút con 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm  Xoá một nút có một nút con 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm  Xoá một nút có hai nút con 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm  Xoá một nút có hai nút con 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm  Thao tác • Xóa 1 phần tử pCurr có 2 nút con: • Thay vì xóa trực tiếp nút pCurr…ta tìm 1 phần tử thay thế p,  là phần tử lớn nhất trong cây con bên trái; hoặc  là phần tử nhỏ nhất trong cây con bên phải • Copy nội dung của p sang pCurr • Xóa nút p. 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm int BSTDelete(NODETYPE *&pCurr, int Key) { if (pCurr==NULL) return 0; // Không tìm thấy if (pCurr->Data > Key) // Xóa trên cây con trái return BSTDelete(pCurr->pLeft, Key); else if (pCurr->Data < Key) //Xóa trên cây phải return BSTDelete(pCurr->pRight, Key); // Tìm thấy nút cần xóa pCurr Xóa ! _Delete(pCurr); return 1; } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm void _Delete(NODETYPE *&pCurr) { NODETYPE *pTemp = pCurr; if (pCurr->pRight==NULL) //có 1 nút con trái pCurr = pCurr->pLeft; // Lưu lại nhánh con trái else if (pCurr->pLeft==NULL) pCurr = pCurr->pRight; // Lưu lại nhánh phải else // Có 2 nhánh con pTemp = _SearchStandFor(pCurr->pLeft, pCurr); delete pTemp; } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Các thao tác trên cây nhị phân tìm kiếm // Tìm phần tử thay thế: “Phần tử lớn nhất trong cây //con bên trái” NODETYPE * _SearchStandFor(NODETYPE *&p, NODETYPE *pCurr) { if (p->pRight != NULL) return _SearchStandFor(p->pRight, pCurr); // Tìm thấy phần tử thay thế… pCurr->Data = p->Data; // Copy dữ liệu NODETYPE *pTemp = p; p = p->pLeft; // Lưu lại nhánh con trái return pTemp; // Xóa phần tử thay thế } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân cân bằng  Cây nhị phân tìm kiếm đạt hiệu quả cao nhất khi nó có chiều cao thấp nhất (cây đạt trạng thái cân bằng), khi đó thời gian tìm kiếm sẽ là O(log2n)  Tuy nhiên khi thực hiện các thao tác thêm hoặc xoá các nút sẽ làm cho cây mất trạng thái cân bằng và có thể trở thành suy biến  hiệu suất tìm kiếm giảm  Vì thế để cây nhị phân tìm kiếm đạt hiệu quả tối đa thì phải giữ cho cây luôn trong trạng thái cân bằng 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân cân bằng C:\MyData\Downloads\books\GiaoTrinh\CauTrucDuLieu1\Htm\images\hinh13.2.gif 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân cân bằng 20 5 3010 15 13 5 30 20 15 10 30 5 10 20 15 Cây mất cân bằng Cây bị suy biến 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân cân bằng  Cây nhị phân tìm kiếm cân bằng (còn gọi là cây AVL), được các tác giả người Nga Adelson- Velskii và Landis đưa ra năm 1962.  Cây nhị phân cân bằng là cây nhị phân tìm kiếm mà tại mỗi nút của nó chiều cao của cây con trái và cây con phải lệch nhau không quá 1 đơn vị.  Cây AVL có chiều cao log2n +1, với n là số nút trên cây. 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân cân bằng  Cấu trúc lưu trữ Ta định nghĩa các hằng số chỉ trạng thái cân bằng của nút //Cây con trái cao hơn #define LH -1 //Hai cây con bằng nhau #define EH -0 //Cây con phải cao hơn #define RH 1 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cây nhị phân cân bằng  Khai báo cấu trúc một nút typedef struct Node { int Key;//Du lieu trong nut struct Node *pLeft;//Con tro den cay con trai struct Node *pRight;//Con tro den cay con phai char Balance;//Trang thai can bang int Count;//So nut trong cac cay con }AVL_Node;  Khai báo con trỏ đến nút gốc của cây typedef AVL_Node *AVLTree; 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cân bằng lại cây  Trường hợp 1 • Nút P bị mất cân bằng về bên trái • Nhánh con trái P1 của P bị lệch trái 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Cài đặt void RotateRight(AVLTree &P) //Xoay nút P sang bên phải { if(P!=NULL) { AVL_Node *P1; P1 = P->pLeft; //Q la con trai' cua P P->pLeft = P1->pRight; //Lien ket pLeft cua P tro //toi con phai cua P1 P1->pRight = P;//Lien ket pRight cua Q tro toi P P = P1; //ghi nhan dia chi moi cua P } } Xoay đơn sang phải 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cân bằng lại cây  Trường hợp 2 • Nút P bị mất cân bằng về bên trái • Nhánh con trái P1 của P bị lệch phải 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Cài đặt void DLRR(AVLTree &p) { if(p!=NULL) { AVL_Node *p1; p1 = p->pLeft; RotateLeft(p1); p->pLeft = p1; RotateRight(p); } } Xoay kép Left-Right 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cân bằng lại cây  Trường hợp 3 • Nút P bị mất cân bằng về bên phải • Nhánh con trái P1 của P bị lệch phải P A B P1 Ch h h + 1 RL Áp dụng xoay đơn phải – trái (Right-Left) 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Cài đặt void RotateLeft(AVLTree &P) //Xoay nut P sang ben trai { if(P!=NULL) { AVL_Node *P1; P1 =P->pRight; //q tro vao con trai' cua p P->pRight = P1->pLeft; //lien ket Right cua p tro //toi con trai' cua q P1->pLeft = P; //lien ket Left cua Q tro toi P - //dua P xuong ben trai P = P1; //xac nhan lai dia chi moi cua P } } Xoay đơn sang trái 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Cân bằng lại cây  Trường hợp 4 • Nút P bị mất cân bằng về bên phải • Nhánh con trái P1 của P bị lệch trái P2 P1P A DCB h h P P1 P2 A D B C h h h h 1 2 (b) : áp dụng xoay kép Phải – Trái (DRL_Double Right Left) DRL 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Cài đặt void DRLR(AVLTree &p) { if(p!=NULL) { AVL_Node *p1; P1 = p->pRight; RotateRight(p1); p->pRight = p1; RotateLeft(p); } } Xoay kép Right-Left 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Thêm phần tử mới vào cây Việc thêm một phần tử vào cây AVL diễn ra tương tự như trên CNPTK. Tuy nhiên, sau khi thêm xong, nếu chiều cao của cây thay đổi, từ vị trí thêm vào, ta phải lần ngược lên gốc để kiểm tra xem có nút nào bị mất cân bằng không. Nếu có, ta phải cân bằng lại ở nút này. Cây nhị phân cân bằng 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Thêm phần tử vào cây int insertNode(AVLTree &T, DataType X) { int res; if(T) { if(T->key == X) return 0; //đã có if(T->key > X) { res = insertNode(T->pLeft, X); if(res < 2) return res; switch(T->Balance) { case RH: T->Balance = EH; return 1; case EH: T->Balance = LH; return 2; case LH: balanceLeft (T); return 1; } } else { res = insertNode(T-> pRight, X); if(res < 2) return res; switch(T->Balance) { case LH: T->Balance = EH; return 1; case EH: T->Balance = RH; return 2; case RH: balanceRight(T); return 1; } } } T = new AVL_Node; if(T == NULL) return -1; //thiếu bộ nhớ T->key = X; T->Balance = EH; T->pLeft = T->pRight = NULL; return 2; // thành công, chiều cao tăng } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây  Huỷ phần tử trên cây Cũng giống như thao tác thêm một nút, việc hủy một phần tử X ra khỏi cây AVL thực hiện giống như trên CNPTK. Chỉ sau khi hủy, ta phải lần ngược lên gốc để kiểm tra xem có nút nào bị mất cân bằng không, nếu có ta sẽ thực hiện việc cân bằng lại Cây nhị phân cân bằng 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Huỷ phần tử trên cây int delNode(AVLTree &T, DataType X) { int res; if(T==NULL) return 0; if(T->key > X) { res = delNode (T->pLeft, X); if(res < 2) return res; switch(T->Balance) { case LH: T->Balance = EH; return 2; case EH: T->Balance = RH; return 1; case RH: return balanceRight(T); } } if(T->key < X) { res = delNode (T->pRight, X); if(res < 2) return res; switch(T->Balance) { case RH: T->Balance = EH; return 2; case EH: T->Balance = LH; return 1; case LH: return balanceLeft(T); } }else { //T->key == X AVLNode* p = T; if(T->pLeft == NULL) { T = T->pRight; res = 2; }else if(T->pRight == NULL) { T = T->pLeft; res = 2; }else { //T có cả 2 con res=searchStandFor(p,T->pRight); if(res < 2) return res; switch(T->Balance) { case RH: T->Balance = EH; return 2; case EH: T->Balance = LH; return 1; case LH: return balanceLeft(T); } } delete p; return res; } } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Huỷ phần tử trên cây //Tìm phần tử thế mạng int searchStandFor(AVLTree &p, AVLTree &q) { int res; if(q->pLeft) { res = searchStandFor(p, q->pLeft); if(res < 2) return res; switch(q->Balance) { case LH: q->Balance = EH;return 2; case EH: q->Balance = RH;return 1; case RH: return balanceRight(T); } }else { p->key = q->key; p = q; q = q->pRight; return 2; } } 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Huỷ phần tử trên cây void BalanceRight(Tree &P) { AVL_Node *Q, *R; Q = P->pRight; //q tro vao cay con phai switch(Q->Balance) { case 1: //Single Rotation P->Balance = 0; Q->Balance = 0; RotateLeft(P); break; case -1: //cay lech trai-->Double Rotation R = Q->pLeft; switch(R->Balance) { case 0: P->Balance = 0; Q->Balance = 0; break; case -1: P->Balance = 0; Q->Balance = 1; break; case 1: P->Balance = -1; Q->Balance = 0; break; } R->Balance = 0; /*Double Right-Left Rotation*/ DRLR(P); break; } } Cân bằng lại cây con bên phải của node P trong trường hợp P lệch phải 3/11/2010 www.lhu.edu.vn Chương 6 Cấu trúc cây Huỷ phần tử trên cây void BalanceLeft(Tree &P) { AVL_Node *Q, *R; Q = P->pLeft; //q tro vao cay con trai switch(Q->Balance) { case -1: //Single Rotation P->Balance = 0; Q->Balance = 0; RotateRight(P); break; case 1: //Double Rotation R = Q->pRight; switch(R->Balance) { case 0: P->Balance = 0; Q->Balance = 0; break; case -1: P->Balance = -1; Q->Balance = 0; break; case 1: P->Balance = 0; Q->Balance = -1; break; } R->Balance = 0; /*Double pLeft-pRight Rotation*/ DLRR(P); break; } } Cân bằng lại cây con bên trái của node P trong trường hợp P lệch trái