intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Lê Trinh Vàng | Ngày: | Loại File: PPT | Số trang:17

Thêm vào BST
Báo xấu
102
lượt xem 11
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 . 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)

Chủ đề:

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

Lưu

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. CCẤẤUUTRÚC UUVÀ GI THU ẢI ITHU TT11 trúcDDdỮỮ Cấu TRÚC ữLILIliỆỆệ uVÀvàGIẢthu gi ậtẬẬ ải Click To Edit 1 NỘMaster CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG I DUNGTitle Style
  2. Click Ðịnh To Edit Master Title Style 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 44 ải TT11 Ví dụ: 23 88 uVÀvà UUVÀ GIẢthu GI THU ẢI ITHU gi ậtẬẬ 13 37 59 108 Cấu TRÚC CCẤẤUUTRÚC ữLILIliỆỆệ trúcDDdỮỮ 15 30 40 55 71 2
  3. Tổ Click chức dTo ữ liEdit ệu 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) ải TT11  CSCB(p) = 1 ⇔ Độ cao cây trái (p) < Độ cao THU ẢI ITHU gi ậtẬẬ cây phải (p) GIẢthu  CSCB(p) = -1 ⇔ Độ cao cây trái (p) > Độ GI uVÀvà UUVÀ cao cây phải (p) Cấu TRÚC CCẤẤUUTRÚC ữLILIliỆỆệ trúcDDdỮỮ 3
  4. Tổ Click chức dTo ữ liEdit ệu(tt)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 { char balFactor; //chỉ số cân bằng gi ậtẬẬ THU ải TT11 Data key; ẢI ITHU GIẢthu struct tagAVLNode* pLeft; GI uVÀvà UUVÀ struct tagAVLNode* pRight; ữLILIliỆỆệ }AVLNode; trúcDDdỮỮ Cấu TRÚC CCẤẤUUTRÚC typedef AVLNode *AVLTree; 4
  5. CácClick trườngTo hợEdit p mấMaster Title t cân bằng Style do lệch 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 ậtẬẬ THU ẢI ITHU GIẢthu ải TT11 gi L1 R1 GI uVÀvà L1 T2 UUVÀ Cấu TRÚC CCẤẤUUTRÚC ữLILIliỆỆệ trúcDDdỮỮ L21 R21 5
  6. CácClick trườngTo hợEdit p mấMaster Title t cân bằng Style do lệch 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 T1 ải TT11 T1 GI uVÀvà ẢI ITHU GIẢthu gi ậtẬẬ THU T2 R1 UUVÀ L1 R1 Cấu TRÚC CCẤẤUUTRÚC ữLILIliỆỆệ trúcDDdỮỮ L21 R21 6
  7. CácClick thao To tác Edit Master trên cây cân Title bằ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 gi ậtẬẬ ải TT11  Lệch nhánh phải, thêm bên phải THU ẢI ITHU GIẢthu  Lệch nhánh trái, hủy bên phải GI uVÀvà UUVÀ  Lệch nhánh phải, hủy bên trái ữLILIliỆỆệ  Cân bằng lại cây : tìm cách bố trí lại cây sao cho trúcDDdỮỮ chiều cao 2 cây con cân đối: Cấu TRÚC CCẤẤUUTRÚC  Kéo nhánh cao bù cho nhánh thấp 7
  8. CCẤẤUUTRÚC UUVÀ GI THU ẢI ITHU TT11 trúcDDdỮỮ Cấu TRÚC ữLILIliỆỆệ uVÀvàGIẢthu gi ậtẬẬ ải L1 T1 CânClick R1 T bằngTo lạiEdit R 8 trường L1 Master T1 R1 T hợp 1Title Style R
  9. CàiClick TobEdit đặt cân ằng Master lại cho trTitle ườngStyle hợp 1 void LL(AVLTree &T) { AVLNode *T1=T->pLeft; T->pLeft = T1->pRight; T1->pRight=T; switch(T1-> balFactor) gi ậtẬẬ ải TT11 { case LH: T-> balFactor =EH; THU ẢI ITHU GIẢthu T1->balFactor=EH; break; GI uVÀvà case EH: T->balFactor=LH; UUVÀ ữLILIliỆỆệ T1->balFactor =RH; break; trúcDDdỮỮ } Cấu TRÚC CCẤẤUUTRÚC T=T1; } 9
  10. CânClick bằngTo lạiEdit Master trường hợp 2Title Style T T2 T1 R T1 T ải TT11 gi T2 ậtẬẬ L1 THU L21 R21 R ẢI ITHU L1 uVÀvà UUVÀ GIẢthu GI L21 R21 Cấu TRÚC CCẤẤUUTRÚC ữLILIliỆỆệ trúcDDdỮỮ 10
  11. CàiClick TobEdit đặt cân ằng Master lại cho trTitle ườngStyle 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; ải TT11 gi switch(T2->balFactor) ậtẬẬ THU ẢI ITHU { case LH: T->balFactor=RH; GIẢthu T1->balFactor=EH; break; GI uVÀvà UUVÀ case EH: T->balFactor = EH; ữLILIliỆỆệ T1->balFactor=EH; break; trúcDDdỮỮ case RH: T->balFactor =EH; Cấu TRÚC CCẤẤUUTRÚC T1->balFactor= LH; break; }T2->balFactor =EH; T=T2 11 }
  12. CCẤẤUUTRÚC UUVÀ GI THU ẢI ITHU TT11 trúcDDdỮỮ Cấu TRÚC ữLILIliỆỆệ uVÀvàGIẢthu gi ậtẬẬ ải L T L1 CânClick T1 bằngTo R1 lạiEdit 12 L trường T Master L1 T1 R1 hợp 3Title Style
  13. CàiClick TobEdit đặt cân ằng Master lại cho trTitle ườngStyle hợp 3 void RR(AVLTree &T) { AVLNode *T1= T->pRight; T->pRight=T1->pLeft; T1->pLeft=T; switch(T1-> balFactor) { gi ậtẬẬ ải TT11 case RH: T-> balFactor = EH; THU ẢI ITHU GIẢthu T-> balFactor = EH; break; GI uVÀvà case EH: T-> balFactor = RH; UUVÀ ữLILIliỆỆệ T1-> balFactor = LH; break; trúcDDdỮỮ } Cấu TRÚC CCẤẤUUTRÚC T=T1 } 13
  14. CânClick bằngTo lạiEdit Master trường hợp 4Title Style T T2 L T1 T T1 ải TT11 T2 R1 gi ậtẬẬ R1 THU L L21 R21 GI uVÀvà UUVÀ ẢI ITHU GIẢthu L21 R21 Cấu TRÚC CCẤẤUUTRÚC ữLILIliỆỆệ trúcDDdỮỮ 14
  15. CàiClick TobEdit đặt cân ằng Master lại cho trTitle ườngStyle 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; ải TT11 switch(T2-> balFactor) gi ậtẬẬ THU { case RH: T-> balFactor = LH; ẢI ITHU GIẢthu T1-> balFactor = EH; break; GI uVÀvà case EH: T-> balFactor = EH; UUVÀ T1-> balFactor = EH; break; ữLILIliỆỆệ case LH: T-> balFactor = EH; trúcDDdỮỮ T1-> balFactor = RH; break; Cấu TRÚC CCẤẤUUTRÚC } T2-> balFactor =EH; T=T2;} 15
  16. Click Thêm To Edit Master Title Style 1 nút  Thêm bình thường như trường hợp cây NPTK  Nếu cây tăng trưởng chiều cao  Lần ngược về gốc để phát hiện nút bị mất cân bằng gi ậtẬẬ THU ải TT11  Tiến hành cân bằng lại nút đó bằng thao tác cân ẢI ITHU GIẢthu bằng thích hợp GI uVÀvà UUVÀ ữLILIliỆỆệ  Việc cân bằng lại chỉ cần thực hiện 1 lần nơi mất trúcDDdỮỮ cân bằng Cấu TRÚC CCẤẤUUTRÚC 16
  17. HủyClick 1 nútTo Edit Master Title Style  Hủy bình thường như trường hợp cây NPTK  Nế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ằng ải TT11  Tiến hành cân bằng lại nút đó bằng thao tác cân THU ẢI ITHU gi ậtẬẬ bằng thích hợp GIẢthu GI uVÀvà  Tiếp tục lần ngược lên nút cha… UUVÀ ữLILIliỆỆệ trúcDDdỮỮ  Việc cân bằng lại co thể lan truyền lên tận Cấu TRÚC CCẤẤUUTRÚC gốc 17
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2