Chapter 6: Cấu trúc cây ( tree)

Chia sẻ: Thanh Tran | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

90
lượt xem 4
download

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

Các khái niệm cơ bản Cây nhị phân tìm kiếm Cây nhị phân cân bằng Cây nhiều nhánh 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 ??

Chủ đề:

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

Lưu

Nội dung Text: Chapter 6: Cấu trúc cây ( tree)

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