Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Trường ĐH Công nghệ Thông tin

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 trình bày nội dung về cây nhị phân tìm kiếm, cây nhị phân tìm kiếm cân bằng: định nghĩa, cấu trúc dữ liệu, các thao tác trên cây nhị phân tìm kiếm, Các trường hợp mất cân bằng. Kính mời quý đọc giả 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 7 - Trường ĐH Công nghệ Thông tin NỘIMaster Click To Edit DUNGTitle Style CÂY NHỊ PHÂN TÌM KIẾM Cấu trúc dữ liệu và thuật giải CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNGCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 1 Ðịnh nghĩaTo Click cây nhị Master Edit phân tìm Title kiếm Style • Cây nhị phân • Bảo đảm nguyên tắc bố trí khoá tại mỗi nút: – Các nút trong cây trái nhỏ hơn nút hiện hành – Các nút trong cây phải lớn hơn nút hiện hành Cấu trúc dữ liệu và thuật giảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Ví dụ: 18 13 37 15 23 40 2 Ưu Click điểm của To cây Editnhị phân tìm Master kiếm Title Style • Nhờ trật tự bố trí khóa trên cây : – Định hướng được khi tìm kiếm • Cây gồm N phần tử : – Trường hợp tốt nhất h = log2N – Trường hợp xấu nhất h = Ln Cấu trúc dữ liệu và thuật giảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 – Tình huống xảy ra trường hợp xấu nhất ? 3 CấuClick trúc dữ Toliệu củaMaster Edit cây nhị Title phân Style tìm kiếm • Cấu trúc dữ liệu của 1 nút typedef struct tagTNode { int Key; //trường dữ liệu là 1 số nguyên struct tagTNode *pLeft; Cấu trúc dữ liệu và thuật giảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 struct tagTNode *pRight; }TNode; • Cấu trúc dữ liệu của cây typedef TNode *TREE; 4 CácClick thao tác To trên Editcây nhị phân Master tìmStyle Title kiếm Tạo 1 cây rỗng Tạo 1 nút có trường Key bằng x Thêm 1 nút vào cây nhị phân tìm kiếm Cấu trúc dữ liệu và thuật giảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Xoá 1 nút có Key bằng x trên cây Tìm 1 nút có khoá bằng x trên cây 5 TạoClick cây rỗng To Edit Master Title Style • Cây rỗng -> địa chỉ nút gốc bằng NULL void CreateTree(TREE &T) { T= ...