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

Trong hướng dẫn này mình sẽ trình làng những bạn một cấu trúc tài liệu dạng cây nữa đó chính là cây đỏ đen. Đây là một dạng đặc biệt quan trọng của cây nhị phân tìm kiếm, vì thế những bạn cần nắm vững kiến thức và kỹ năng về cây nhị phân tìm kiếm trước khi vào bài học kinh nghiệm này nhé .
Chúng ta sẽ cùng nhau tìm hiểu và khám phá về khái niệm cây đỏ đen là gì ? Và cấu trúc tài liệu của nó, cũng như những thao tác cơ bản trong cây đỏ đen .

1. Cây đỏ đen (Red-Black Tree) là gì?

Cây đỏ đen ( Red-Black Tree ) là một cây nhị phân tìm kiếm ( BST ) tuân thủ theo những quy tắc sau :

1. Mọi Node trong cây phải là đỏ hoặc đen.
2. Node gốc là Node đen.
3. Các Node ngoài phải (NULL Node) luôn luôn đen.
4. Nếu một Node là đỏ thì những Node con của nó phải là đen (quy tắc xung đột).
5. Mọi đường dẫn từ Node gốc đến Node ngoài phải có cùng số lượng Node đen.

Một cây nhị phân tìm kiếm tuân thủ theo các quy tắc trên được gọi là cây đỏ đen, ví dụ như cây sau đây:

Ta có 1 số ít khái niệm như sau :

• Chiều cao đen (black height – hb(x)): Là số Node đen trên đường đi từ x đến Node ngoài (không bao gồm x).
• Hiện tượng xung đột đỏ – đỏ: Đây là trường hợp vi phạm quy tắc số 4, khi Node cha và Node con trực tiếp cùng một màu đỏ.

2. Cấu trúc dữ liệu của cây đỏ đen

Từ định nghĩa ta hoàn toàn có thể suy ra được cấu trúc tài liệu của cây đỏ đen, đơn cử như sau :

• Thông tin lưu trữ tại Node (key).
• Địa chỉ Node gốc của cây con bên trái (* pLeft).
• Địa chỉ Node gốc của cây con bên phải (* pRight).
• Địa chỉ của Node cha (* pParent).
• Thuộc tính màu của Node (color).

Dựa vào những thuộc tính trên ta hoàn toàn có thể viết cấu trúc tài liệu trong C + + như sau :

/* khai báo thuộc tính màu cho Node */
enum Color {RED, BLACK}; 
/* Khai báo cấu trúc Node */
struct Node 
{   
    int data; 
    bool color; 
    Node *left, *right, *parent; 
  
    // Constructor 
    Node(int data) 
    { 
       this->data = data; 
       left = right = parent = NULL; 
       this->color = RED; 
    } 
}; 

3. Các tính chất của cây đỏ đen

Trong phần này tất cả chúng ta sẽ khám phá về 3 đặc thù của cây đỏ đen, đơn cử :

Tính chất 1

h <= 2 * hb

Trong đó:

• h là chiều cao của cây.
• hb là chiều cao đen.

Tính chât 2

Giả sử cây đỏ đen có N Node thì khi đó :

h <= 2 * log(N + 1)

Tính chất 3

Thời gian tìm kiếm O một Node:

O(log N)

4. Các thao tác cơ bản trong cây đỏ đen

Vì cây đỏ đen là một cây nhị phân tìm kiếm, thế cho nên về cơ bản nó cũng có những thao tác như cây nhị phân tìm kiếm, đơn cử là những thao tác sau :

• Tìm kiếm và duyệt cây (giống BST).
• Thêm Node mới (insert Node).
• Xóa Node (delete Node).

Việc tìm kiếm những Node trong cây và duyệt cây trọn vẹn tương tự như cây nhị phân tìm kiếm. Còn thao tác thêm Node và xóa Node thì khác so với cây nhị phân tìm kiếm, vì sau mỗi lần thêm Node hoặc xóa Node ta phải update lại thuộc tính color để không vi phạm những quy tắc của cây đỏ đen .

5. Kết luận

Như vậy là tất cả chúng ta đã khám phá xong về cây đỏ đen là gì ? và cấu trúc tài liệu của nó thế nào. Để hoàn toàn có thể tìm hiểu và khám phá về cây đỏ đen yên cầu những bạn cần có kiến thức và kỹ năng cơ bản về C / C + + và cây nhị phân tìm kiếm. Vì cây đỏ đen cũng chính là cây nhị phân tìm kiếm, vậy nên nó cũng có những quy tắc tàng trữ như cây nhị phân tìm kiếm. Ở bài tiếp theo mình sẽ hướng dẫn những bạn những thao tác cơ bản trong cây đỏ đen, hãy chú ý quan tâm theo dõi nhé ! !

Source: dolatrees.com
Category: Cây