›
›

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

pdf 17 trang phuongnguyen 3570
Download
Bạn đang xem tài liệu "Cấu trúc dữ liệu và giải thuật - Chương 8: Cây nhị phân tìm kiếm cân bằng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_chuong_8_cay_nhi_phan_tim_kie.pdf

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

  1. CẤCấuCẤUU TRÚ TRÚ trúCCc DỮ DỮdữ L LIỆU IỆUliệu V V À Àvà GIẢI GIẢI thu THUẬT THUẬật gTiải 1 1 Click Click To Master Edit Title Style CÂYTÌM NHỊ PHÂNKIẾM BẰNGCÂN NỘI DUNG NỘI 1
  2. CẤCấuCẤUU TRÚ TRÚ trúCCc DỮ DỮdữ L LIỆU IỆUliệu V V À Àvà GIẢI GIẢI thu THUẬT THUẬật gTiải 1 1  Ðịnh Ðịnh nghĩa chênh chênh lệch khôngquámột của nó của cây độ cao con trái vàcủa cây phải con Câynhị phântìm kiếm cân bằnglàcây Vídụ: Click Click To Master Edit Title Style 13 15 23 30 37 2 40 44 55 mà tại màmỗi tại nút 59 71 88 108
  3. Tổ Clickchức dữTo liệuEdit Master Title Style 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) 1 iải T 1 . CSCB(p) = 1 Độ cao cây trái (p) Độ À GIẢI À GIẢI và cao cây phải (p) IỆU V LIỆU V c dữ liệu C DỮ C DỮ L trú U TRÚ ẤU ẤU TRÚ C Cấu CẤ 3
  4. Tổ Clickchức dữTo liệu(tt)Edit Master Title Style #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 1 iải { char balFactor; //chỉ số cân bằng T 1 ật g ật Data key; THUẬ THUẬT thu struct tagAVLNode* pLeft; À À GIẢI À GIẢI À GIẢI và struct tagAVLNode* pRight; IỆU V LIỆU V }AVLNode; c dữ liệu C DỮ C DỮ L typedef AVLNode *AVLTree; trú U TRÚ ẤU ẤU TRÚ C Cấu CẤ 4
  5. CácClick trường To hợp Edit mất Master cân bằng Title do lệchStyle trái Cây mất cân bằng tại nút T TH1: Left-Left T TH2: Left-Right T T1 R T1 R 1 iải T 1 ật g ật THUẬ THUẬT thu L1 R1 À À GIẢI À GIẢI À GIẢI và L1 T2 IỆU V LIỆU V c dữ liệu C DỮ C DỮ L L21 R21 trú U TRÚ ẤU ẤU TRÚ C Cấu CẤ 5
  6. CácClick trường To hợp Edit mất Master cân bằng Title do lệchStyle phải Cây mất cân bằng tại nút T TH3: Right-Right TH4: Right-Left T T L L 1 iải T1 T 1 T1 ật g ật THUẬ THUẬT thu À À GIẢI À GIẢI À GIẢI và L1 R1 T2 R1 IỆU V LIỆU V c dữ liệu C DỮ C DỮ L trú L21 R21 U TRÚ ẤU ẤU TRÚ C Cấu CẤ 6
  7. CácClick thao Totác Edit trên Mastercây cân Titlebằng Style  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 1 iải T 1 ật g ật . Lệch nhánh phải, thêm bên phải THUẬ THUẬT thu . Lệch nhánh trái, hủy bên phải À À GIẢI À GIẢI À GIẢI và . Lệch nhánh phải, hủy bên trái IỆU V LIỆU V  Cân bằng lại cây : tìm cách bố trí lại cây sao cho c dữ liệu C DỮ C DỮ L chiều cao 2 cây con cân đối: trú U TRÚ ẤU ẤU TRÚ . Kéo nhánh cao bù cho nhánh thấp C Cấu CẤ . Phải bảo đảm cây 7vẫn là Nhị phân tìm kiếm
  8. CẤCấuCẤUU TRÚ TRÚ trúCCc DỮ DỮdữ L LIỆU IỆUliệu V V À Àvà GIẢI GIẢI thu THUẬT THUẬật gTiải 1 1 Cân Cân bằng lại trường hợp 1 L1 Click Click To Master Edit Title Style T1 R1 T R 8 L1 T1 R1 T R
  9. CàiClick đặt cân To bằngEdit Masterlại cho trường Title Style hợp 1 void LL(AVLTree &T) { AVLNode *T1=T->pLeft; T->pLeft = T1->pRight; T1->pRight=T; switch(T1-> balFactor) 1 iải T 1 ật g ật { case LH: T-> balFactor =EH; THUẬ THUẬT thu T1->balFactor=EH; break; À À GIẢI À GIẢI À GIẢI và case EH: T->balFactor=LH; IỆU V LIỆU V T1->balFactor =RH; break; c dữ liệu C DỮ C DỮ L } trú T=T1; U TRÚ ẤU ẤU TRÚ C Cấu CẤ } 9
  10. CẤCấuCẤUU TRÚ TRÚ trúCCc DỮ DỮdữ L LIỆU IỆUliệu V V À Àvà GIẢI GIẢI thu THUẬT THUẬật gTiải 1 1 Cân Cân bằng lại trường hợp 2 L1 Click Click To Master Edit Title Style L21 T1 T2 T R21 R 10 L1 T1 L21 T2 R21 T R
  11. CàiClick đặt cân To bằngEdit Masterlại cho trường Title Style 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; 1 iải T 1 switch(T2->balFactor) ật g ật THUẬ THUẬT { case LH: T->balFactor=RH; thu T1->balFactor=EH; break; À À GIẢI À GIẢI À GIẢI và case EH: T->balFactor = EH; IỆU V LIỆU V T1->balFactor=EH; break; c dữ liệu C DỮ C DỮ L case RH: T->balFactor =EH; trú T1->balFactor= LH; break; U TRÚ ẤU ẤU TRÚ C Cấu CẤ }T2->balFactor =EH; T=T2} 11
  12. CẤCấuCẤUU TRÚ TRÚ trúCCc DỮ DỮdữ L LIỆU IỆUliệu V V À Àvà GIẢI GIẢI thu THUẬT THUẬật gTiải 1 1 Cân Cân bằng lại trường hợp 3 L Click Click To Master Edit Title Style L1 T T1 R1 12 L T L1 T1 R1
  13. CàiClick đặt cân To bằngEdit Masterlại cho trường Title Style hợp 3 void RR(AVLTree &T) { AVLNode *T1= T->pRight; T->pRight=T1->pLeft; T1->pLeft=T; switch(T1-> balFactor) { 1 iải T 1 case RH: T-> balFactor = EH; ật g ật THUẬ THUẬT thu T-> balFactor = EH; break; À À GIẢI À GIẢI À GIẢI và case EH: T-> balFactor = RH; IỆU V LIỆU V T1-> balFactor = LH; break; c dữ liệu C DỮ } C DỮ L trú T=T1 U TRÚ ẤU ẤU TRÚ C Cấu CẤ } 13
  14. CẤCấuCẤUU TRÚ TRÚ trúCCc DỮ DỮdữ L LIỆU IỆUliệu V V À Àvà GIẢI GIẢI thu THUẬT THUẬật gTiải 1 1 Cân Cân bằng lại trường hợp 4 L L21 Click Click To Master Edit Title Style T2 T R21 T1 R1 14 L T L21 T2 R21 T1 R1
  15. CàiClick đặt cân To bằngEdit Masterlại cho trường Title Style 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; 1 iải switch(T2-> balFactor) T 1 { case RH: T-> balFactor = LH; ật g ật THUẬ THUẬT T1-> balFactor = EH; break; thu À À GIẢI case EH: T-> balFactor = EH; À GIẢI À GIẢI và T1-> balFactor = EH; break; IỆU V LIỆU V case LH: T-> balFactor = EH; c dữ liệu C DỮ T1-> balFactor = RH; break; C DỮ L } trú U TRÚ ẤU ẤU TRÚ T2-> balFactor =EH; T=T2;} C Cấu CẤ 15
  16. CẤCấuCẤUU TRÚ TRÚ trúCCc DỮ DỮdữ L LIỆU IỆUliệu V V À Àvà GIẢI GIẢI thu THUẬT THUẬật gTiải 1 1 Thêm 1 nút    cân bằng Vi N Th Click Click To Master Edit Title Style . . ếu cây tăng ếu câytrưởng tăng chiều cao ệc cân bằnglạichỉ cần thực hiện 1lầnnơimất êm bình thườngnhư trường hợp cây NPTK bằng thích bằng thích hợp Ti bằng L ần ngược ần ngược vềgốc để phát hiệnnút bị mất cân ến hành cân ến bằng hành cân đó lại nút tác bằng thao cân 16
  17. CẤCấuCẤUU TRÚ TRÚ trúCCc DỮ DỮdữ L LIỆU IỆUliệu V V À Àvà GIẢI GIẢI thu THUẬT THUẬật gTiải 1 1 Hủy 1 Hủy nút    gốc lên thểlan tận truyền co bằnglại cân Việc giảm cao: chiều Nếu cây NPTK hợp câybình thường nhưtrường Hủy Click Click To Master Edit Title Style . . . Tiếp tục Tiếp tục lần ngược lênnút cha bằng thích hợp cân Tiến nút hành thao tác bằng lại đó bằng cân bằng Lần ngược vềgốc để phát hiện nút bị mất cân 17