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

Bài giảng Cấu trúc dữ liệu và giải thuật 1: Chương 9

Chia sẻ: ViTokyo2711 ViTokyo2711 | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST
Báo xấu
42
lượt xem 5
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 1: Chương 9 trình bày các nội dung chính sau: Cây nhị phân tìm kiếm cân bằng, 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 thao tác trên cây cân bằng,... Mời các bạn cùng tham khảo để nắm 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 1: Chương 9

  1. CẤU TRÚC CẤUTRÚC DỮ LIỆU VÀGIẢI GIẢITHUẬT THUẬT11 Cấu trúcDỮ liệuVÀ dữLIỆU 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
  2. Ðịnh nghĩa Click To Edit Master Title Style  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 11 23 88 Ví dụ: VÀ liệuVÀ GIẢI và THUẬT THUẬT thuật 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
  3. Tổ Click chức dữ To liệu 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  CSCB(p) = 1  Độ cao cây trái (p) < Độ cao cây THUẬT THUẬT 11 phải (p) thuật 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
  4. Tổ Click chứ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 { 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
  5. CácClick trường Tohợp mất Edit cân bằng Master do lệch Title Styletrá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
  6. CácClick trường Tohợp mất Edit cân bằng Master do lệch Title Stylephả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
  7. 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Ữ chiều cao 2 cây con cân đối: TRÚC CẤUTRÚC  Kéo nhánh cao bù cho nhánh thấp Cấu CẤU 7
  8. CẤU TRÚC CẤUTRÚC DỮ LIỆU VÀGIẢI GIẢITHUẬT THUẬT11 Cấu liệuVÀ dữLIỆU trúcDỮ 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
  9. CàiClick đặt cân To bằng lại cho trường Edit Master hợp 1 Title Style 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
  10. CânClick bằngTo lạiEdit trường hợp 2Title Style Master 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 R21 LIỆU L21 Cấu CẤU TRÚC CẤUTRÚC dữLIỆU DỮ trúcDỮ 10
  11. CàiClick đặt cân To bằng lại cho trường Edit Master hợp 2 Title Style 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ẬT THUẬT 11 switch(T2->balFactor) 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 }
  12. CẤU TRÚC CẤUTRÚC DỮ LIỆU VÀGIẢI GIẢITHUẬT THUẬT11 Cấu liệuVÀ dữLIỆU trúcDỮ 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
  13. CàiClick đặt cân To bằng lại cho trường Edit Master hợp 3 Title Style 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
  14. CânClick bằngTo lạiEdit trường hợp 4Title Style Master 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
  15. CàiClick đặt cân To bằng lại cho trường Edit Master hợp 4 Title Style 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
  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ả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 bằng thích hợp GIẢI 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
  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 giải 11  Tiến hành cân bằng lại nút đó bằng thao tác cân THUẬT 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 Việc cân bằng lại co thể lan truyền lên tận TRÚC CẤUTRÚC DỮ trúcDỮ gốc Cấu CẤU 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