Red-black tree là gì?

Cây đỏ đen (red-black tree) là cây tìm kiếm nhị phân tự cân bằng (self-balancing binary search tree), trong đó mỗi nút (node) chứa thêm một bit để biểu thị màu của nút, đỏ hoặc đen.

Cây đỏ đen (red-black tree) thỏa mãn các tính chất sau:

• Thuộc tính Đỏ / Đen: Mọi nút đều có màu, đỏ hoặc đen.
• Thuộc tính của nút gốc (root node): Nút gốc có màu đen.
• Thuộc tính của nút lá (leaf node): Mọi nút lá đều có màu đen.
• Thuộc tính màu đỏ: Nếu một nút màu đỏ có các nút con thì các nút con luôn có màu đen.
• Thuộc tính độ sâu (depth): Đối với mỗi nút, bất kỳ đường dẫn (path) đơn giản nào từ nút này đến bất kỳ lá nào trong số các lá con của nó đều có cùng độ sâu màu đen (black depth) tức là số lượng nút màu đen.

Mỗi nút có các thuộc tính sau:

• Màu sắc
• Key
• Con bên trái (left child)
• Con bên phải (righ child)
• Cha (parent), ngoại trừ nút gốc