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

Trong hướng dẫn này mình sẽ trình làng những 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 thao tác với những cấu trúc tài liệu nói chung và cấu trúc cây đỏ đen nói riêng .
Chúng ta sẽ cùng nhau tìm hiểu và khám phá về cách xóa một Node khỏi cây đỏ đen và khắc phục những 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 tất cả chúng ta dựa vào sắc tố của Node chú U để quyết định hành động trường hợp tương thích. Trong thao tác xóa, tất cả chúng ta dựa vào sắc tố của anh chị em Node N để thực quyết định hành động trường hợp thích hợp .

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

Khi thực thi 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 thi thao tác xóa Node khỏi list ta sẽ vi phạm quy tắc số 5 đó là sẽ làm đổi khác số Node đen tính từ Node gốc đến Node ngoài .
Việc xóa là một quy trình khá phức tạp. Khi một Node đen bị xóa, ta cần phải sửa chữa thay thế vào đó một Node đen khác để bảo vệ rằng chiều cao từ Node gốc đến Node ngoài không bị biến hóa .
Chúng ta sẽ thực thi lần lược những bước sau để xóa Node khỏi cây đỏ đen : v là Node bị xóa và u là Node sửa chữa thay thế v

Bước 1

Ta sẽ thực thi viết một hàm xóa một Node tựa như 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à quan tâm 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 thi thay thế sửa chữa Node con là màu đen ( không biến hóa chiều cao của đen của cây ). Lưu ý rằng cả u và v không hề có màu đỏ vì v là cha của u và hai màu đỏ liên tục không được phép trong cây đỏ đen .

Bước 3

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

Trường hợp 1:

Có hai Node u là màu đen, trách nhiệm của ta giờ đây là giảm bớt một Node đen u đi để sửa chữa 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 .

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 thi những phép quay. Ta gọi con màu đỏ của s đó là r thì việc thực thi 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 triển khai đổ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 tái diễn, ta chỉ cần đặt lại cho nó màu đen .

Trường hợp 3:

Nếu Node cần xóa v là Node gốc, ta triển khai đổ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ẽ triển khai thêm vào một số ít Node là số nguyên, sau đó xóa một vài số và hiển thị tác dụng ra màn hình hiển thị. Trong code mình đã có chú thích những bạn quan tâm theo dõi nhé .

Full code:

#include  
#include
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 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<
Kết quả:

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

Source: dolatrees.com
Category: Cây