Red Black Tree - Cây đỏ đen

I. Giới thiệu:

Cây đỏ đen (RB Tree) là một dạng cây nhị phân tìm kiếm tự cân bằng, RB Tree được giới thiệu vào năm 1972 bởi Rudolf Bayer.

Các phép toán trên chúng như tìm kiếm (search), chèn (insert), và xóa (delete) trong thời gian O(logn), trong đó n là số các phần tử của cây.

II. Tổng quan về RB Tree:

1. Các tính chất:

RB Tree là một cây tìm kiếm nhị phân (BST) nên trước hết nó thừa hưởng hết mọi tính chất của một BST thông thường. Chúng ta sẽ nói về các tính chất riêng của RB Tree. Đầu tiên, điểm đặt biệt ở RB Tree so với các BST khác đó là mỗi nút của nó có thêm một thuộc tính là color chỉ nhận một trong hai giá trị là Red hoặc Black (đỏ hoặc đen) và đây cũng là lí do tại sao nó được đặt tên là cây đỏ đen.

Các điểm đặc trưng của RB Tree so với các BST khác có thể được tóm tắt bằng 5 tình chất sau:

  1. Một node trên cây sẽ có màu là đỏ hoặc đen.
  2. Nút gốc có màu là đen.
  3. Tất cả các node NULL đều có màu đen (con của các node lá hoặc các node không đủ 2 node con).
  4. Không tồn tại một đường đi trên cây đi từ gốc đến nút NULL mà có 2 nút liên tiếp là màu đỏ (và suy ra mọi nút đỏ đều có nút cha là đen, không có con hoặc có 2 nút con là đen).
  5. Xét một node bất kì, ta luôn có tất cả các đường đi từ node đó đến các node NULL sẽ có số lượng node màu đen bằng nhau (ở đây và cả trong bài viết này, đường đi có nghĩa là đi từ một node xuống một node sâu hơn)

2. Sự cân bằng của RB-Tree.

Trước hết, cần lưu ý rằng, sự cân bằng của RB Tree không phải là tuyệt đối như cây AVL.
Từ 5 tính chất trên, ta có thể rút ra được các nhận xét như sau:

Chứng minh:

Dựa vào tính chất 4, ta luôn có số nút đen trên một đường đi là bằng nhau. Với một số luợng nút đen cho trước, đường đi ngắn nhất có thể sẽ chỉ gồm các nút đen, và đường đi dài nhất có thể sẽ có các nút đỏ, đen xen kẽ nhau (vì theo tính chất 5 ta không thể có 2 nút đen liên tiếp trên đường đi nhưng vì muốn độ dài đường đi càng lớn càng tốt nên ta sẽ thêm càng nhiều nút đỏ càng tốt, và thêm xen kẽ là cách tối ưu) mà gốc là nút đen, nên số nút đỏ trên một đường đi tối đa bằng số nút đen trên đường đi đó.

Nói các khác, chênh lệch tối đa giữa đường đi dài nhất và đường đi ngắn nhất bằng với số lượng nút đỏ tối đa có thể có trên đường đi và đúng bằng số nút đen trên đó. Từ đó ta suy ra được tính chất trên: A≤2B

Cũng từ tính chất 2 ta có thể nhận thấy rằng, nếu gọi độ dài đường đi ngắn nhất từ gốc đến một nút lá nào đó là H thì tất cả các đỉnh có khoảng cách tới gốc không vượt quá H sẽ tạo thành cây nhị phân đầy đủ có độ cao H. Kết hợp với nhận xét đầu tiên thì RB Tree sẽ có độ cao trong khoảng [log(n+1), 2log(n+1)] - nói cách khác, độ cao của RB Tree sẽ không thể vượt quá 2log(n+1).

Tham khảo thêm: https://doctrina.org/maximum-height-of-red-black-tree.html

III. Thao tác trên RB Tree:

1. Biểu diễn RB Tree:

Kiểu dữ liệu của các nút trên cây:


class Node {
    private:
        int color;
        int data;
        Node *leftChild;
        Node *rightChild;
        Node *parent;
    public:
        Node(int color, int data) {
            this->color = color;
            this->data = data;
            this->leftChild = NULL;
            this->rightChild = NULL;
            this->parent = NULL;
        }
    friend class RBTree;
};

Dữ liệu của lớp biểu diễn cây chỉ cần lưu lại nút gốc:

class RBTree {
    private:
        Node *root;
};

2. Phép quay cây

97. Attachments/Blog/2022-05-04-red-black-tree/rotate.gif

Các bạn có thể xem thêm phần này tại đây.
Mục đích của phép quay cây là để chỉnh sửa cây BST lại (mục đích thường là hướng tới việc giảm độ cao) mà cây mới sau khi quay vẫn là cây BST. Quay cây gồm có quay qua trái và quay qua phải. Phép quay sẽ được diễn ra như sau:

2.1 Quay trái

97. Attachments/Blog/2022-05-04-red-black-tree/rotateLeft.png


void RBTree::rotateLeft(Node *&ptr) {
    Node *rightChild = ptr->rightChild;

    ptr->rightChild = rightChild->leftChild;
    if (ptr->rightChild != NULL)
        ptr->rightChild->parent = ptr;

    if (ptr == this->root)
        this->root = rightChild;

    else if (ptr == ptr->parent->leftChild)
        ptr->parent->leftChild = rightChild;
    else
        ptr->parent->rightChild = rightChild;

    rightChild->leftChild = ptr;
    rightChild->parent = ptr->parent;
    ptr->parent = rightChild;
}

2.2 Quay phải

97. Attachments/Blog/2022-05-04-red-black-tree/rotateRight.png


void RBTree::rotateRight(Node *&ptr) {
    Node *leftChild = ptr->leftChild;

    ptr->leftChild = leftChild->rightChild;
    if (ptr->leftChild != NULL)
        ptr->leftChild->parent = ptr;

    if (ptr == this->root)
        this->root = leftChild;
    else if (ptr == ptr->parent->leftChild)
        ptr->parent->leftChild = leftChild;
    else
        ptr->parent->rightChild = leftChild;

    leftChild->rightChild = ptr;
    leftChild->parent = ptr->parent;
    ptr->parent = leftChild;
}

3. Insert

3.1 Chọn vị trí.

Khi thêm một giá trị vào RB Tree, ta cần chú ý cây có rỗng hay không, nếu cây đang rỗng thì ta chỉ cần cho nút đó trở thành gốc và gán cho nó màu đen.

Trong trường hợp cây không rỗng, ta sẽ duyệt như duyệt cây BST để tìm vị trí thích hợp trên cây. Cụ thể, gọi x là giá trị cần thêm vào cây. Bắt đầu từ linker = root, nếu x < linker->data thì ta đi về phía bên trái của linker. Trong trường hợp linker->leftChild là một nút NULL thì ta cho luôn nút mới vào vị trí này. Còn nếu x >= linker->data thì ta cho linker đi về nhánh phải, nếu nhánh này NULL thì cho luôn nút mới vào vị trí này.

Sau khi đã thêm được nút vào cây, ta cần chỉnh lại cấu trúc của cây để cây thỏa 5 tính chất ở trên bằng cách quay cây và đổi màu của nút. Cụ thể hơn sẽ được nói ở phần tiếp theo.

Lưu ý, mặc định thì nút mới sẽ có màu là đỏ.

void RBTree::insert(int data) {
    Node *ptr = new Node(RED,data);
    if (root == NULL) {
        root = ptr;
        root->color = BLACK;
        return;
    }   
    Node *linker = root;
    while (linker != NULL) {
        if (data < linker->data) { // go left
            if (linker -> leftChild == NULL) {
                linker->leftChild = ptr;
                break;
            } else
                linker = linker->leftChild;
        } else { // go right
            if (linker->rightChild == NULL) {
                linker->rightChild = ptr;
                break;
            } else
                linker = linker->rightChild;
        }
    }
    ptr->parent = linker;
    insertFix(ptr);
}

3.2 Chỉnh cây:

Trước hết ta có cách gọi các nút liên quan đến một nút X nào đó như sau:

97. Attachments/Blog/2022-05-04-red-black-tree/defination.png

3.2.1 Nút cha có màu đen:

Khi nút cha của nút X vừa được thêm vào có màu đen thì cây vẫn thỏa mãn đủ 5 tính chất, nên ta không cần làm gì thêm ở bước này nữa.

3.2.2 Nút cha có màu đỏ:

3.2.2.1 Nút uncle có màu đỏ:

97. Attachments/Blog/2022-05-04-red-black-tree/redred.png

Trường hợp này ta sẽ đổi màu các nút P, U, G sau đó coi G như là X mới và xử lí tiếp trên nút X mới này.

3.2.2.1 Nút uncle có màu đen:

97. Attachments/Blog/2022-05-04-red-black-tree/redblack.png

Cần lưu ý rằng, trường hợp này không xảy ra ngay từ đầu mà nó sẽ xảy ra sau khi gặp trường hợp 3.2.2.1 một số lần. Tức là sau khi ta thực hiện đổi màu trong trường hợp trên thì mới có khả năng xuất hiện trường hợp này (các bạn có thể tưởng tượng thật ra trước đó nút X là màu đen chữ không phải màu đỏ như hình vì thật chất nó là nút G cũ trong trường hợp trên mà sau đó nó mới được gán thành nút X). Và hiện tại thì đường đi từ X đến NULL vẫn có số đỉnh đen bằng với đi từ U xuống NULL.

Ta sẽ có 4 trường hợp như sau:

3.3 Giải thích thêm:

  1. Hình trong trường hợp 2 bị sai vị trí các nút T1, T2, T3 sau khi quay cây, nhưng không cần quan tâm đến các nút đó.

3.4 Code:

void RBTree::insertFix(Node *&ptr) {
    while (ptr != root && getColor(ptr) == RED && getColor(ptr->parent) == RED) {
        Node *parent = ptr->parent;
        Node *grandparent = parent->parent;
        if (parent == grandparent->leftChild) {
            Node *uncle = grandparent->rightChild;
            if (getColor(uncle) == RED) {
                setColor(uncle, BLACK);
                setColor(parent, BLACK);
                setColor(grandparent, RED);
                ptr = grandparent;
            } else {
                if (ptr == parent->rightChild) {
                    rotateLeft(parent);
                    ptr = parent;
                    parent = ptr->parent;
                }
                rotateRight(grandparent);
                setColor(grandparent, RED);
                setColor(parent, BLACK);
                ptr = parent;
            }
        } else {
            Node *uncle = grandparent->leftChild;
            if (getColor(uncle) == RED) {
                setColor(uncle, BLACK);
                setColor(parent, BLACK);
                setColor(grandparent, RED);
                ptr = grandparent;
            } else {
                if (ptr == parent->leftChild) {
                    rotateRight(parent);
                    ptr = parent;
                    parent = ptr->parent;

                }
                rotateLeft(grandparent);
                setColor(grandparent, RED);
                setColor(parent, BLACK);
                ptr = parent;
            }
        }

    }
    setColor(root, BLACK);
}

4. Delete

4.1 Tiền xử lí

Khi xóa một nút V bất kì, nếu nút V đó có cả 2 nút con thì ta hoàn toàn có thể đi tới nút X là nút có giá trị nhỏ nhất trong cây con của nút con phải hoặc nút X là nút có giá trị lớn nhất trong cây con của nút con trái. Gán V->data = X->data. Sau đó xóa nút X đi. Như vậy cũng tương đương với việc xóa trực tiếp nút V.

97. Attachments/Blog/2022-05-04-red-black-tree/delete2Node.png

Chú ý: Nếu nút V chỉ có 1 con thì ta cũng có thể làm tương tự như vậy nhưng chỉ có 1 lựa chọn (nhỏ nhất nhánh phải hoặc lớn nhất nhánh trái). Nhưng điều này cũng không cần thiết lắm vì nếu có 1 nút con duy nhất thì nút đó phải là nút lá màu đỏ, và nó sẽ thuộc trường hợp đơn giản sẽ được nói sau đây, nên việc tìm nút để thay thế là không cần thiết.

Vậy giờ ta chỉ cần quan tâm đến việc xóa nút có nhiều nhất 1 nhánh con.

Gọi U là nút con duy nhất của nút V cần xóa (nếu V không có nút con nào thì U là nút NULL và sẽ có màu đen).

Như vậy việc đầu tiên cần làm sau khi xóa V đó là để U thay vào vị trí của V sau đó ta sẽ tiến hành chỉnh cây lại nếu cần.

Nếu V và U có một nút mang màu đỏ (cả hai nút không thể cùng có màu đỏ được). Ta sẽ đổi màu của U thành đen khi đó các ràng buộc sẽ được đảm bảo. Như đã nói ở phần chú ý, nếu có duy nhất một con thì con đó phải là nút lá màu đỏ nên trường hợp này đã giải quyết được 2 trường hợp: V là lá màu đỏ, V có một nút con.

Vậy thì chỉ còn lại trường hợp V đen và không có con nào cả (U là NULL). Khi đó ta sẽ gọi hàm eraseFix

void RBTree::eraseNode(Node *&ptr) {
    Node* child = (ptr->leftChild == NULL) ? ptr->rightChild : ptr->leftChild;
    Node* parent = ptr->parent;
    // case one of ptr & child red

    if (ptr->color == RED || getColor(child) == RED) {
        //child->parent = parent;
        setParent(child, parent);
        // case ptr is root
        if (parent != NULL)
            if (parent->leftChild == ptr)
                parent->leftChild = child;
            else
                parent->rightChild = child;
        else
            root = child;
        setColor(child, BLACK); // child is red then set child as black
        delete ptr; // delete because we return right now
        return;
    }
    // luc nay ptr va child deu la mau den, nen se goi ham eraseFix
    Node *sibling = getSibling(ptr); // de tien hon cho ham eraseFix
    if (parent != NULL)
        if (parent->leftChild == ptr)
            parent->leftChild = NULL;
        else
            parent->rightChild = NULL;
    else
        root = child;
    delete ptr;
    
    eraseFix(parent, sibling);
}

void RBTree::erase(int data) {
    Node *ptr = find(data);   

    if (ptr->leftChild != NULL && ptr->rightChild != NULL) {
        Node *beErase = minimumRight(ptr);
        ptr->data = beErase->data;
        ptr = beErase;
    }
    eraseNode(ptr);
}

4.2 Chỉnh cây

Nhắc lại một lần nữa, khi đã gọi hàm eraseFix thì chắc chắn rơi vào trường hợp cả V và U đều là màu đen (V là lá và U là NULL), nhánh của U ít hơn nhánh của sibling một nút đen. Gọi sibling của U là S, cha của sibling là P, con trái và con phải của S lần lượt là SL và SR (2 nút con này có thể là NULL hoặc RED)

97. Attachments/Blog/2022-05-04-red-black-tree/deleteFixTree.png

4.3.1 SL và SR có ít nhất một nút màu đỏ

97. Attachments/Blog/2022-05-04-red-black-tree/deleteRed1.png

97. Attachments/Blog/2022-05-04-red-black-tree/deleteRed3.webp

97. Attachments/Blog/2022-05-04-red-black-tree/deleteRed4.png

P/S: Đổi màu trước hay quay trước đều được cả, không ảnh hưởng đến kết quả. Trong trường hợp 1 và 3, nếu cả hai nút con của S đều là đỏ thì cũng không ảnh hưởng đến kết quả, nhưng nếu nút con ở vị trí thuận không phải màu đỏ (trường hợp 2 và 4) thì phải xoay cây để đưa về trường hợp thuận chiều (1 và 3).

4.3.2 S, SL và SR đều có màu đen:

Thì SL và SR đều là NULL, ta sẽ xử lí trường hợp này như sau:

97. Attachments/Blog/2022-05-04-red-black-tree/deleteBlack1.2.png

97. Attachments/Blog/2022-05-04-red-black-tree/deleteBlack1.png

Trước hết cần lưu ý rằng, đường đi đến nút NULL có qua S là một đường đi chuẩn, tức là nó có số nút đen bằng với các đường đi từ root đến các nút NULL khác.

Vậy thì ta chỉ cần fix làm sao mà từ P đến S không thay đổi số lượng nút đen và từ P đến U tăng thêm 1 nút đen vì từ P đến U đang ít hơn 1 nút đen so với từ P đến S.

Còn nếu không có khả năng làm việc đó, thì ta giảm số nút đen đến S đi 1 rồi tăng số nút đen đến P lên 1 mà không ảnh hưởng đến số nút đen đến U khi đó chỉ tính riêng cây con gốc P thì đã bằng, nên nếu P đang là gốc rồi thì không cần phải chỉnh nữa.

4.3.3 S có màu đỏ:

Trường hợp này thì đơn giản thôi (vì nó là cái cuối rồi)

97. Attachments/Blog/2022-05-04-red-black-tree/deleteRedS.webp

S là màu đỏ thì P, SL, SR đều là màu đen, xử lí như trên là được:

void RBTree::eraseFix(Node *&parent, Node *sibling) {
    if (parent == NULL) return;
    //cout << parent->data << " " << sibling->data << " " << "\n";
    //Node *sibling = (parent->leftChild == NULL) ? parent->rightChild : parent->leftChild;
    Node *leftChild = sibling->leftChild;
    Node *rightChild = sibling->rightChild;

    if (getColor(leftChild) == RED || getColor(rightChild) == RED) {
        if (parent -> leftChild == sibling) {
            if (getColor(leftChild) != RED) {
                setColor(sibling, RED);
                setColor(rightChild, BLACK);
                rotateLeft(sibling);
                sibling = sibling->parent;
                leftChild = sibling->leftChild;
            }
            int oldColor = getColor(parent);
            setColor(parent, BLACK);
            setColor(leftChild, BLACK);
            rotateRight(parent);
            setColor(sibling, oldColor);
        }
        else {
            //cout << "ok\n" ;
            if (getColor(rightChild) != RED) {
                setColor(sibling, RED);
                setColor(leftChild, BLACK);
                rotateRight(sibling);
                sibling = sibling->parent;
                rightChild = sibling->rightChild;
            }
            int oldColor = getColor(parent);
            setColor(parent, BLACK);
            setColor(rightChild, BLACK);
            rotateLeft(parent);
            setColor(sibling, oldColor);
        }
        return;
    }
    if (getColor(sibling) == BLACK) {
        setColor(sibling, RED);
        if (getColor(parent) == RED)     
            setColor(parent, BLACK);
        else
            eraseFix(parent->parent, getSibling(parent));
        return;
    }

    if (getColor(sibling) == RED) {
        Node* other = getSibling(sibling);
        setColor(sibling, BLACK);
        setColor(parent, RED);
        if (sibling == parent->rightChild)
            rotateLeft(parent);
        else
            rotateRight(parent);
        // cout << parent->color << " " << sibling->color << "\n\n";
        // (*this)._display_tree();
        eraseFix(parent, otherChild(parent, other));
        eraseFix(parent, sibling);
        return;
    }
}

4.3.4 Tổng kết:

Với thao tác delete ta sẽ chia thành các trường hợp:

III. Lời kết

IV. Tham khảo

  1. Lập trình không khó
  2. Geek for geeks
  3. Wikipedia