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

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útCá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)
Nội dung trích xuất từ tài liệu:
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ẰNGCCẤẤUUTRÚC UUVÀ GI THU ẢI ITHU TT11 trúcDDdỮỮCấu TRÚC ữLILIliỆỆệ uVÀvàGIẢthu gi ậtẬẬ ải Click To Edit1 NỘMaster CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG I 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 ải TT11 Ví dụ: 23 88 uVÀvà UUVÀ GIẢthu GI THU ẢI ITHU gi ậtẬẬ 13 37 59 108Cấu TRÚCCCẤẤUUTRÚC ữLILIliỆỆệ trúcDDdỮỮ 15 30 40 55 71 2 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ÚCCCẤẤUUTRÚC ữLILIliỆỆệ trúcDDdỮỮ 3 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ỆỆệ ...