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

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.
Nội dung trích xuất từ tài liệu:
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 tin8CẤU CẤUTRÚC TRÚC DỮ LIỆU VÀGIẢI GIẢITHUẬT THUẬT11Cấu trúcDỮ dữLIỆU liệuVÀvà thuật giải Click To Edit1 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 71CấuCẤ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ấuCẤ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ấuCẤ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 ...