Bài giảng Cấu trúc dữ liệu và Thuật toán - Chương 4: Cấu trúc cây - Trees - Phan Nguyệt Thuần

1CHƢƠNG 4 CẤU TRÚC CÂY - TREES 2Tài Liệu Tham Khảo  Bài giảng CTDL, ĐH Công nghệ thông tin TPHCM  Bài giảng CTDL, Khoa Công nghệ thông tin, ĐH KHTN TPHCM  Nhập môn CTDL, Dương Anh Đức, Trần Hạnh Nhi, ĐH KHTN TPHCM 3Nội dung  Các khái niệm và thuật ngữ cơ bản  Cây tổng quát  Cây nhị phân (Binary Tree)  Cây nhị phân tìm kiếm (BST- Binary Search Tree)  Cây nhị phân tìm kiếm cân bằng (AVLTree) 4Định Nghĩa Cây 5Định Nghĩa Cây Cây là một tập hợp T các phần tử (gọi là nút của cây), trong đó có một nút đặc biệt gọi là nút gốc, các nút còn lại đƣợc chia thành những tập rời nhau T1, T2, ,Tn theo quan hệ phân cấp, trong đó Ti cũng là 1 cây. Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này ngƣời ta gọi là quan hệ cha – con. 6Ví dụ 7Ví dụ 8Ví dụ 9Các tính chất của cây  Nút gốc không có nút cha  Mỗi nút khác chỉ có 1 nút cha  Mỗi nút có thể có nhiều nút con  Không có chu trình 10 Một Số Khái Niệm  Bậc của một nút: là số cây con của nút đó .  Bậc của một cây: là bậc lớn nhất của các nút trong cây  Nút gốc: là nút không có nút cha.  Nút lá: là nút có bậc bằng 0 .  Mức của một nút: ◦ Mức (gốc (T) ) = 0. ◦ Gọi T1, T2, T3, ... , Tn là các cây con của T0 : Mức (T1) = Mức (T2) = . . . = Mức (Tn) = Mức (T0) + 1.  Độ dài đƣờng đi từ gốc đến nút x: là số nhánh cần đi qua kể từ gốc đến x. 11 Ví dụ 12 Cây Nhị Phân  Mỗi nút có tối đa 2 cây con Caây con traùi Caây con phaûi 13 Một Số Tính Chất Của Cây Nhị Phân  Số nút nằm ở mức i  2i.  Số nút lá  2h-1, với h là chiều cao của cây.  Chiều cao của cây h  log2(N) ◦ N = số nút trong cây  Số nút trong cây  2h-1. 14 Một Số Tính Chất Của Cây Nhị Phân 15 Cấu Trúc Dữ Liệu Của Cây Nhị Phân typedef struct tagTNode { Data Key; struct tagTNode *pLeft; struct tagTNode *pRight; }TNode; typedef TNode *TREE; Key 16 Ví Dụ Cây Đƣợc Tổ Chức Trong Bộ Nhớ Trong 3f62f 1f N97f 3f 5f4N 2f N5N 5f N8N 7f 17 Duyệt cây nhị phân 18 Ví Dụ Kết Quả Của Phép Duyệt Cây  NLR: 9, 2, 6, 1, 10, 8, 5, 3, 7, 12, 4.  LNR: 6, 2, 10, 1, 9, 3, 5, 8, 12, 7, 4.  Kết quả của phép duyệt : LRN, NRL,LRN, LNR? 9 82 16 10 5 3 7 412 19 Duyệt Trƣớc void NLR(TREE Root) { if (Root != NULL) { ; //Xử lý tƣơng ứng theo nhu cầuNLR(Root->pLeft); NLR(Root->pRight); } } 20 Duyệt Giữa void LNR(TREE Root) { if (Root != NULL) { LNR(Root->pLeft); ; // Xử lý tƣơng ứng theo nhu cầu LNR(Root->pRight); } } 21 Duyệt Sau void LRN(TREE Root) { if (Root != NULL) { LRN(Root->pLeft); LRN(Root->pRight); ; // Xử lý tương ứng theo nhu cầu } } 22 Biểu Diễn Cây Tổng Quát Bằng Cây Nhị Phân  Giữ lại nút con trái nhất làm nút con trái.  Các nút con còn lại chuyển thành nút con phải.  Trong cây nhị phân mới, con trái thể hiện quan hệ cha con và con phải thể hiện quan hệ anh em trong cây tổng quát ban đầu. 23 Biểu Diễn Cây Tổng Quát Bằng Cây Nhị Phân A B C D E F G H I J A B C D E F G H I J 24 Ðịnh nghĩa cây nhị phân tìm kiếm  Cây nhị phân  Bảo đảm nguyên tắc bố trí khoá tại mỗi nút: ◦ Các nút trong cây trái nhỏ hơn nút hiện hành ◦ Các nút trong cây phải lớn hơn nút hiện hành 18 13 37 15 23 40 Ví dụ: 25 Ƣu điểm của cây nhị phân tìm kiếm Nhờ trật tự bố trí khóa trên cây : ◦ Định hƣớng đƣợc khi tìm kiếm Cây gồm N phần tử : ◦ Trƣờng hợp tốt nhất h = log2N ◦ Trƣờng hợp xấu nhất h = Ln 26 Cấu trúc dữ liệu của cây nhị phân tìm kiếm  Cấu trúc dữ liệu của 1 nút typedef struct tagTNode { int Key; //trƣờng dữ liệu là 1 số nguyên struct tagTNode *pLeft; struct tagTNode *pRight; }TNode;  Cấu trúc dữ liệu của cây typedef TNode *TREE; 27 Các thao tác trên cây nhị phân tìm kiếm Tạo 1 cây rỗng Tạo 1 nút có trƣờng Key bằng x Thêm 1 nút vào cây nhị phân tìm kiếm Xoá 1 nút có Key bằng x trên cây Tìm 1 nút có khoá bằng x trên cây 28 Tạo cây rỗng  Cây rỗng -> địa chỉ nút gốc bằng NULL void CreateTree(TREE &T) { T=NULL; } 29 Tạo 1 nút có Key bằng x TNode *CreateTNode(int x) { TNode *p; p = new TNode; //cấp phát vùng nhớ động if(p==NULL) exit(1); // thoát else { p->key = x; //gán trƣờng dữ liệu của nút = x p->pLeft = NULL; p->pRight = NULL; } return p; } 30 Thêm một nút x  Rằng buộc: Sau khi thêm cây đảm bảo là cây nhị phân tìm kiếm. int insertNode(TREE &T, Data X) { if(T) { if(T->Key == X) return 0; if(T->Key > X) return insertNode(T->pLeft, X); else return insertNode(T->pRight, X);} T = new TNode; if(T == NULL) return -1; T->Key = X; T->pLeft =T->pRight = NULL; return 1; } 31 Minh họa thêm 1 phần tử vào cây 44 18 88 13 37 59 108 15 23 40 55 71 Theâm X=50 44 < X 88 > X 59 > X 50 55 > X 32 Minh họa thêm 1 phần tử vào cây 33 Tìm nút có khoá bằng x (không dùng đệ quy) TNode * searchNode(TREE Root, Data x) { Node *p = Root; while (p != NULL) { if(x == p->Key) return p; else if(x Key) p = p->pLeft; else p = p->pRight; } return NULL; } 34 Tìm nút có khoá bằng x (dùng đệ quy) TNode *SearchTNode(TREE T, int x) { if(T!=NULL) { if(T->key==x) return T; else if(x>T->key) return SearchTNode(T- >pRight,x); else return SearchTNode(T->pLeft,x); } return NULL; } 35 Minh hoạ tìm một nút 44 18 88 13 37 59 108 15 23 40 55 71 Tìm X=55 Tìm thấy X=55 55 36 Minh hoạ tìm một nút 37 Minh hoạ tìm một nút 38 Minh hoạ thành lập 1 cây từ dãy số 9, 5, 4, 8, 6, 3, 14,12,13 9 5 14 84 63 12 13 39 Hủy 1 nút có khoá bằng X trên cây Hủy 1 phần tử trên cây phải đảm bảo điều kiện ràng buộc của Cây nhị phân tìm kiếm Có 3 trƣờng hợp khi hủy 1 nút trên cây  TH1: X là nút lá  TH2: X chỉ có 1 cây con (cây con trái hoặc cây con phải)  TH3: X có đầy đủ 2 cây con TH1: Ta xoá nút lá mà không ành hƣởng đến các nút khác ttrên cây TH2: Trƣớc khi xoá x ta móc nối cha của X với con duy nhất của X. TH3: Ta dùng cách xoá gián tiếp 40 Minh hoạ hủy một nút 41 Minh hoạ hủy một nút 42 Minh hoạ hủy một nút 43 Minh hoạ hủy một nút 44 Minh hoạ hủy một nút 45 Minh hoạ hủy phần tử x có 1 cây con 44 18 88 13 59 10837 15 23 55 71 Hủy X=37 46 Hủy 1 nút có 2 cây con Ta dùng cách hủy gián tiếp, do X có 2 cây con Thay vì hủy X ta tìm phần tử thế mạng Y. Nút Y có tối đa 1 cây con. Thông tin lƣu tại nút Y sẽ đƣợc chuyển lên lƣu tại X. Ta tiến hành xoá hủy nút Y (xoá Y giống 2 trƣờng hợp đầu) Cách tìm nút thế mạng Y cho X: Có 2 cách  C1: Nút Y là nút có khoá nhỏ nhất (trái nhất) bên cây con phải X C2: Nút Y là nút có khoá lớn nhất (phải nhất) bên cây con trái của X 47 Minh họa hủy phần tử X có 2 cây con 44 18 88 13 37 59 108 15 23 40 55 71 30 Xoá nút có trường Key = 18, lúc đó nút có khoá 23 là nút thế mạng 48 Minh họa hủy phần tử X có 2 cây con 49 Cài đặt thao tác xoá nút có trƣờng Key = x void DeleteNodeX1(TREE &T,int x) { if(T!=NULL) { if(T->KeyRight,x); else { if(T->Key>x) DeleteNodeX1(T->Left,x); else //tim thấy Node có trường dữ liệu = x { TNode *p; p=T; if (T->Left==NULL) T = T->Right; else { if(T->Right==NULL) T=T->Left; else ThayThe1(p, T->Right);// tìm bên cây con phải } delete p; }}} else printf("Khong tim thay phan tu can xoa");} 50 Hàm tìm phần tử thế mạng void ThayThe1(TREE &p, TREE &T) { if(T->Left!=NULL) ThayThe1(p,T->Left); else { p->Key = T->Key; p=T; T=T->Right; } } 51 Các đánh giá 52 Ðị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 Ví dụ: 44 23 88 13 37 59 108 15 30 40 55 71 53 Tổ chức dữ liệu Chỉ số cân bằng = độ lệch giữa cây trái và cây phải của một nút Các giá trị hợp lệ : CSCB(p) = 0  Độ cao cây trái (p) = Độ cao cây phải (p) CSCB(p) = 1  Độ cao cây trái (p) < Độ cao cây phải (p) CSCB(p) = -1 Độ cao cây trái (p) > Độ cao cây phải (p) 54 Tổ chức dữ liệu 55 Tổ chức dữ liệu(tt) #define LH -1 //cây con trái cao hơn #define EH 0 //cây con trái bằng cây con phải #define RH 1 //cây con phải cao hơn typedef struct tagAVLNode { char balFactor; //chỉ số cân bằng Data key; struct tagAVLNode* pLeft; struct tagAVLNode* pRight; }AVLNode; typedef AVLNode *AVLTree; 56 Thao tác điều chỉnh cây 57 Thao tác điều chỉnh cây 58 Thao tác điều chỉnh cây 59 Các trƣờng hợp mất cân bằng do lệch trái T RT1 R1L1 T RT1 T2L1 R21L21 Cây mất cân bằng tại nút T TH1: Left-Left TH2: Left-Right 60 Các trƣờng hợp mất cân bằng do lệch phải T T1L R1L1 T T1L R1T2 R21L21 Cây mất cân bằng tại nút T TH3: Right-Right TH4: Right-Left 61 Các thao tác trên cây cân bằng  Khi thêm hay xoá 1 nút trên cây, cĩ thể làm cho cây mất tính cân bằng, khi ấy ta phải tiến hành cân bằng lại.  Cây có khả năng mất cân bằng khi thay đổi chiều cao:  Lệch nhánh trái, thêm bên trái  Lệch nhánh phải, thêm bên phải  Lệch nhánh trái, hủy bên phải  Lệch nhánh phải, hủy bên trái  Cân bằng lại cây : tìm cách bố trí lại cây sao cho chiều cao 2 cây con cân đối:  Kéo nhánh cao bù cho nhánh thấp  Phải bảo đảm cây vẫn là Nhị phân tìm kiếm 62 Cân bằng lại trƣờng hợp 1 T RT1 R1L1 T R T1 R1 L1 63 Ví dụ 64 Cài đặt cân bằng lại cho trƣờng hợp 1 void LL(AVLTree &T) { AVLNode *T1=T->pLeft; T->pLeft = T1->pRight; T1->pRight=T; switch(T1-> balFactor) { case LH: T-> balFactor =EH; T1->balFactor=EH; break; case EH: T->balFactor=LH; T1->balFactor =RH; break; } T=T1; } 65 Cân bằng lại trƣờng hợp 2 T RT1 T2L1 R21L21 T2 TT1 L21L1 RR21 66 Cài đặt cân bằng lại cho trƣờng hợp 2 void LR(AVLTree &T) { AVLNode *T1=T->pLeft; AVLNode *T2=T1->pRight; T->pLeft=T2->pRight; T2->pRight=T; T1->pRight= T2->pLeft; T2->pLeft = T1; switch(T2->balFactor) { case LH: T->balFactor=RH; T1->balFactor=EH; break; case EH: T->balFactor = EH; T1->balFactor=EH; break; case RH: T->balFactor =EH; T1->balFactor= LH; break; }T2->balFactor =EH; T=T2} 67 Cân bằng lại trƣờng hợp 3 T T1L R1L1 R1 T1 T L L1 68 Ví dụ 69 Cài đặt cân bằng lại cho trƣờng hợp 3 void RR(AVLTree &T) { AVLNode *T1= T->pRight; T->pRight=T1->pLeft; T1->pLeft=T; switch(T1-> balFactor) { case RH: T-> balFactor = EH; T-> balFactor = EH; break; case EH: T-> balFactor = RH; T1-> balFactor = LH; break; } T=T1 } 70 Cân bằng lại trƣờng hợp 4 T T1L R1T2 R21L21 T1 R1 T2 R21 T L L21 71 Ví dụ 72 Cài đặt cân bằng lại cho trƣờng hợp 4 void RR(AVLTree &T) { AVLNode *T1= T->pRight; AVLNode *T2=T1->pLeft; T->pRight = T2->pLeft; T2->pLeft = T; T1->pLeft = T2->pRight; T2->pRight = T1; switch(T2-> balFactor) { case RH: T-> balFactor = LH; T1-> balFactor = EH; break; case EH: T-> balFactor = EH; T1-> balFactor = EH; break; case LH: T-> balFactor = EH; T1-> balFactor = RH; break; } T2-> balFactor =EH; T=T2;} 73 Ví dụ tạo cây 74 Ví dụ tạo cây 75 Ví dụ tạo cây 76 Các đánh giá