Bài giảng Cấu trúc dữ liệu và giải thuật: Cây nhị phân tìm kiếm

Bài giảng "Cấu trúc dữ liệu và giải thuật: Cây nhị phân tìm kiếm" cung cấp cho người đọc các kiến thức: Định nghĩa cây nhị phân tìm kiếm, ưu điểm của cây nhị phân tìm kiếm, cấu trúc dữ liệu của cây nhị phân tìm kiếm,.... 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: Cây nhị phân tìm kiếm NỘIMaster Click To Edit DUNGTitle Style Ðị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 44 CÂY NHỊ PHÂN TÌM KIẾM Cấu trúc dữ liệu và thuật giải Cấu trúc dữ liệu và thuật giải Ví dụ:CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 18 88 13 37 59 108 15 23 40 55 71 1 2 Ưu Click điểm của To cây EditnhịMaster phân tìm kiếm Title Style CấuClick trúc dữ Toliệu củaMaster Edit cây nhị Title phân Style tìm kiếm • Nhờ trật tự bố trí khóa trên cây : • Cấu trúc dữ liệu của 1 nút – Định hướng được khi tìm kiếm typedef struct tagTNode • Cây gồm N phần tử : { – Trường hợp tốt nhất h = log2N, int Key; //trường dữ liệu là 1 số nguyên – Trường hợp xấu nhất h = LnN struct tagTNode *pLeft; Cấu trúc dữ liệu và thuật giải Cấu trúc dữ liệu và thuật giảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT – Tình huống xảy ra trường hợp xấu nhất ? struct tagTNode *pRight; }TNode; • Cấu trúc dữ liệu của cây ...