Bài giảng "Thiết kế và đánh giá thuật toán: Cây tìm kiếm nhị phân" cung cấp cho người học các kiến thức: Cây tìm kiếm nhị phân, dựng cây tìm kiếm nhị phân, cây tìm kiếm nhị phân cân bằng. nội dung chi tiết. | Thiết Kế & Đánh Giá Thuật Toán Cây Tìm Kiếm Nhị Phân TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung Cây tìm kiếm nhị phân (TKNP) Dựng cây TKNP Cây TKNP cân bằng Cây Đỏ - Đen Cây AVL Cây Treap 1 Định Nghĩa Cây TKNP: cây nhị phân lưu khóa ở đỉnh trong lá rỗng thỏa mãn tính chất: ≤ ≤ trong cây con trái của trong cây con phải của 6 9 2 1 4 8 2 Thao Tác Chính Cây TKNP thực hiện các tao thác chính Truy vấn: không thay đổi cấu trúc cây TKNP Tìm kiếm (SEARCH) Nhỏ nhất (MINIMUM) Lớn nhất (MAXIMUM) Trước (PREDECESSOR) Sau (SUCCESSOR) Sửa đổi: thay đổi cấu trúc cây TKNP Chèn (INSERT) Xóa (DELETE) 3 Tính Chất trong cây con trái của , trong cây con phải của ≤ ≤ Duyệt cây TKNP theo thứ tự trong, thăm các khóa theo thứ tự tăng dần Sử dụng cây TKNP cho cài đặt từ điển Cây thứ tự bộ phận (heap) là cây tìm kiếm là cây nhị phân không phải cây TKNP dùng quản lý hàng đợi ưu .
