Xóa Node khỏi cây đỏ đen

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xóa một Node khỏi cây đỏ đen. Đây là một thao tác thường gặp khi làm việc với các cấu trúc dữ liệu nói chung và cấu trúc cây đỏ đen nói riêng.

test php

Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ đen và khắc phục các trường hợp vi phạm quy tắc cây đỏ đen khi xóa Node.

1. Xóa Node khỏi cây đỏ đen

Trong thao tác chèn chúng ta dựa vào màu sắc của Node chú U để quyết định trường hợp phù hợp. Trong thao tác xóa, chúng ta dựa vào màu sắc của anh chị em Node N để thực quyết định trường hợp thích hợp.

Khi thực hiện thêm một Node mới vào ta sẽ vi phạm quy tắc số 4 đó là xảy ra xung đột đỏ - đỏ. Còn khi thực hiện thao tác xóa Node khỏi danh sách ta sẽ vi phạm quy tắc số 5 đó là sẽ làm thay đổi số Node đen tính từ Node gốc đến Node ngoài.

Bài viết này được đăng tại [free tuts .net]

Việc xóa là một quá trình khá phức tạp. Khi một Node đen bị xóa, ta cần phải thay thế vào đó một Node đen khác để đảm bảo rằng chiều cao từ Node gốc đến Node ngoài không bị thay đổi.

Chúng ta sẽ thực hiện lần lược các bước sau để xóa Node khỏi cây đỏ đen: v là Node bị xóa và u là Node thay thế v

Bước 1

Ta sẽ thực hiện viết một hàm xóa một Node tương tự như xóa nốt ở cây nhị phân tìm kiếm, sẽ có 3 trường hợp đó chính là Node lá, Node có một con và Node có hai con. ta sẽ xét từng trường hợp và xóa nó. Và lưu ý rằng Node lá sẽ có hai Node ngoài là Node đen.

Bước 2

Ta xét trường hợp nếu u hoặc v là màu đỏ ta thực hiện thay thế Node con là màu đen (không thay đổi chiều cao của đen của cây). Lưu ý rằng cả u và v không thể có màu đỏ vì v là cha của u và hai màu đỏ liên tiếp không được phép trong cây đỏ đen.

xoa node 1 png

Bước 3

Trong trường hợp u va v đều là Node đen, ta sẽ xét tiếp các trường hợp sau:

Trường hợp 1:

Có hai Node u là màu đen, nhiệm vụ của ta bây giờ là giảm bớt một Node đen u đi để thay thế vào Node v cần xóa ở trên nó. Nếu v là Node lá thì hai Node u cũng là Node đen và có giá trị NULL.

xoa node 2 png

Trường hợp 2:

Nếu Node cần xóa có Node u là Node đen kép và nó không phải là Node gốc. khi này ta sẽ gọi s là Node anh chị em của v. Ta sẽ có 2 trường hợp con khác:

Thứ nhất: Nếu s là màu đen và một trong số con của s có màu đỏ ta sẽ thực hiện các phép quay. Ta gọi con màu đỏ của s đó là r thì việc thực hiện phép quay tùy thuộc vào vị trí của s và r.

Trường hợp Left Left : s là con trái của cha và r là con trái của s.
Trường hợp Left Right: s là con trái của cha và r là con phải.
Trường hợp Right Right: s là con bên phải của cha và r là con bên phải của s.
Trường hợp Right Left: s là con bên phải của cha và r là con bên trái của s.

Thú hai: Nếu s là màu đen và cả hai con của nó đều màu đen, ta thực hiện đổi màu và lặp lại cho cha của nó nếu cha của nó cũng màu đen. Trong trường hợp cha của nó màu đỏ thì ta không cần lặp lại, ta chỉ cần đặt lại cho nó màu đen.

xoa node 3 png

Trường hợp 3:

Nếu Node cần xóa v là Node gốc, ta thực hiện đổi màu cho u thành đen và khi đó độ dài đen của cây chỉ giảm đi một.

2. Ví dụ xóa Node khỏi cây đỏ đen

Trong ví dụ này mình sẽ thực hiện thêm vào một số Node là số nguyên, sau đó xóa một vài số và hiển thị kết quả ra màn hình. Trong code mình đã có chú thích các bạn chú ý theo dõi nhé.

Full code:

#include <iostream> 
#include<queue>
using namespace std; 
//khai báo thuộc tính color
enum COLOR { RED, BLACK }; 
//tạo cấy trúc node
class Node { 
public: 
  int val; 
  COLOR color; 
  Node *left, *right, *parent; 
  
  Node(int val) : val(val) { 
    parent = left = right = NULL; 
    // Nút được tạo trong quá trình chèn
    // Nút có màu đỏ khi chèn
    color = RED; 
  } 
  
  // trả về con trỏ tới node chú
  Node *uncle() { 
    // Nếu không có node cha hoặc node ông, thì không có node chú
    if (parent == NULL or parent->parent == NULL) 
      return NULL; 
  
    if (parent->isOnLeft()) 
      // node chú bên phải
      return parent->parent->right; 
    else
      //node chú bên trái
      return parent->parent->left; 
  } 
  
  // kiểm tra xem node có phải là node con của cha không 
  bool isOnLeft() { return this == parent->left; } 
  
  // trả về con trỏ cho node anh chị em
  Node *sibling() { 
    // Node anh rỗng nếu không tồn tại node cha 
    if (parent == NULL) 
      return NULL; 
  
    if (isOnLeft()) 
      return parent->right; 
  
    return parent->left; 
  } 
  
  // di chuyển nút xuống và di chuyển nút đã cho vào vị trí của nó
  void moveDown(Node *nParent) { 
    if (parent != NULL) { 
      if (isOnLeft()) { 
        parent->left = nParent; 
      } else { 
        parent->right = nParent; 
      } 
    } 
    nParent->parent = parent; 
    parent = nParent; 
  } 
  
  bool hasRedChild() { 
    return (left != NULL and left->color == RED) or 
           (right != NULL and right->color == RED); 
  } 
}; 
  
class RBTree { 
  Node *root; 
  
  // xoay trái node đã cho 
  void leftRotate(Node *x) { 
    // node cha mới sẽ là con bên phải của nút 
    Node *nParent = x->right; 
  
    // cập nhật gốc nếu nút hiện tại là gốc 
    if (x == root) 
      root = nParent; 
  
    x->moveDown(nParent); 
  
    // kết nối x với phần tử bên trái của cha mẹ mới 
    x->right = nParent->left; 
    // kết nối phần tử bên trái của cha mẹ mới với nút 
    // nếu nó không phải là null 
    if (nParent->left != NULL) 
      nParent->left->parent = x; 
  
    // kết nối cha mẹ mới với x 
    nParent->left = x; 
  } 
  
  void rightRotate(Node *x) { 
    // cha mẹ mới sẽ là con bên trái của nút
    Node *nParent = x->left; 
  
    // cập nhật gốc nếu nút hiện tại là gốc
    if (x == root) 
      root = nParent; 
  
    x->moveDown(nParent); 
  
    // kết nối x với phần tử bên phải của cha mẹ mới 
    x->left = nParent->right; 
    //kết nối phần tử bên phải của cha mẹ mới với nút
    // nếu nó không phải là null
    if (nParent->right != NULL) 
      nParent->right->parent = x; 
  
    // kết nối cha mẹ mới với x
    nParent->right = x; 
  } 
  
  void swapColors(Node *x1, Node *x2) { 
    COLOR temp; 
    temp = x1->color; 
    x1->color = x2->color; 
    x2->color = temp; 
  } 
  
  void swapValues(Node *u, Node *v) { 
    int temp; 
    temp = u->val; 
    u->val = v->val; 
    v->val = temp; 
  } 
  
  // sửa màu đỏ đỏ tại nút nhất định
  void fixRedRed(Node *x) { 
    // nếu x là màu gốc, nó là màu đen và trả về 
    if (x == root) { 
      x->color = BLACK; 
      return; 
    } 
  
    // khởi tạo cha mẹ, ông bà, chú
    Node *parent = x->parent, *grandparent = parent->parent, 
         *uncle = x->uncle(); 
  
    if (parent->color != BLACK) { 
      if (uncle != NULL && uncle->color == RED) { 
        // chú màu đỏ, thực hiện tô màu và đệ quy
        parent->color = BLACK; 
        uncle->color = BLACK; 
        grandparent->color = RED; 
        fixRedRed(grandparent); 
      } else { 
        // Các hoạt động khác LR, LL, RL, RR
        if (parent->isOnLeft()) { 
          if (x->isOnLeft()) { 
            // cho left right 
            swapColors(parent, grandparent); 
          } else { 
            leftRotate(parent); 
            swapColors(x, grandparent); 
          } 
          // cho left left và left right 
          rightRotate(grandparent); 
        } else { 
          if (x->isOnLeft()) { 
            // cho right left 
            rightRotate(parent); 
            swapColors(x, grandparent); 
          } else { 
            swapColors(parent, grandparent); 
          } 
  
          // cho right right và right left 
          leftRotate(grandparent); 
        } 
      } 
    } 
  } 
  
  // tìm nút không có nút con bên trái 
  // trong cây con của nút đã cho 
  Node *successor(Node *x) { 
    Node *temp = x; 
  
    while (temp->left != NULL) 
      temp = temp->left; 
  
    return temp; 
  } 
  
  // tìm nút thay thế nút đã xóa trong BST 
  Node *BSTreplace(Node *x) { 
    // khi nút có 2 con
    if (x->left != NULL and x->right != NULL) 
      return successor(x->right); 
  
    // khi node lá 
    if (x->left == NULL and x->right == NULL) 
      return NULL; 
  
    // khi node có một con
    if (x->left != NULL) 
      return x->left; 
    else
      return x->right; 
  } 
  
  // xóa nút đã cho
  void deleteNode(Node *v) { 
    Node *u = BSTreplace(v); 
  
    // Đúng khi u và v đều đen 
    bool uvBlack = ((u == NULL or u->color == BLACK) and (v->color == BLACK)); 
    Node *parent = v->parent; 
  
    if (u == NULL) { 
      // u là NULL do đó v là lá 
      if (v == root) { 
        // v là root, làm cho root là null 
        root = NULL; 
      } else { 
        if (uvBlack) { 
          // u và v đều đen
          // v là lá, sửa màu đen kép tại v 
          fixDoubleBlack(v); 
        } else { 
          // u hoặc v là đỏ
          if (v->sibling() != NULL) 
            // node anh chị em không rỗng, làm cho nó màu đỏ" 
            v->sibling()->color = RED; 
        } 
  
        // xóa v khỏi cây 
        if (v->isOnLeft()) { 
          parent->left = NULL; 
        } else { 
          parent->right = NULL; 
        } 
      } 
      delete v; 
      return; 
    } 
  
    if (v->left == NULL or v->right == NULL) { 
      // v có 1 node con
      if (v == root) { 
        // v là gốc, gán giá trị của u cho v và xóa u 
        v->val = u->val; 
        v->left = v->right = NULL; 
        delete u; 
      } else { 
        // Tách v khỏi cây và di chuyển u lên
        if (v->isOnLeft()) { 
          parent->left = u; 
        } else { 
          parent->right = u; 
        } 
        delete v; 
        u->parent = parent; 
        if (uvBlack) { 
          // u và v đều đen, sửa hai màu đen ở u 
          fixDoubleBlack(u); 
        } else { 
          // u hoặc v đỏ, màu u đen 
          u->color = BLACK; 
        } 
      } 
      return; 
    } 
  
    // v có 2 con, hoán đổi giá trị với kế nhiệm và đệ quy 
    swapValues(u, v); 
    deleteNode(u); 
  } 
  
  void fixDoubleBlack(Node *x) { 
    if (x == root) 
      // x là node gốc thì return 
      return; 
  
    Node *sibling = x->sibling(), *parent = x->parent; 
    if (sibling == NULL) { 
      // Không có sibiling, màu đen kép được đẩy lên 
      fixDoubleBlack(parent); 
    } else { 
      if (sibling->color == RED) { 
        // Anh chị em màu đỏ 
        parent->color = RED; 
        sibling->color = BLACK; 
        if (sibling->isOnLeft()) { 
          // trường hợp left 
          rightRotate(parent); 
        } else { 
          // trường hợp right 
          leftRotate(parent); 
        } 
        fixDoubleBlack(x); 
      } else { 
        // Anh chị em đen 
        if (sibling->hasRedChild()) { 
          // ít nhất 1 trẻ em màu đỏ 
          if (sibling->left != NULL and sibling->left->color == RED) { 
            if (sibling->isOnLeft()) { 
              // left left 
              sibling->left->color = sibling->color; 
              sibling->color = parent->color; 
              rightRotate(parent); 
            } else { 
              // right left 
              sibling->left->color = parent->color; 
              rightRotate(sibling); 
              leftRotate(parent); 
            } 
          } else { 
            if (sibling->isOnLeft()) { 
              // left right 
              sibling->right->color = parent->color; 
              leftRotate(sibling); 
              rightRotate(parent); 
            } else { 
              // right right 
              sibling->right->color = sibling->color; 
              sibling->color = parent->color; 
              leftRotate(parent); 
            } 
          } 
          parent->color = BLACK; 
        } else { 
          // hai con đen 
          sibling->color = RED; 
          if (parent->color == BLACK) 
            fixDoubleBlack(parent); 
          else
            parent->color = BLACK; 
        } 
      } 
    } 
  } 
  
  // in thứ tự cho node 
  void levelOrder(Node *x) { 
    if (x == NULL) 
      return; 
    queue<Node *> q; 
    Node *curr; 
    q.push(x); 
  
    while (!q.empty()) { 
      curr = q.front(); 
      q.pop(); 
      cout << curr->val << " "; 
      if (curr->left != NULL) 
        q.push(curr->left); 
      if (curr->right != NULL) 
        q.push(curr->right); 
    } 
  } 
  
  // in đệ quy order
  void inorder(Node *x) { 
    if (x == NULL) 
      return; 
    inorder(x->left); 
    cout << x->val << " "; 
    inorder(x->right); 
  } 
  
public: 
  RBTree() { root = NULL; } 
  
  Node *getRoot() { return root; } 
  Node *search(int n) { 
    Node *temp = root; 
    while (temp != NULL) { 
      if (n < temp->val) { 
        if (temp->left == NULL) 
          break; 
        else
          temp = temp->left; 
      } else if (n == temp->val) { 
        break; 
      } else { 
        if (temp->right == NULL) 
          break; 
        else
          temp = temp->right; 
      } 
    } 
  
    return temp; 
  } 
  
  // chen giá trị đã cho vào cây
  void insert(int n) { 
    Node *newNode = new Node(n); 
    if (root == NULL) { 
      newNode->color = BLACK; 
      root = newNode; 
    } else { 
      Node *temp = search(n); 
  
      if (temp->val == n) { 
        return; 
      } 
      newNode->parent = temp; 
  
      if (n < temp->val) 
        temp->left = newNode; 
      else
        temp->right = newNode; 
  
      fixRedRed(newNode); 
    } 
  } 
  
  // chức năng tiện ích xóa nút có giá trị nhất định
  void deleteByVal(int n) { 
    if (root == NULL) 
      // Tree is empty 
      return; 
  
    Node *v = search(n), *u; 
  
    if (v->val != n) { 
      cout << "Không tìm thấy nút nào để xóa với giá trị:" << n << endl; 
      return; 
    } 
  
    deleteNode(v); 
  } 
  
  // in theo thứ tự 
  void printInOrder() { 
    cout << "In theo thứ tự: " << endl; 
    if (root == NULL) 
      cout << "cây rỗng" << endl; 
    else
      inorder(root); 
    cout << endl; 
  } 
  
  // in theo thứ tự cấp 
  void printLevelOrder() { 
    cout << "In theo thứ tự cấp: " << endl; 
    if (root == NULL) 
      cout << "cây rỗng" << endl; 
    else
      levelOrder(root); 
    cout << endl; 
  } 
}; 
  
int main() { 
  RBTree tree; 
  //insert dữ liệu
  tree.insert(7); 
  tree.insert(3); 
  tree.insert(18); 
  tree.insert(10); 
  tree.insert(22); 
  tree.insert(8); 
  tree.insert(11); 
  tree.insert(26); 
  tree.insert(2); 
  tree.insert(6); 
  tree.insert(13); 
  //gọi hàm in
  tree.printInOrder(); 
  tree.printLevelOrder(); 
  
  cout<<endl<<"xóa các số: 18, 11, 3, 10, 22"<<endl; 
  //thực hiện xóa node
  tree.deleteByVal(18); 
  tree.deleteByVal(11); 
  tree.deleteByVal(3); 
  tree.deleteByVal(10); 
  tree.deleteByVal(22); 
  //gọi hàm in
  tree.printInOrder(); 
  tree.printLevelOrder(); 

  cout<<"\n-----------------------------\n"; 
  cout<<"Chương trình này được đăng tại Freetuts.net";
}

Kết quả:

cay do den 3 PNG

3. Kết luận

Như vậy là chúng ta đã tìm hiểu xong cách xóa một Node khỏi cây đỏ đen, cũng như tìm hiểu cách khắc phục các trường hợp vi phạm quy tắc cây đỏ đen. Cũng như thực hiện một ví dụ xóa các số nguyên trong cây đỏ đen số nguyên. Chúc các bạn thực hiện thành công !!!

Bài trước Bài tiếp

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Tìm kiếm phần tử k trong danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu cách tìm kiếm một phần tử k trong…