Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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. nội dung chi tiết. | 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 Các cấu trúc dữ liệu nâng cao (Advanced Data Structures) 3.1 Cây nhị phân tìm kiếm cân bằng 3.2 B-Cây 3.3 Bảng băm – Hash Table Winter 2017 123 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/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 DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/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 DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/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 DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/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 DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/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 DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/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 DH.KHTN DHQG-HCM CuuDuongThanCong.com .
