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

Báo cáo: Cây nhị phân tìm kiếm cân bằng

Chia sẻ: Vo Vui | Ngày: | Loại File: PPT | Số trang:17

Thêm vào BST
Báo xấu
232
lượt xem 25
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. Lần ngược về gốc để phát hiện nút bị mất cân bằng. Tiến hành cân bằng lại nút đó bằng thao tác cân bằng thích hợp.

Chủ đề:

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

Lưu

Nội dung Text: Báo cáo: Cây nhị phân tìm kiếm cân bằng

  1. CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU t ÚC dữ ệu v G Ả HU T 1 NỘI DUNG CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG Click To Edit Master Title Style
  2. Ðịnh nghĩa Edit Master Title Style Click To  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 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 Ví dụ: 23 88 CẤU t ÚC dữ ệu v G Ả HU T 59 108 13 37 15 30 40 55 71 2
  3. Tổ Click dữ liệu Master Title Style chức To Edit  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) Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11  CSCB(p) = 1 ⇔ Độ cao cây trái (p) < Độ cao CẤU t ÚC dữ ệu v G Ả HU T cây phải (p) ⇔ Độ cao cây trái (p) > Độ  CSCB(p) = -1 cao cây phải (p) 3
  4. Tổ Click dữ liệu(tt) chức To 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 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 CẤU t ÚC dữ ệu v G Ả HU T Data key; struct tagAVLNode* pLeft; struct tagAVLNode* pRight; }AVLNode; typedef AVLNode *AVLTree; 4
  5. CácClick ToợEdit Masterng do lệch trái trường h p mất cân bằ Title Style Cây mất cân bằng tại nút T T TH1: Left-Left TH2: Left-Right T T1 R T1 R Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 CẤU t ÚC dữ ệu v G Ả HU T R1 L1 T2 L1 R21 L21 5
  6. CácClick ToợEdit Masterng do lệch phải trường h p mất cân bằ Title Style Cây mất cân bằng tại nút T TH3: Right-Right TH4: Right-Left T T L L T1 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 T1 CẤU t ÚC dữ ệu v G Ả HU T T2 R1 L1 R1 R21 L21 6
  7. Các thao To Edit cây cân Title Style Click tác trên Master bằng  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 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 CẤU t ÚC dữ ệu v G Ả HU T  Lệch nhánh phải, thêm bên phải  Lệch nhánh trái, hủy bên phải  Lệch nhánh phải, hủy bên trái  Câ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ấp 7
  8. CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU t ÚC dữ ệu v G Ả HU T L1 T1 R1 T R 8 L1 Cân bằng lạiEdit ng hợp 1 T1 R1 T Click To trườMaster Title Style R
  9. CàiClick Tobằng Mastertrường hợp 1 đặt cân Edit lại cho Title Style void LL(AVLTree &T) { AVLNode *T1=T->pLeft; T->pLeft = T1->pRight; T1->pRight=T; switch(T1-> balFactor) Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 CẤU t ÚC dữ ệu v G Ả HU T { case LH: T-> balFactor =EH; T1->balFactor=EH; break; case EH: T->balFactor=LH; T1->balFactor =RH; break; } T=T1; } 9
  10. CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU t ÚC dữ ệu v G Ả HU T L1 T1 L21 T2 T R21 R 10 L1 T1 Cân bằng lạiEdit ng hợp 2 L21 T2 R21 T Click To trườMaster Title Style R
  11. CàiClick Tobằng Mastertrường hợp 2 đặt cân Edit lại cho 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; Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 CẤU t ÚC dữ ệu v G Ả HU T 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} 11
  12. CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU t ÚC dữ ệu v G Ả HU T L T L1 T1 R1 12 L T Cân bằng lạiEdit ng hợp 3 L1 T1 R1 Click To trườMaster Title Style
  13. CàiClick Tobằng Mastertrường hợp 3 đặt cân Edit lại cho Title Style void RR(AVLTree &T) { AVLNode *T1= T->pRight; T->pRight=T1->pLeft; T1->pLeft=T; switch(T1-> balFactor) { Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 CẤU t ÚC dữ ệu v G Ả HU T case RH: T-> balFactor = EH; T-> balFactor = EH; break; case EH: T-> balFactor = RH; T1-> balFactor = LH; break; } T=T1 } 13
  14. CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU t ÚC dữ ệu v G Ả HU T L L21 T T2 T1 R21 R1 14 L T Cân bằng lạiEdit ng hợp 4 L21 T2 R21 T1 Click To trườMaster Title Style R1
  15. CàiClick Tobằng Mastertrường hợp 4 đặt cân Edit lại cho 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; Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 switch(T2-> balFactor) CẤU t ÚC dữ ệu v G Ả HU T { 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;} 15
  16. Thêm 1 nút Edit Master Title Style Click To  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 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11 CẤU t ÚC dữ ệu v G Ả HU T  Tiến hành cân bằng lại nút đó bằng thao tác cân bằng thích hợp  Việc cân bằng lại chỉ cần thực hiện 1 lần nơi mất cân bằng 16
  17. Hủy 1 nút Edit Master Title Style Click To  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 Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11  Tiến hành cân bằng lại nút đó bằng thao tác cân CẤU t ÚC dữ ệu v G Ả HU T bằng thích hợp  Tiếp tục lần ngược lên nút cha…  Việc cân bằng lại co thể lan truyền lên tận gốc 17
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.09: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Quản Trị Kinh Doanh
81 tài liệu
1643 lượt tải
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