Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - ThS. Trịnh Quốc Sơn (ĐH Công nghệ Thông tin8

Chia sẻ: May Trời Gio Bien | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

67
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "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" cung cấp cho người học các kiến thức: Định nghĩa, tổ chức dữ liệu, các trường hợp mất cân bằng do lệch trái, các trường hợp mất cân bằng do lệch phải, cân bằng lại,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - ThS. Trịnh Quốc Sơn (ĐH Công nghệ Thông tin8

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