Cây đỏ đen
Bách khoa toàn thư mở Wikipedia
Cây đỏ đen là một loại cây nhị phân tìm kiếm tự cân bằng. Nó có những đặc điểm chính như sau:
- mọi node trên cây phải có màu đỏ hoặc đen.
- node ngoài phải có màu đen.
- mọi node có màu đỏ thì con của nó phải có màu đen.
- mọi đường đi từ node gốc đến node lá phải có cùng số lượng node đen (chiều cao đen).