Báo Cáo BÀI BÁO CÁO MÔN CẤU TRÚC DỮ LIỆU : Cây Đỏ Đen

BÀI BÁO CÁO MÔN CẤU TRÚC DỮ LIỆU : Cây Đỏ Đen


Mục lục:
Lời nói đầu: 2
Mục lục: 3
I- Giới thiệu: 3
II- Định nghĩa: 5
III- Các thuật toán cơ bản của Black and Red Tree 6
1- Thêm một Node mới 6
2- Xóa một node: 14
IV- Thuật toán cài đặt: 14
V- Nhận xét : 31

I- Giới thiệu:

Cây đỏ đen được ra giới thiệu bởi Rudolf Bayer trong quyển “Symmetric Binary B-Trees: Data Structure and maintenance Algorithms”, nhà xuất bản Acta Informatica, Tâp1, trang 290-306. Sau đó Leonidas J.Guibas và Robert Sedgewick đã thêm các đặc tính của cây đỏ đen và đặt tên cho nó ( Tham khảo: Guibas, L. and Sedgewick R. “ A dichromatic Framwork for Balanced Trees”, in Proc. 19th IEEE Symp. Foundations of Computer Science, trang 8-21, năm 1978).

Ta đã biết cây tìm kiếm nhị phân thông thường có những 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ử. Do đó, cây tìm kiếm nhị phân xem ra là một cấu trúc lưu trữ dữ liệu tốt.

Tuy nhiên trong một số trường hợp cây tìm kiếm nhị phân có một số hạn chế. Nó hoạt động tốt nếu dữ liệu được chèn vào cây theo thứ tự ngẫu nhiên. Tuy nhiên, 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ả.