CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 7: CÂY NHỊ PHÂN TÌM KIẾM

Tham khảo bài thuyết trình cấu trúc dữ liệu và giải thuật - chương 7: cây nhị phân tìm kiếm, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
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 7: CÂY NHỊ PHÂN TÌM KIẾMCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1Cấu trúc dữ liệu và thuật giải Click To Edit1 NỘMaster CÂY NHỊ PHÂN TÌM KIẾM I DUNGTitle Style Click Ðịnh nghĩaTo câyEdit Master nhị phân Title tìm 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 cTo EditnhMaster ủa cây Title ị phân tìm kiếmStyle • 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 Cấu trúc dữ liệu và thuật giải – Trường hợp xấu nhất h = LnCẤ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 dTo ữ liệEdit u củaMaster cây nhị Title Style phân 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 Totrên thao tác Editcây Master Title nhị phân tìm Style 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ỗTo ng Edit Master Title Style • Cây rỗng -> địa chỉ nút gốc bằng NULL void CreateTree(TREE &T) { T=NULL; } Cấu trúc dữ liệu và thuật giảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 6 ...