1
CÂY ĐỎ ĐEN
1
Nội dung
• Giới thiệu
• Định nghĩa và tính chất cây đỏ đen
• Phép quay, cân bằng lại theo kiểu bottom-up
• Thêm nút mới, Loại bỏ nút
• Tính hiệu quả của cây đỏ đen
• Cài đặt
2
Cây tìm kiếm nhị phân
(binary search tree)
•Cây tìm kiếm nhị phân (TKNP) là cây nhị phân mà
khoá tại mỗi nút lớn hơn khoá của tất cả các nút
thuộc cây con bên trái và nhỏ hơn khoá của tất cả
các nút thuộc cây con bên phải.
20
10
17 5
15
35
22 42
37
3
Giới thiệu
•Cây tìm kiếm nhị phân thuận lợi lớn về mặt lưu trữ và truy
xuất dữ liệu trong phép toán tìm kiếm, thêm vào hay loại bỏ
một phần tử. cây TKNP là một CTDL tốt.
•Hạn chế:
– Nếu dữ liệu được chèn vào theo thứ tự đã đuợc sắp xếp sẽ
không hiệu quả. Khi đó cây nhị phân trở nên không cân
bằng.(Lệch về bên trái hoặc bên phải).
–Khi cây không cân bằng, khả năng tìm kiếm nhanh (hoặc
chèn hoặc xóa) một phần tử đã cho hạn chế
•Cây không cân bằng:
=> giải quyết: đó là cây đỏ đen, là cây tìm kiếm nhị phân có
thêm một vài đặc điểm.
4
Giới thiệu
Các node được chèn theo thứ tự tăng dần
5