1. Tính chất của cây đỏ đen

• Mỗi nút là màu đỏ hoặc màu đen.
• Nút gốc luôn là màu đen.
• Nếu một nút là màu đỏ, thì cả hai nút con của nó phải là màu đen.
• Tất cả các đường đi từ một nút đến tất cả các nút lá đều chứa cùng số lượng nút đen.
• Tất cả các nút lá (nút rỗng) đều là màu đen.

2. Nút của cây đỏ đen

Trong cây đỏ đen, thay vì sử dụng "hệ số cân bằng" như trong cây AVL, chúng ta sử dụng màu sắc (đen hoặc đỏ) để duy trì tính cân bằng.

enum Color {
    RED,
    BLACK
};

template<class K, class V>
struct RBTreeNode {
    RBTreeNode<K, V>* left;
    RBTreeNode<K, V>* right;
    RBTreeNode<K, V>* parent;
    std::pair<K, V> kv;
    Color col;

    RBTreeNode(const std::pair<K, V>& kv)
        : left(nullptr), right(nullptr), parent(nullptr), kv(kv), col(RED) {}
};

3. Thêm nút vào cây đỏ đen

Cây đỏ đen được xây dựng dựa trên cây tìm kiếm nhị phân, do đó quy tắc thêm nút tương tự: nếu giá trị nhỏ hơn nút hiện tại, di chuyển sang trái; nếu lớn hơn, di chuyển sang phải. Tuy nhiên, sau khi thêm, cần điều chỉnh để đảm bảo tính chất của cây đỏ đen.

bool Insert(const std::pair<K, V>& kv) {
    if (root == nullptr) {
        root = new Node(kv);
        root->col = BLACK;
        return true;
    }

    Node* parent = nullptr;
    Node* current = root;
    while (current) {
        if (current->kv.first < kv.first) {
            parent = current;
            current = current->right;
        } else if (current->kv.first > kv.first) {
            parent = current;
            current = current->left;
        } else {
            return false;
        }
    }

    current = new Node(kv); // Màu đỏ
    if (parent->kv.first < kv.first) {
        parent->right = current;
    } else {
        parent->left = current;
    }
    current->parent = parent;
}

3.1. Cân bằng cây đỏ đen

Vì nút mới mặc định có màu đỏ, nếu nút cha cũng là màu đỏ, sẽ vi phạm tính chất không có hai nút đỏ liên tiếp. Do đó, cần thực hiện các phép quay và đổi màu.

3.1.1. Trường hợp nút cha là nút con trái của nút ông

Trường hợp 1:

• Nếu nút chú (nút anh em của nút cha) tồn tại và có màu đỏ, đổi màu cho nút cha, nút chú thành đen, nút ông thành đỏ. Tiếp tục kiểm tra từ nút ông.
• Nếu nút ông là nút gốc, đổi màu nút ông thành đen.

if (uncle && uncle->col == RED) {
    parent->col = uncle->col = BLACK;
    grandfather->col = RED;
    current = grandfather;
    parent = current->parent;
}

Trường hợp 2:

• Nếu nút chú không tồn tại hoặc có màu đen, thực hiện quay phải với nút ông, đổi màu cho nút cha và nút ông.

RotateRight(grandfather);
parent->col = BLACK;
grandfather->col = RED;

Trường hợp 3:

• Nếu nút mới nằm bên trái nút cha, thực hiện quay trái với nút cha, sau đó quay phải với nút ông, đổi màu cho nút mới và nút ông.

RotateLeft(parent);
RotateRight(grandfather);
current->col = BLACK;
grandfather->col = RED;

3.1.2. Trường hợp nút cha là nút con phải của nút ông

Trường hợp 4:

• Tương tự trường hợp 1.

parent->col = uncle->col = BLACK;
grandfather->col = RED;
current = grandfather;
parent = current->parent;

Trường hợp 5:

• Thực hiện quay trái với nút ông, đổi màu cho nút cha và nút ông.

RotateLeft(grandfather);
parent->col = BLACK;
grandfather->col = RED;

Trường hợp 6:

• Tương tự trường hợp 3, nhưng thực hiện quay phải với nút cha, sau đó quay trái với nút ông, đổi màu cho nút mới và nút ông.

RotateRight(parent);
RotateLeft(grandfather);
current->col = BLACK;
grandfather->col = RED;

Đoạn mã tổng hợp:

while (parent && parent->col == RED) {
    Node* grandfather = parent->parent;
    if (parent == grandfather->left) {
        Node* uncle = grandfather->right;
        if (uncle && uncle->col == RED) {
            parent->col = uncle->col = BLACK;
            grandfather->col = RED;
            current = grandfather;
            parent = current->parent;
        } else {
            if (current == parent->left) {
                RotateRight(grandfather);
                parent->col = BLACK;
                grandfather->col = RED;
            } else {
                RotateLeft(parent);
                RotateRight(grandfather);
                current->col = BLACK;
                grandfather->col = RED;
            }
            break;
        }
    } else {
        Node* uncle = grandfather->left;
        if (uncle && uncle->col == RED) {
            parent->col = uncle->col = BLACK;
            grandfather->col = RED;
            current = grandfather;
            parent = current->parent;
        } else {
            if (current == parent->right) {
                RotateLeft(grandfather);
                parent->col = BLACK;
                grandfather->col = RED;
            } else {
                RotateRight(parent);
                RotateLeft(grandfather);
                current->col = BLACK;
                grandfather->col = RED;
            }
            break;
        }
    }
}
root->col = BLACK;

Kiểm tra cân bằng của cây đỏ đen

• Không có hai nút đỏ liên tiếp.
• Số nút đen trên mọi đường đi từ nút gốc đến nút lá phải bằng nhau.

bool IsBalanced() {
    if (root && root->col == RED) return false;

    int refBlackNum = 0;
    Node* current = root;
    while (current) {
        if (current->col == BLACK) refBlackNum++;
        current = current->left;
    }

    return Check(root, 0, refBlackNum);
}

bool Check(Node* current, int blackNum, int refBlackNum) {
    if (current == nullptr) {
        if (refBlackNum != blackNum) {
            std::cout << "Số nút đen không khớp." << std::endl;
            return false;
        }
        return true;
    }

    if (current->col == RED && current->parent->col == RED) {
        std::cout << current->kv.first << " có nút đỏ liên tiếp." << std::endl;
        return false;
    }

    if (current->col == BLACK) blackNum++;

    return Check(current->left, blackNum, refBlackNum) &&
           Check(current->right, blackNum, refBlackNum);
}