Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Cây nhị phân tìm kiếm

Chương 5. Cây nhị phân tìm kiếmTrần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn1Nội dungKhái niệmĐặc điểmĐịnh nghĩa cấu trúc dữ liệuCác lưu ý khi cài đặtCác thao tác xử lý2Khái niệmBậc của một nút: là số cây con của nút đó Bậc của cây: là bậc lớn nhất của các nút trong cây. Cây có bậc n thì gọi là cây n-phân Nút gốc: là nút không có nút chaNút lá: là nút có bậc bằng 0 Nút nhánh: là nút có bậc khác 0 và không phải là gốc3222110000Mức 4Mức 3Mức 2Mức 1Khái niệmChiều dài đường đi đến nút x: là số nhánh cần đi qua kể từ gốc đến xChiều cao h của cây: Mức lớn nhất của các nút lá4xĐặc điểm của cây nhị phânSố nút ở mức I  2I-1Số nút ở mức lá  2h-1, với h là chiều cao của câyChiều cao của cây h  log2N, với N là số nút trong cây5Biểu diễn cây nhị phânCây nhị phân là một cấu trúc bao gồm các phần tử (node) được kết nối với nhau theo quan hệ “cha-con” với mỗi cha có tối đa 2 con. Mỗi nút gồm các thông tin: Dữ liệu lưu trữ: data Liên kết tới cây con trái của nút: pLeftLiên kết tới cây con phải của nút: pRight6Định nghĩa kiểu dữ liệu dùng C7typedef struct TNode{ DataType data; TNode *pLeft, *pRight;} *Tree; NútGiá trịTrỏ tráiTrỏ phảiTNODEdatapLeftpRightVí dụ khai báo node chứa giá trị nguyêntypedef struct TNode{ int data; TNode *pLeft, *pRight;} *Tree;8Cây nhị phân tìm kiếmLà 1 cây nhị phânGiá trị của một node luôn lớn hơn giá trị của các node nhánh trái và nhỏ hơn giá trị các node nhánh phảiNút có giá trị nhỏ nhất nằm ở nút trái nhất của cây Nút có giá trị lớn nhất nằm ở nút phải nhất của cây97336161540234Các lưu ý khi cài đặtBước 1: Khai báo kiểu dữ liệu biểu diễn câyBước 2: Xây dựng hàm đưa dữ liệu (nhập) vào câyBước 3: Xây dựng các thao tác duyệt, tìm kiếm, huỷ, 10Cấu trúc chương trình11Khai báo cấu trúc câyKhởi tạo cây rỗngXây dựng câyCác thao tácHủy câyCác thao tác cơ bản1. Tạo cây2. Duyệt cây3. Cho biết các thông tin của cây4. Tìm kiếm5. Xoá node trên cây 12Tạo cây134015461363736316415407Nếu node cần thêm nhỏ hơn node đang xét thì thêm về bên tráiNgược lại thì thêm về bên phảiHàm thêm một phần tử vào cây14int InsertNode (Tree & t, int x){ if(t!=NULL) { if(x==t->data) return 0; //Có giá trị trùng else { if(xdata) InsertNode(t->pLeft, x); else InsertNode(t->pRight, x); } } else { t=new TNode; if(t==NULL) return -1; //Thiếu bộ nhớ t->data=x; t->pLeft=t->pRight=NULL; return 1; //Thêm thành công }}Bài tậpViết hàm tạo cây nhị phân số nguyên từ các giá trị nhập vào từ bàn phím. Quá trình nhập cho đến khi gặp giá trị trùng hoặc hết bộ nhớViết hàm tạo cây nhị phân số nguyên từ dãy số nguyên cho trước15Duyệt câyThứ tự trước (NLR)Thứ tự giữa (LNR)Thứ tự sau (LRN)1617BướcKết quả duyệt theo thứ tự NLR17L7R723L3R3R731R3R746L6R754R7636L36R36715R15R36823R36940KQ73164361523407336161540234Hàm duyệt NLRTại node t đang xét, nếu khác rỗng thìIn giá trị của tDuyệt cây con bên trái của t theo thứ tự NLRDuyệt cây con bên phải của t theo thứ tự NLR 18void NLR (Tree t){ if(t!=NULL) { coutKeypLeft); NLR(t->pRight); }}Bài tậpVẽ cây nhị phân tìm kiếm theo thứ tự nhập từ trái sang phải và duyệt cây theo thứ tự trước:27; 19; 10; 21; 35; 25; 41; 12; 46; 7H; B; C; A; E; D; Z; M; P; THuế; Đà Nẵng; Hà Nội; Vĩnh Long; Cần Thơ; Sóc Trăng; Nha Trang; Đồng Nai; Vũng Tàu; An Giang; Tiền Giang; Bình Dương; Hải Dương1920BướcKết quả duyệt theo thứ tự LNR1L77R72L33R37R7313R37R743R37R75L667R76467R7767R787R79L3636R361015R1536R36112336R361236R361340KQ13467152336407336161540234Hàm duyệt LNRTại node t đang xét, nếu khác rỗng thìDuyệt cây con bên trái của t theo thứ tự LNRIn giá trị của tDuyệt cây con bên phải của t theo thứ tự LNR 21void LNR (Tree t){ if(t!=NULL) { LNR(t->pLeft); coutKeypRight); }}22BướcKết quả duyệt theo thứ tự LRN1L7R772L3R33R7731R33R774L663R775463R77663R7773R778L36R363679R1515R36367102315R363671115R36367124036713367147KQ14632315403677336161540234Hàm duyệt LRNTại node t đang xét, nếu khác rỗng thìDuyệt cây con bên trái của t theo thứ tự LRNDuyệt cây con bên phải của t theo thứ tự LRN In giá trị của t 23void LRN (Tree t){ if(t!=NULL) { LRN(t->pLeft); LRN(t->pRight); coutKeykey) Remove(t->pLeft, x);else if (x > t->key) Remove(t->pRight, x);else{TNode * pHuy = t;if (t->pLeft == NULL) t = t->pRight;else if (t->pRight == NULL) t = t->pLeft;else SearchStandFor(pHuy, t->pRight);delete pHuy;}}}45void SearchStandFor(Tree &pHuy, Tree &pTM){if(pTM->pLeft) SearchStandFor(pHuy, pTM->pLeft);else{pHuy->key=pTM->key;pHuy=pTM;pTM=pTM->pRight;}}Đánh giáThao tác tìm kiếm, thêm mới, xóa đều có độ phức tạp trung bình O(h), với h là chiều cao của cây Trường hợp tốt nhất, cây có n nút sẽ có độ cao h = log2(n). Chi phí tìm kiếm sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tự Trường hợp xấu nhất, cây có thể bị suy biến thành 1 DSLK. Lúc đó các thao tác trên sẽ có độ phức tạp O(n) Vì vậy cần có cải tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n) 46Cây nhị phân tìm kiếm cân bằngPhát minh: Nhà toán học Nga G. M. Adel’Son-Vel’Skil và E. M. Landis (1962)Cấu trúc cây giúp tối ưu thời gian tìm kiếmCây nhị phân tìm kiếm cân bằng: cây AVLChi phí tìm kiếm, thêm mới, xoá trong cây n nút là O(log n)47Định nghĩaCây AVL là một cây nhị phân tìm kiếmChiều cao cây con trái và phải của nút gốc hơn kém nhau không quá 1Cả hai cây con trái và phải cũng phải là cây AVL48Chỉ số cân bằng (Balance factor)Chỉ số cân bằng (bF – balance Factor) của một nút: bF = hR – hLhL: chiều cao cây con tráihR: chiều cao cây con phảiCó 3 trường hợp:bF = 0: hL = hR (Ký hiệu EH: Equal Height)bF > 0: hL hR (Ký hiệu LH: Left Higher)49Khai báo cấu trúc cây AVLtypedef struct AVLNode{ DataType key;        char bF;    AVLNode* pLeft; AVLNode* pRight;} *AVLTree;50const char LH = -1;const char EH = 0;const char RH = 1;Trường hợp 1: Lệch trái51Trường hợp 2: Lệch phải52Trường hợp 1.1: T1 lệch trái53Quay đơn Left - LeftTrường hợp 1.2: T1 không lệch54Quay đơn Left - Leftvoid RotateLL ( AVLTree &T) {             AVLNode * T1 = T-> pLeft ;             T->pLeft      = T1->pRight ;             T1-> pRight = T;             switch(T1-> bF)             {                          case LH: T-> bF = EH;                                       T1-> bF = EH;                                       break ;                          case EH: T-> bF = LH;                                       T1-> bF = RH;                                       break ;             }             T = T1; }Trường hợp 1.3: T1 lệch phải56Quay kép Left - Rightvoid RotateLR(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-> bF)             {                          case LH: T-> bF = RH;                                       T1-> bF = EH;                                       break ;                          case EH: T-> bF = EH;                                       T1-> bF = EH;                                       break ;                          case RH: T-> bF = EH;                                       T1-> bF = LH;                                       break ;             }             T2-> bF = EH;             T = T2; }Trường hợp 2.1 và 2.258void RotateRR(AVLTree &T){             AVLNode * T1 = T-> pRight ;             T->pRight = T1-> pLeft ;             T1-> pLeft = T;             switch (T1-> bF)             {                          case RH: T-> bF = EH;                                       T1-> bF = EH;                                       break ;                          case EH: T-> bF = RH;                                       T1-> bF = LH;                                       break ;             }             T = T1; }Trường hợp 2.359void RotateRL ( 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-> bF)             {                          case RH: T-> bF = LH;                                       T1-> bF = EH;                                       break ;                          case EH: T-> bF = EH;                                       T1-> bF = EH;                                       break ;                          case LH: T-> bF = EH;                                       T1-> bF = RH;                                       break ;             }             T2-> bF = EH;             T = T2; } Thêm 1 node vào cây AVLTương tự như trên cây NPTKSau khi thêm xong, nếu chiều cao của cây thay đổi. Nếu có mất cân bằng  cân bằng lại ở nút nàyHàm insertNode trả về giá trị -1: không đủ bộ nhớ 0: trùng giá trị1: thêm thành công2: thêm thành công và chiều cao tăng6061int InsertNode(AVLTree &T, int X){            int kq;            if (T != NULL )             {                        if(T->key == X)                                     return 0; // tồn tại x                         else if (T->key > X) // thêm về bên trái                        {                                    kq = InsertNode(T->pLeft, X);                                    if (kq bF)                                    {                                                case RH: T->bF= EH;                                                            return 1;                                                case EH: T->bF = LH;                                                            return 2;                                                case LH: BalanceLeft(T);                                                             return 1;                                    }                        }62                        else //Trường hợp T->key pRight, X);                                    if (res bF)                                     {                                                case LH: T->bF = EH;                                                            return 1;                                                case EH: T->bF = RH;                                                            return 2;                                                case RH: BalanceRight(T);                                                             return 1;                                    }                        }            }63            //Tạo node mới T = new TNode;            if (T == NULL) return -1; //thiếu bộ nhớ            T->key = X;             T->bF = EH;            T->pLeft = T->pRight = NULL;            return 2; //Thêm thành công và chiều cao tăng}int BalanceLeft(AVLTree &T){             switch (T-> pLeft -> bF)             {                          case LH: RotateLL (T);  return 2;                          case EH: RotateLL (T);  return 1;                          case RH: RotateLR (T); return 2;             }             return 0; }int BalanceRight(AVLTree &T){             switch (T-> pRight -> bF)             {                          case LH: RotateRL (T);  return 2;                          case EH: RotateRR (T); return 1;                          case RH: RotateRR (T); return 2;             }             return 0; }Hủy 1 node trên câyTương tự như trên cây NPTKSau khi hủy, nếu mất cân bằng  cân bằng lạiHàm deleteNode trả về giá trị 1: hủy thành công 0: không có X trong cây 2: hủy thành công và chiều cao của cây giảm6566int DeleteNode(AVLTree &T, int X){             int kq ;             if (T==NULL)                          return 0;             if (T->key > X)             {                          kq = DeleteNode (T-> pLeft , X);                          if ( kq  bF )                          {                                       case LH: T-> bF = EH;                                                 return 2;                                       case EH: T-> bF = RH;                                                    return 1;                                       case BalanceRight (T);                          }             } 67else if (T->key  pRight , X);                          if ( kq bF )                          {                                       case RH: T-> bF = EH;                                                    return 2;                                       case EH: T-> bF = LH;                                                    return 1;                                       case LH: return BalanceLeft (T);                          }             } 68 else // if (T->key == X)             {                                                   AVLNode * p = T;                          if (T-> pLeft == NULL)                          {                                       T = T->pRight ; kq = 2;                          }                          else if (T-> pRight == NULL)                          {                                       T = T-> pLeft ; kq = 2;                          } 69                         else // if (T-> pLeft != NULL && T-> pRight != NULL)                          {                                       kq = SearchStandFor ( p, T -> pRight );                                       if( kq  bF )                                       {                                                    case RH: T-> bF = EH;                                                                 return 2;                                                    case EH: T-> bF = LH;                                                                 return 1;                                                    case LH: return BalanceLeft (T);                                       }                          }                          delete p;                          return kq ;             } }70int SearchStandFor(AVLTree &p, AVLTree &q){             int kq;            if (q->pLeft != NULLL) {                        kq = SearchStandFor(p, q->pLeft);                        if (kq bF){                                    case LH: q->bF= EH;                                                return 2;                                    case EH: q->bF= RH;                                                return 1;                                    case RH: return BalanceRight(T);                         }            } else {                        p->key = q->key;                        p = q;                        q = q->pRight;                        return 2;            }}