Chèn vào Red Black Tree trong cấu trúc dữ liệu

Red Black Tree là Self-Balanced BST, mỗi nút màu Đỏ hoặc Đen. 3 thao tác: Search, Insert, Delete.

Giả sử chèn vào cây sau:

Ý tưởng chèn đơn giản: chèn như BST thường. Từ gốc, kiểm tra màu, chèn vị trí thích hợp. Nhưng RBT cần thủ tục bổ sung.

RBT cân bằng khi thỏa mãn:

• Gốc luôn Đen.
• Mỗi nút Đỏ hoặc Đen.
• Nút Đỏ → con phải Đen.
• Đường từ gốc đến lá NULL có số nút Đen bằng nhau.

Các bước chèn:

• Kiểm tra cây rỗng. Nếu rỗng: chèn nút mới, tô Đen (gốc phải Đen).
• Cây không rỗng: chèn nút mới làm lá, tô Đỏ.
• Nếu cha của nút mới Đỏ và anh chị em (uncle) cũng Đỏ → Flip màu cha, chú, ông (nếu ông không phải gốc). Nếu ông là gốc → flip cha và chú chỉ.
• Nếu cha Đỏ và anh chị em rỗng/NULL → Xoay (Left-Left hoặc Left-Right) nút mới và cha.

Hai loại xoay: Left-Left Rotation và Left-Right Rotation. Điều kiện áp dụng:

• Cha Đỏ, anh chị em rỗng/NULL → xoay trái/phải.
• Left-Left Rotation: flip màu cha và ông. Cha thành ông, ông thành con.

Thuật toán

RBTreeInsertion(root,key)

// Màu nút chèn mới là Đỏ
color[key] <- Red
while(key != root and color(p[key]) == Red) do
    if p[key] == left(p[p[key]]) then
        y <- right[p[p[key]]] // chú
        // Nếu cha Đỏ (có ông thay vì gốc) Flip màu
        if color[y] == Red then
            color(p[key]) <- Black
            color(p[p[key]]) <- Red
            key <- p[p[key]]
        else if key == right[p[key]] then
            key <- p[key]
            // Cha Đỏ, anh chị em NULL
            LeftRotate(root, key)
        color(p[key]) <- Black
        color(p[p[key]]) <- Red
        RightRotate(root, p[p[key]])
    else
        // đối xứng trái/phải để cân bằng
        exchange left and right elements to make it balance.
color(root) <- Black