Cây đỏ đen và AA Tree

Tác giả -
Nhà xuất bản -
Ngôn ngữ Tiếng Việt
Số Trang 33
 
Sách giấy -
Ebook FREE   ĐỌC NGAY
 
Upload bởi Nguyễn Thùy Dương (27-05-2014 03:26 PM)
Tags -
Lượt đọc 184
Chia sẻ
Giới thiệu
_

—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.

Bình luận