Cây đỏ đen và AA Tree

_

—Cây đỏ đen là một dạn cây tìm kiếm nhị phân tự cân bằng.

—Cấu trúc ban đầu của nó được đưa ra vào năm 1972 bởi Rudolf Bayer với tên là “B-cây cân bằng” còn tên hiện nay được đưa ra từ 1978 bởi Leo J. Guibas và Robert Sedgewick.

—Nó là một cấu trúc phức tạp nhưng cho kết quả tốt về thời gian thực hiện trong trường hợp xấu nhất.

—Các phép toán như tìm kiếm (search), chèn ( insert), và xóa (delete) thực hiện trong thời gian O(log n).

Thay vì thời gian là O (n) như cây nhị phân thông thường trong trường hợp dữ liệu đã được sắp xếp trước khi chèn.