Xem mẫu
Chương 5. Cây nhị phân tìm kiếm – Cây cân bằng
Trần Minh Thái
Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn
1
Nội dung
1. Khái niệm cây AVL
2. Đặc điểm
3. Định nghĩa cấu trúc dữ liệu
4. Các kỹ thuật cân bằng cây
5. Chèn phần tử vào cây
6. Xóa phần tử khỏi cây
2
Cây nhị phân tìm kiếm cân bằng
• Phát minh: Nhà toán học Nga G. M. Adel’Son-
Vel’Skil và E. M. Landis (1962)
• Cấu trúc cây giúp tối ưu thời gian tìm kiếm
• Cây nhị phân tìm kiếm cân bằng: cây AVL
• Chi phí tìm kiếm, thêm mới, xoá trong cây n nút là
O(log n)
3
Định nghĩa
• CâyAVL là một cây nhị phân tìm kiếm
• Chiều cao cây con trái và phải của nút gốc hơn
kém nhau không quá 1
• Cả hai cây con trái và phải cũng phải là cây AVL
4
Chỉ số cân bằng (Balance factor)
Chỉ số cân bằng (bF – balance Factor) của một nút: bF = hL – hR
hL: chiều cao cây con trái
hR: chiều cao cây con phải Có 3 trường hợp:
bF = 0: hL = hR bF > 0: hL > hR bF < 0: hL < hR
5
...
- tailieumienphi.vn
nguon tai.lieu . vn