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

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.
Nội dung trích xuất từ tài liệu:
Báo cáo: Cây nhị phân tìm kiếm cân bằngCẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải CẤU t ÚC dữ ệu v G Ả HU T1 NỘI DUNG CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG Click To Edit Master Title Style Ðị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 44Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiảiCẤ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 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ảiCẤ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 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ằngCấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiảiCẤ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 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 RCấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiảiCẤ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 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 T1Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiảiCẤ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 Các thao To Edit cây cân Title Style Click tác trên Master bằng ...