tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu nâng cao - Nguyễn Tri Tuấn

Bài giảng "Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu nâng cao" cung cấp cho người đọc các kiến thức: Cây nhị phân tìm kiếm cân bằng, B-Cây, bảng băm - Hash table. | Các cấu trúc dữ liệu nâng cao Advanced Data Structures Cây nhị phân tìm kiếm cân bằng B-Cây Bảng băm Hash Table Winter 2017 123 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Cây nhị phân tìm kiếm cân bằng 1 Cây BST có thể bị lệch Vì sao cây BST trở nên bị lệch Chi phí tìm kiếm trên cây bị lệch Một cây BST không cân bằng Winter 2017 124 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Cây nhị phân tìm kiếm cân bằng 2 Cây cân bằng chiều cao và chi phí tìm kiếm tối ưu O log2N Winter 2017 125 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Cây nhị phân tìm kiếm cân bằng 3 Cần có phương pháp để duy trì tính cân bằng cho cây BST Winter 2017 126 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Cây nhị phân tìm kiếm cân bằng 4 Các loại cây BST cân bằng Cây AVL Cây Đỏ - Đen Red Black tree Cây AA Winter 2017 127 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Cây AVL 1 Định nghĩa Cài đặt cấu trúc dữ liệu Mất cân bằng khi thêm xóa node Các thuật toán điều chỉnh cây Đánh giá so sánh E. M. Landis G. M. Adelson-Velskii Winter 2017 128 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Cây AVL 2 Cấu trúc cây AVL do 2 tác giả người Liên xô G. M. Adelson-Velskii và E. M. Landis công bố năm 1962 Đây là mô hình cây tự cân bằng đầu tiên được đề xuất self-adjusting height- balanced binary search tree Winter 2017 129 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Định nghĩa cây AVL 1 Cây AVL Là một cây nhị phân tìm kiếm BST Mỗi nút p của cây đều thỏa chiều cao của cây con bên trái p- gt left và chiều cao của cây con bên phải p- gt right chênh lệch nhau không quá 1 p TAVL abs hp- gt left - hp- gt right 1 Winter 2017 130 C Nguyen Tri Tuan - Truong