CÂY NHỊ PHÂN
CÂY ĐỎ ĐEN
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

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 dạng cây nữa đó chính là cây đỏ đen. Đây là một dạng đặc biệt của cây nhị phân tìm kiếm, vì vậy các bạn cần nắm vững kiến thức về cây nhị phân tìm kiếm trước khi vào bài học này nhé.

Chúng ta sẽ cùng nhau tìm hiểu về khái niệm cây đỏ đen là gì? Và cấu trúc dữ liệu của nó, cũng như các thao tác cơ bản trong cây đỏ đen.

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

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 các 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:

cay do den 1 PNG

Ta có một số 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 có thể suy ra được cấu trúc dữ liệu của cây đỏ đen, cụ thể 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 các thuộc tính trên ta có thể viết cấu trúc dữ 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 chúng ta sẽ tìm hiểu về 3 tính chất của cây đỏ đen, cụ thể:

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, vì vậy về cơ bản nó cũng có các thao tác như cây nhị phân tìm kiếm, cụ thể là các 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 các Node trong cây và duyệt cây hoàn toàn tương tự 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 cập nhật lại thuộc tính color để không vi phạm các quy tắc của cây đỏ đen.

5. Kết luận

Như vậy là chúng ta đã tìm hiểu xong về cây đỏ đen là gì? và cấu trúc dữ liệu của nó ra sao. Để có thể tìm hiểu về cây đỏ đen đòi hỏi các bạn cần có kiến thức 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ó các quy tắc lưu trữ như cây nhị phân tìm kiếm. Ở bài tiếp theo mình sẽ hướng dẫn các bạn các thao tác cơ bản trong cây đỏ đen, hãy chú ý theo dõi nhé!!

Cùng chuyên mục:

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

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

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

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

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

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

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

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

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?

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ữ…

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

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

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

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

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

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

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

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

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

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

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

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?

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

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

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…

Top