Cây Đỏ Đen (Red-Black Tree) – Phần 2 (Insert)

0
223
This entry is part 15 of 16 in the series Cấu trúc dữ liệu
89 / 100

Ở bài trước, chúng ta đã tìm hiểu sơ qua về cây đỏ đen – Red Black Tree. Còn trong bài viết này, ta sẽ cùng nhau đi tìm hiểu cách để thêm (insert) một node vào cây đỏ đen.

Phần 1: Cây Đỏ Đen (Red-Black Tree) – Phần 1 (Giới thiệu)

1. Ôn lại kiến thức và Quy ước gọi tên

Cây Đỏ Đen (Red-Black Tree) - Phần 2 (Insert) 1

Trước khi bắt đầu thì chúng ta nên ôn lại kiến thức một tý: cây đỏ đen là gì? Nó như thế nào? Có những quy tắc chi? Cây đỏ đen là cây mà mọi node đều có thêm thuộc tính bit – quy định màu sắc (đỏ hoặc đen). Trong đó có 2 trong 5 quy tắc rất quan trọng:

        1. Không có hai node đỏ liền kề (Một node đỏ thì không thể có cha đỏ hoặc con đỏ).
        2. Mọi đường dẫn từ một node đến bất kì node NULL (thuộc con của nó ) thì đều có cùng số lượng node đen.

Về cách gọi tên các Node:

Cây Đỏ Đen (Red-Black Tree) - Phần 2 (Insert) 2

x->parent: đây được gọi là Node cha của x.

x->parent->left: đây là Node anh em của x (có thể right, tùy trường hợp)

x->parent->parent: chính là Node ông của x

x->parent->parent->left: được gọi là Node chú của x (có thể right, tùy trường hợp)

Note: Root (R viết hoa) là từ dùng để chỉ root của cả cây đỏ đen. Còn root thì dùng để chỉ node đang nằm trong các hàm.

2. Cấu trúc dữ liệu và cách để insert

a) Nhắc lại cây AVL

Đối với cây AVL mình chỉ cần tạo một struct Node rồi sau đó sử dụng đệ quy để thêm vào cây. Bởi vì tất cả các node của cây AVL đều có vai trò như nhau, bình đẳng nhau (kể cả root) nên mới sử dụng đệ quy như vậy được.

b) Về Red-Black Tree

Đối với cây đỏ đen, ta không cần biết chiều cao của cây bằng bao nhiêu như cây AVL. Thay vào đó ta cần phải biết node cha (parent) màu gì? Có cùng màu đỏ với con hay không? Vậy nên phải thêm vào một con trỏ nữa, và tất nhiên là không thể thiếu thuộc tính color – chỉ màu sắc của một node với:

            • 1 – True : Chỉ màu đỏ
            • 0 – False: Chỉ màu đen

Tuy nhiên, khác với cây AVL, các node của RBTree không bình đẳng. Có một node đặc biệt, đó chính là Root. Node Root luôn luôn phải mang màu đen – quy tắc 2. Do đó mình sẽ tạo thêm một struct RBTree nhằm kiểm soát được Root.

Các bạn đọc sơ qua code, rồi xem kĩ lại theo thứ tự phía dưới nha:

  1. Node* Root: mình phải luôn luôn kiểm soát được màu sắc Node này.
  2. RedBlackTree(): đây là Constructor – hàm khởi tạo (xem thêm tại Lập trình hướng đối tượng). Hiểu đơn giản là khi mình khởi tạo 1 đối tượng RedBlackTree tree. Thì khi đó mặc định tree->Root = NULL.
  3. Insert(): Hàm này dùng để thêm 1 node vào nhưng… nó chỉ quan tâm đến node Root. Nếu Root == NULL thì gán vào Root với màu đen. Ngược lại nếu Root != NULL thì chỉ cần giao cho một hàm khác giải quyết – insertHelp(). Giả sử hàm này vô tình đổi màu Root thành màu đỏ thì chỉ cần tô lại đen.
  4. insertHelp(): Khi Root đã được xử lí riêng thì tất cả các node còn lại đều bình đẳng. Do đó ta chỉ cần sử dụng đệ quy như cây AVL để thêm node mới vào. Tuy nhiên, vì có thêm thuộc tính parent nên sau thêm ta phải gán giá trị của parent vào.

Lưu ý: Các node mới được thêm vào luôn luôn màu đỏ.

Tại sao ư? Ở bài trước, mình có nói: không thể có 3 node đen liên tiếp. Giả sử bạn thêm một node đen vào thì phải kiểm tra node cha có màu đen hay không? Node ông có màu đen không? Chưa kể, bạn phải kiểm tra các đường đi có số node đen bằng nhau không? Quá phức tạp.

Tuy nhiên nếu mình thêm node đỏ thì sao? Các đường đi vẫn đảm bảo số node đen bằng nhau vì mình chả thêm node đen nào cả. Và mình chỉ cần kiểm tra node cha, nếu màu đen thì ok – ổn, còn nếu màu đỏ thì chỉ cần xử lí xung đột đỏ.

3. Các phép quay cây đỏ đen

Hoàn toàn tương tự như cách quay cây AVL, RBTree cũng có hai cách quay đó là: quay phải, quay trái. Khác một tý là các bạn phải gán lại parent cho những node bị thay đổi. Và ngoài ra, lúc quay không đụng gì đến màu sắc nên bạn không cần phải để ý đâu.

a) Kỹ thuật quay phải – rotateRight

Cây Đỏ Đen (Red-Black Tree) - Phần 2 (Insert) 3

Gọi Node x, y lần lượt là các con trái, phải của root. Bây giờ, ta chỉ cần chú ý đến 3 Node: root, x, x.right.

Con trái của root không còn là x nữa mà là x.right hay  root.left = x.right

Nếu x.right != NULL thì x.right->parent = root

X sẽ lên làm Node cha với con phải là root hay x.right = root

Khi đó cha của root là x ==> root.parent = x

Trả về x

b) Kỹ thuật quay trái – rotateLeft

Cây Đỏ Đen (Red-Black Tree) - Phần 2 (Insert) 4

Hoàn toàn tương tự, gọi x y lần lượt là các con trái phải của root. Và ta chỉ cần quan tâm 3 Node: root, y, y.left

4. Xử lí xung đột đỏ – insertHelp()

Khi ta thêm một node đỏ X vào cây, sẽ có 3 trường hợp xảy ra:

    1. Node cha màu đen. (Hoàn toàn ok – không cần xử lí gì cả)
    2. Node cha màu đỏ, Node chú cũng màu đỏ.
    3. Node cha màu đỏ, Node chú màu đen

Note: Node cha đỏ thì Node ông chắc chắn màu đen

1. Cha đỏ – Chú đỏ

Cây Đỏ Đen (Red-Black Tree) - Phần 2 (Insert) 5

Cách xử rất đơn giản, chỉ cần đổi màu 3 node sau:

    • Node cha: đỏ => đen
    • Node chú: đỏ => đen
    • Node ông: đen => đỏ

Về cơ bản thì cây con trên đã cân bằng và thỏa mãn 5 qui tắc cây đỏ đen. Tuy nhiên sẽ có người hỏi rằng: Node ông màu đỏ, nếu cha của node ông cũng màu đỏ thì sao? Thì mình sẽ xử lí tiếp thôi, ở đây mình sử dụng đệ quy nên nó sẽ dần dần truy hồi đến các Node tổ tiên. Gặp xung đột đỏ ở đâu thì xử lí ở đó.

2. Cha đỏ – Chú đỏ

Sẽ có 4 trường hợp: Trái trái, Trái phải, Phải phải, Phải phải, Phải trái. Cách xử lí thì hoàn toàn tương tự cây AVL chỉ thêm bước tô màu.

a) Trái trái – Left left case

Cây Đỏ Đen (Red-Black Tree) - Phần 2 (Insert) 6

Xảy ra khi:

Node cha: là con trái của ông

Node X   : là con trái của cha

Xử lí:

      1. Quay phải Node ông
      2. Node cha: đỏ -> đen
      3. Node ông: đen -> đỏ

b) Trái phải – Left right case

Cây Đỏ Đen (Red-Black Tree) - Phần 2 (Insert) 7

Xảy ra khi:

Node cha: là con trái của ông

Node X   : là con phải của cha

Xử lí:

      1. Quay trái Node cha (Đưa về Left left case)
      2. Xử lí y như trường hợp Trái trái

c) Phải phải – Right right case

Cây Đỏ Đen (Red-Black Tree) - Phần 2 (Insert) 8

Xảy ra khi:

Node cha: là con phải của ông

Node X   : là con phải của cha

Xử lí:

      1. Quay trái Node ông
      2. Node cha: đỏ -> đen
      3. Node ông: đen -> đỏ

d) Phải trái – Right right case

Cây Đỏ Đen (Red-Black Tree) - Phần 2 (Insert) 9

Xảy ra khi:

Node cha: là con phải của ông

Node X   : là con trái của cha

Xử lí:

      1. Quay phải Node cha (Đưa về Right right case)
      2. Xử lí y như trường hợp Phải phải

5. Code chính

Kết quả:

Cảm ơn các bạn đã đọc bài viết của mình. Nếu thấy hay thì hãy chia sẽ nó cho mọi người cùng đọc nhé!  Ngoài ra, bạn nào muốn tham khảo code các ngôn ngữ khác thì hãy truy cập vào Geeks for geeks – Red Black Tree – Set 2 | Insert.

Nguồn tham khảo: Geeks for Geeks

Bài tiếp theo, cũng là bài cuối của cây đỏ đen: Cây Đỏ Đen – Phần 3 (Delete)

Nothing changes if nothing changes. /* Come from HCMUS */
Subscribe
Notify of
guest
0 Bình luận
Inline Feedbacks
View all comments