Bài giảng Thiết kế và đánh giá thuật toán: Cây tìm kiếm nhị phân - TS. Lê Nguyên Khôi

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