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

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.
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 1: Chương 9CẤU TRÚC CẤUTRÚC DỮ LIỆU VÀGIẢI GIẢITHUẬT THUẬT11Cấu trúcDỮ liệuVÀ dữLIỆU 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 Ðị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 71CấuCẤU 2 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ấuCẤU TRÚC CẤUTRÚC DỮ trúcDỮ LIỆU dữLIỆU 3 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ấuCẤU 4 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 ...