Đề tài cuối kì Môn: Cấu trúc dữ liệu 2 Lớp 0811cl2 Nhóm thực hiện: - Vũ Chí Phương - Nguyễn Nhân Nghĩa Phần I - Cây đỏ đen (Red Black 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. Quy tắc của cây đỏ đen  Cây đỏ đen là một cây nhị phân tìm kiếm( BST) tuân thủ các quy tắc sau:  Mọi node phải là đỏ hoặc đen.  Node gốc và các node lá phải luôn luôn đen.  Nếu một node là đỏ, những node con của nó phải đen.  Mọi đường dẫn từ gốc đến một lá phải có cùng số lượng node đen hay có cùng chiều cao đen black height(bh).