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

NỘI DUNGCÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNGÐịnh nghĩaCâ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ụ:4423881337591081530405571Tổ chức dữ liệuChỉ số cân bằng = độ lệch giữa cây trái và cây phải của một nútCá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)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ơntypedef struct tagAVLNode { char balFactor; //chỉ số cân bằng Data key; struct tagAVLNode* pLeft; struct tagAVLNode* pRight;}AVLNode;typedef AVLNode *AVLTree; Các trường hợp mất cân bằng do lệch tráiTRT1R1L1TRT1T2L1R21L21Cây mất cân bằng tại nút TTH1: Left-LeftTH2: Left-RightCác trường hợp mất cân bằng do lệch phảiTT1LR1L1TT1LR1T2R21L21Cây mất cân bằng tại nút TTH3: Right-RightTH4: Right-LeftCác thao tác trên cây cân bằngKhi 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áiLệch nhánh phải, thêm bên phảiLệch nhánh trái, hủy bên phảiLệch nhánh phải, hủy bên tráiCâ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ấpPhải bảo đảm cây vẫn là Nhị phân tìm kiếmCân bằng lại trường hợp 1TRT1R1L1TRT1R1L1Cài đặt cân bằng lại cho trường hợp 1void 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;}Cân bằng lại trường hợp 2TRT1T2L1R21L21T2TT1L21L1RR21Cài đặt cân bằng lại cho trường hợp 2void 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}Cân bằng lại trường hợp 3TT1LR1L1R1T1TLL1Cài đặt cân bằng lại cho trường hợp 3void 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}Cân bằng lại trường hợp 4TT1LR1T2R21L21T1R1T2R21TLL21Cài đặt cân bằng lại cho trường hợp 4void 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;}Thêm 1 nútThêm bình thường như trường hợp cây NPTKNếu cây tăng trưởng chiều caoLần ngược về gốc để phát hiện nút bị mất cân bằngTiến hành cân bằng lại nút đó bằng thao tác cân bằng thích hợpViệc cân bằng lại chỉ cần thực hiện 1 lần nơi mất cân bằngHủy 1 nútHủy bình thường như trường hợp cây NPTKNếu cây giảm chiều cao:Lần ngược về gốc để phát hiện nút bị mất cân bằngTiến hành cân bằng lại nút đó bằng thao tác cân bằng thích hợpTiếp tục lần ngược lên nút chaViệc cân bằng lại co thể lan truyền lên tận gốc