Bối cảnh và vấn đề nghiên cứu

Trong lĩnh vực khoa học máy tính, cấu trúc dữ liệu và giải thuật đóng vai trò quyết định đến hiệu năng xử lý và mức độ tối ưu tài nguyên của hệ thống phần mềm. Bài toán tìm kiếm bản ghi theo khóa $X$ trong tập dữ liệu $n$ phần tử ($R_1, R_2, \dots, R_n$) là thao tác căn bản và xuất hiện thường xuyên. Đối với dữ liệu lưu trữ trong bộ nhớ trong, phương pháp tìm kiếm nhị phân trên mảng đạt hiệu quả cao với chi phí thời gian $O(\log_2 n)$. Tuy nhiên, phương pháp này đòi hỏi dãy khóa phải được sắp xếp cố định; khi tập dữ liệu liên tục biến động (thường xuyên bổ sung hoặc loại bỏ bản ghi), chi phí tái sắp xếp mảng làm suy giảm nghiêm trọng hiệu suất tổng thể.

Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree - BST) ra đời nhằm đáp ứng nhu cầu tìm kiếm trên các tập dữ liệu động. Mặc dù vậy, dạng hình học của cây nhị phân tìm kiếm phụ thuộc hoàn toàn vào thứ tự của chuỗi khóa đầu vào. Trong trường hợp xấu nhất—khi dãy dữ liệu đưa vào đã có thứ tự tăng dần hoặc giảm dần—cây sẽ bị suy biến thành một danh sách liên kết tuyến tính, khiến chiều cao của cây đạt mức $h = n$ và chi phí tìm kiếm, chèn, xóa tăng lên mức $O(n)$. Để giải quyết triệt để nhược điểm suy biến này, cấu trúc cây đỏ đen (Red-Black Tree)—một dạng cây nhị phân tìm kiếm tự cân bằng—được áp dụng nhằm duy trì chiều cao cây luôn ở mức logarit, bảo đảm thời gian thực thi trong trường hợp xấu nhất là $O(\log_2 n)$.

Khóa luận xác định các mục tiêu và nhiệm vụ nghiên cứu cụ thể sau:

  1. Nghiên cứu lý thuyết về cây đỏ đen, một dạng cây nhị phân tìm kiếm tự cân bằng để thấy được những điểm mạnh của kiểu cấu trúc dữ liệu này.
  2. Khẳng định, làm rõ những khái niệm, tính chất và việc sử dụng cấu trúc dữ liệu cây đỏ đen vào việc lưu trữ dữ liệu và thực hiện tìm kiếm trong bài toán tìm kiếm.
  3. Thực hiện nghiên cứu và mô phỏng các phép toán chèn, xóa, tìm kiếm trên cây đỏ đen, đánh giá chúng so với cây nhị phân tìm kiếm.

Đối tượng nghiên cứu của đề tài là cấu trúc dữ liệu cây nhị phân, cây nhị phân tìm kiếm, cây đỏ đen và các giải thuật cân bằng (phép quay, lật màu, khôi phục cân bằng). Phạm vi nghiên cứu tập trung vào cấu trúc dữ liệu lưu trữ trên bộ nhớ trong và xây dựng phần mềm mô phỏng thuật toán, được thực hiện tại Khoa Tin học, Trường Đại học Sư phạm – Đại học Đà Nẵng, hoàn thành vào tháng 5 năm 2012.

Cơ sở lý thuyết và phương pháp

Khóa luận xây dựng nội dung dựa trên các nền tảng lý thuyết và công trình khoa học kinh điển:

  • Lý thuyết đồ thị và cấu trúc cây: Ứng dụng định nghĩa cây từ công trình năm 1857 của nhà toán học Arthur Cayley (sử dụng đồ thị liên thông không chu trình để biểu diễn các hợp chất hóa học), phát triển thành các khái niệm bậc của nút, mức, chiều cao, cây $n$-phân và cây nhị phân.
  • Lý thuyết cây đỏ đen: Khởi nguồn từ công trình nghiên cứu "Symmetric Binary B-Trees: Data Structure and maintenance Algorithms" của Rudolf Bayer (1972) công bố trên tạp chí Acta Informatica, và công trình chuẩn hóa thuộc tính cùng tên gọi "Red-Black Tree" của Leo J. Guibas và Robert Sedgewick (1978) trong bài báo "A dichromatic Framework for Balanced Trees" tại Hội thảo IEEE FOCS lần thứ 19.
  • Các cấu trúc liên quan: Mô hình cây tìm kiếm nhị phân thông thường, cây 2-3-4 và các phép biến đổi cây tự cân bằng.

Phương pháp nghiên cứu được tác giả triển khai kết hợp giữa nghiên cứu lý thuyết và phát triển phần mềm:

  • Phương pháp phân tích - tổng hợp tài liệu: Thu thập, phân tích và hệ thống hóa các tài liệu chuyên ngành, giáo trình giải thuật, bài báo khoa học về cấu trúc cây, cây nhị phân tìm kiếm và các quy tắc đỏ - đen.
  • Phương pháp mô hình hóa và thiết kế thuật toán: Chi tiết hóa các giải thuật duyệt cây, tìm kiếm đệ quy/không đệ quy, phép quay trái, quay phải, cơ chế lật màu và thuật toán khôi phục vi phạm RB-INSERT-FIXUP.
  • Phương pháp thực nghiệm phần mềm: Ứng dụng phương pháp lập trình hướng đối tượng (OOP) để hiện thực hóa cấu trúc dữ liệu và xây dựng giao diện mô phỏng trực quan các thao tác biến đổi cấu trúc cây.

Nguồn dữ liệu của đề tài bao gồm các tài liệu học thuật xuất bản quốc tế, giáo trình cấu trúc dữ liệu và các tập dữ liệu số nguyên mẫu dùng trong kiểm thử thuật toán và mô phỏng giao diện.

Thiết kế và triển khai

Cấu trúc lưu trữ của cây đỏ đen được thiết kế bằng cách mở rộng nút của cây nhị phân tìm kiếm, bổ sung liên kết đến nút cha và thuộc tính màu sắc.

Khai báo kiểu dữ liệu nút của cây đỏ đen trong chương trình:

struct Node {
    Node *left;
    Node *right;
    Node *parent; // trỏ đến nút cha
    int color;    // màu nút (BLACK, RED)
    int key;      // dữ liệu
};

struct RBTree {
    Node* root;
};

Hệ thống triển khai hai phép biến đổi cấu trúc cơ bản là quay trái (rotateLeft) và quay phải (rotateRight) nhằm thay đổi quan hệ phân cấp giữa nút cha và nút con mà không làm thay đổi thứ tự khóa tìm kiếm:

  • Phép quay trái tại đỉnh $X$: Đưa nút con phải $Y$ của $X$ lên thay thế vị trí của $X$, $X$ chuyển xuống thành nút con trái của $Y$, và cây con trái của $Y$ được chuyển sang làm cây con phải của $X$.
  • Phép quay phải tại đỉnh $Y$: Đưa nút con trái $X$ của $Y$ lên vị trí của $Y$, $Y$ chuyển xuống thành nút con phải của $X$, và cây con phải của $X$ chuyển sang làm cây con trái của $Y$.

Chương trình ứng dụng ngôn ngữ Java để xây dựng ứng dụng mô phỏng đồ họa. Giao diện chương trình cho phép người dùng nhập khóa, thực hiện các thao tác chèn từng nút, theo dõi trực quan quá trình lật màu (đổi màu đỏ/đen) và các bước xoay cây nhằm khôi phục trạng thái cân bằng.

Nội dung chính theo từng chương

Chương I: Tổng quan về cấu trúc cây

Chương này trình bày có hệ thống các khái niệm cơ bản về cây theo lý thuyết đồ thị: cây là đồ thị liên thông không có chu trình đơn; cấu trúc gồm nút gốc (root), các nhánh và nút lá. Khóa luận định nghĩa các thông số kỹ thuật:

  • Mức của đỉnh: độ dài đường đi từ gốc đến đỉnh đó (gốc ở mức 0).
  • Chiều cao của cây: số mức lớn nhất của các nút có trên cây.
  • Bậc của nút: số lượng cây con của nút đó; bậc của cây là bậc lớn nhất trong tất cả các nút.
  • Phân loại cây: cây $n$-phân, cây $n$-phân đầy đủ, cây cân bằng (các lá có mức $h$ hoặc $h-1$).

Chương I làm rõ các dạng đặc biệt của cây nhị phân (mỗi nút có tối đa hai con) bao gồm: cây suy biến (lệch trái, lệch phải, zic-zắc), cây nhị phân hoàn chỉnh, cây nhị phân đầy đủ cân bằng và cây gần đầy. Các tính chất toán học được chứng minh bằng quy nạp:

  1. Số lượng tối đa các nút ở mức $k$ ($k \ge 1$) trên cây nhị phân là $2^{k-1}$.
  2. Số lượng tối đa các nút trên cây nhị phân có chiều cao $h$ là $2^h - 1$.
  3. Cây suy biến có chiều cao lớn nhất ($h = n$), trong khi cây hoàn chỉnh hoặc gần đầy có chiều cao nhỏ nhất ($h \approx \log_2 n$).

Các ví dụ thực tế về ứng dụng cấu trúc cây được dẫn chứng: sơ đồ tổ chức doanh nghiệp, cấu trúc mục lục sách, biểu diễn biểu thức số học $x + y * (z - t) + u / v$, tối ưu mạng máy tính và thuật toán mã hóa dữ liệu.

Chương II: Cây nhị phân tìm kiếm

Chương II khảo sát chi tiết cây nhị phân tìm kiếm (Binary Search Tree - BST), trong đó khóa tại mỗi nút luôn lớn hơn tất cả các khóa trên cây con bên trái và nhỏ hơn tất cả các khóa trên cây con bên phải.

Nội dung trọng tâm của chương bao gồm:

  • Các giải thuật duyệt cây: Duyệt theo thứ tự trước (NLR: Node - Left - Right), thứ tự giữa (LNR: Left - Node - Right), và thứ tự sau (LRN: Left - Right - Node). Phép duyệt LNR cho dãy khóa theo thứ tự tăng dần; độ phức tạp của phép duyệt toàn bộ cây là $\Omega(n)$ và $O(n)$.
  • Giải thuật tìm kiếm: Triển khai bằng cả phương pháp đệ quy và khử đệ quy (while). Phép tìm kiếm bắt đầu từ gốc, so sánh khóa cần tìm $K$ với khóa tại nút hiện hành để rẽ sang nhánh trái hoặc nhánh phải.
  • Thao tác chèn nút (insertNode): Thực hiện tương tự tìm kiếm cho đến khi gặp nút rỗng ngoài cùng thì tạo nút mới gắn vào, không làm xáo trộn các nút hiện có.
  • Thao tác hủy nút (delNode): Phân loại và xử lý theo 3 trường hợp:
    1. Nút $X$ là nút lá: Xóa nút và gán liên kết từ cha về NULL.
    2. Nút $X$ có một cây con: Nối trực tiếp nút cha của $X$ với nút con duy nhất của $X$.
    3. Nút $X$ có đủ hai cây con: Sử dụng kỹ thuật hủy gián tiếp thông qua hàm searchStandFor. Nút thế mạng $Y$ được chọn là nút cực phải của cây con bên trái (khóa lớn nhất bên trái) hoặc nút cực trái của cây con bên phải (khóa nhỏ nhất bên phải). Dữ liệu của $Y$ được sao chép sang $X$, sau đó thực hiện xóa nút $Y$.
  • Đánh giá độ phức tạp: Chi phí trung bình của các thao tác tìm kiếm, chèn, xóa trên BST là $O(\log_2 n)$. Tuy nhiên, trong trường hợp xấu nhất khi cây suy biến thành danh sách liên kết, chi phí đạt mức $O(n)$.

Chương III: Cây đỏ đen

Chương III tập trung phân tích lý thuyết chuyên sâu về cây đỏ đen. Cây đỏ đen là cây nhị phân tìm kiếm thỏa mãn 5 quy tắc bất biến:

  1. Mọi nút đều có màu đỏ hoặc đen.
  2. Nút gốc luôn có màu đen.
  3. Tất cả các nút lá (nút lá giả nil) đều có màu đen.
  4. Nếu một nút có màu đỏ thì cả hai con của nó phải có màu đen (không có hai nút đỏ kề nhau trên một đường dẫn).
  5. Mọi đường dẫn đơn từ một nút đến các nút lá hậu duệ đều chứa số lượng nút đen bằng nhau.

Số lượng nút đen trên đường dẫn từ gốc đến lá gọi là chiều cao đen ($bh$). Khóa luận nêu và chứng minh bổ đề: Một cây đỏ đen có $n$ nút nội thì chiều cao $h$ thỏa mãn bất đẳng thức: $$h \le 2\log_2(n + 1)$$ Do đường dẫn dài nhất (xen kẽ đỏ - đen) không vượt quá 2 lần đường dẫn ngắn nhất (chỉ gồm nút đen), cây đỏ đen luôn duy trì trạng thái gần cân bằng, bảo đảm mọi phép toán tìm kiếm, chèn, xóa trong trường hợp xấu nhất đều đạt độ phức tạp $O(\log_2 n)$.

Để duy trì 5 quy tắc đỏ - đen khi chèn nút mới $X$ (luôn được tô màu đỏ ban đầu), thuật toán RB-INSERT-FIXUP phân tích các tình huống vi phạm tính chất 4 (xung đột đỏ - đỏ giữa nút cha $P$ và nút con $X$) dựa trên màu của nút chú bác $U$ (anh em của $P$) và vị trí của $X$ đối với nút ông bà $G$:

  • Trường hợp 1 (Nút $P$ đen): Không xuất hiện xung đột đỏ - đỏ, cây giữ nguyên tính chất cân bằng, kết thúc thao tác.
  • Trường hợp 2 (Nút $P$ đỏ và nút chú bác $U$ đỏ): Thực hiện phép lật màu trên đường đi xuống: đổi màu nút $P$ và $U$ thành đen, đổi màu nút $G$ thành đỏ (nếu $G$ không phải gốc). Tiếp tục kiểm tra xung đột đỏ - đỏ tại $G$.
  • Trường hợp 3 (Nút $P$ đỏ, nút chú bác $U$ đen, $X$ là "cháu ngoại" của $G$): $X$ và $P$ nằm cùng một phía (cùng là con trái hoặc cùng là con phải). Đổi màu nút $P$ thành đen, đổi màu nút $G$ thành đỏ, sau đó thực hiện một phép quay đơn tại đỉnh $G$ về phía ngược lại để nâng $P$ lên.
  • Trường hợp 4 (Nút $P$ đỏ, nút chú bác $U$ đen, $X$ là "cháu nội" của $G$): $X$ và $P$ nằm khác phía ($X$ là con phải của $P$ trong khi $P$ là con trái của $G$, hoặc ngược lại). Thực hiện phép quay tại $P$ để đưa $X$ về vị trí "cháu ngoại", sau đó đổi màu $X$ thành đen, $G$ thành đỏ và quay tiếp tại $G$.

Chương IV: Cài đặt chương trình

Chương IV trình bày việc cài đặt thuật toán cây đỏ đen và xây dựng phần mềm mô phỏng bằng ngôn ngữ lập trình Java. Tác giả giới thiệu các đặc tính hướng đối tượng của Java, cách thức tổ chức các lớp biểu diễn nút, cấu trúc cây và các hàm xử lý đồ họa. Phần demo chương trình hiển thị giao diện người dùng, minh họa trực quan các bước chèn khóa, quá trình biến đổi màu sắc của từng nút và các chuyển động quay cây khi xảy ra vi phạm quy tắc đỏ - đen.

Kết quả và đóng góp

Khóa luận đã tổng hợp và chuẩn hóa toàn bộ cơ sở toán học cùng giải thuật của cấu trúc cây đỏ đen, so sánh trực tiếp với cây nhị phân tìm kiếm thông thường.

Tiêu chí so sánh Cây nhị phân tìm kiếm (BST) Cây đỏ đen (Red-Black Tree)
Chiều cao cây ($h$) tốt nhất $\log_2(n + 1)$ $\approx \log_2(n + 1)$
Chiều cao cây ($h$) xấu nhất $n$ (suy biến thành danh sách) $\le 2\log_2(n + 1)$
Tìm kiếm (Trường hợp trung bình) $O(\log_2 n)$ $O(\log_2 n)$
Tìm kiếm (Trường hợp xấu nhất) $O(n)$ $O(\log_2 n)$
Chèn phần tử (Xấu nhất) $O(n)$ $O(\log_2 n)$
Xóa phần tử (Xấu nhất) $O(n)$ $O(\log_2 n)$
Chi phí bộ nhớ cho một nút Con trỏ left, right, dữ liệu Con trỏ left, right, parent, thuộc tính color, dữ liệu
Cơ chế cân bằng Không có cơ chế tự cân bằng Tự cân bằng qua phép quay và lật màu (RB-INSERT-FIXUP)

Các đóng góp chính của đề tài bao gồm:

  • Hệ thống hóa đầy đủ các trường hợp biến đổi khi chèn nút trên cây đỏ đen, làm rõ bản chất hình học của các phép quay trái, quay phải và kỹ thuật lật màu.
  • Hiện thực hóa thành công mã nguồn giải thuật cân bằng và xây dựng phần mềm mô phỏng trên nền tảng Java, giúp trực quan hóa các thao tác xử lý phức tạp của cấu trúc dữ liệu này.

Hạn chế và hướng nghiên cứu tiếp

  • Hạn chế: Khóa luận tập trung chủ yếu vào lý thuyết, cài đặt và mô phỏng chi tiết thao tác chèn (insert) cùng quy trình khôi phục vi phạm đỏ - đen. Giải thuật xóa nút (RB-DELETE-FIXUP) với các trường hợp suy giảm chiều cao đen phức tạp chưa được phân tích sâu và cài đặt chi tiết trong mã nguồn mô phỏng như thao tác chèn. Ngoài ra, việc nghiên cứu mới chỉ giới hạn ở cấu trúc dữ liệu lưu trữ trong bộ nhớ trong.
  • Hướng nghiên cứu tiếp:
    1. Hoàn thiện cài đặt và mô phỏng toàn diện giải thuật xóa nút trên cây đỏ đen kèm đầy đủ các trường hợp hiệu chỉnh màu và quay khôi phục.
    2. Mở rộng nghiên cứu sang các cấu trúc cây tự cân bằng khác phục vụ lưu trữ dữ liệu bộ nhớ ngoài và cơ sở dữ liệu như cây 2-3-4, cây AVL và cây B-Tree.

Giá trị tham khảo

Khóa luận là tài liệu tham khảo chuyên ngành hữu ích cho:

  • Sinh viên các ngành Công nghệ thông tin, Sư phạm Tin học, Kỹ thuật phần mềm đang học tập các học phần Cấu trúc dữ liệu và Giải thuật, Giải thuật nâng cao.
  • Người nghiên cứu cần tài liệu tham khảo chi tiết về cơ chế hoạt động của các cấu trúc cây tự cân bằng, đặc biệt là cách phân loại các trường hợp vi phạm quy tắc đỏ - đen khi chèn nút và kỹ thuật cài đặt phép quay.
  • Người phát triển phần mềm mô phỏng thuật toán phục vụ mục đích giảng dạy và học tập trực quan.

Câu hỏi thường gặp

1. Năm quy tắc bắt buộc của một cây đỏ đen là gì? Cây đỏ đen là cây nhị phân tìm kiếm thỏa mãn: (1) Mọi nút phải là đỏ hoặc đen; (2) Nút gốc luôn có màu đen; (3) Các nút lá (nil) luôn có màu đen; (4) Nếu một nút là đỏ thì cả hai nút con của nó phải có màu đen; (5) Mọi đường dẫn đơn từ một nút đến các lá hậu duệ đều có cùng số lượng nút đen (cùng chiều cao đen).

2. Tại sao chiều cao của cây đỏ đen không bao giờ vượt quá $2\log_2(n + 1)$? Do quy tắc không có hai nút đỏ liền kề nhau, trên mỗi đường dẫn số nút đỏ không thể nhiều hơn số nút đen. Đường dẫn ngắn nhất chỉ gồm toàn nút đen, còn đường dẫn dài nhất xen kẽ giữa nút đỏ và nút đen. Vì mọi đường dẫn đều có cùng số lượng nút đen, đường dẫn dài nhất không vượt quá hai lần đường dẫn ngắn nhất, giúp cây luôn giữ trạng thái gần cân bằng và chiều cao $h \le 2\log_2(n + 1)$.

3. Khi chèn một nút mới vào cây đỏ đen, những quy tắc nào có nguy cơ bị vi phạm? Nút mới chèn luôn được gán màu đỏ. Khi đó, chỉ có hai quy tắc có thể bị vi phạm: Quy tắc 2 (nếu nút chèn vào là nút gốc của cây) và Quy tắc 4 (xung đột đỏ - đỏ nếu nút cha của nút mới chèn cũng có màu đỏ). Quy tắc 5 về chiều cao đen không bị ảnh hưởng trực tiếp tại thời điểm chèn.

4. Phép lật màu (color flip) được thực hiện trong trường hợp nào và có làm thay đổi chiều cao đen không? Phép lật màu được thực hiện khi nút cha $P$ và nút chú bác $U$ đều có màu đỏ. Thao tác này đổi màu $P$ và $U$ từ đỏ sang đen, đồng thời đổi nút ông bà $G$ từ đen sang đỏ (trừ khi $G$ là gốc). Sau phép lật màu, số lượng nút đen trên mỗi nhánh đi qua $G$ không đổi nên chiều cao đen của cây được bảo toàn hoàn toàn.

5. Trong cây nhị phân tìm kiếm thông thường, nút thế mạng khi xóa nút có hai con được xác định ra sao? Có hai cách chọn nút thế mạng $Y$ để thay thế cho nút $X$ có đủ hai con: (1) Chọn nút có khóa nhỏ nhất (nút cực trái) trên cây con bên phải của $X$; (2) Chọn nút có khóa lớn nhất (nút cực phải) trên cây con bên trái của $X$. Sau khi sao chép khóa của $Y$ vào $X$, thao tác xóa sẽ được thực hiện trực tiếp trên nút $Y$ (vốn chỉ có tối đa một con).

Kết luận

Khóa luận "Cấu trúc dữ liệu cây đỏ đen và mô phỏng" của tác giả Phan Thị Như Ngọc đã hoàn thành việc hệ thống hóa cơ sở lý thuyết về cấu trúc cây, phân tích các giải thuật tìm kiếm, chèn, xóa trên cây nhị phân tìm kiếm và chỉ rõ hạn chế suy biến thời gian về $O(n)$ của cấu trúc này. Đề tài làm sáng tỏ cơ chế tự cân bằng của cây đỏ đen thông qua 5 quy tắc bất biến, chứng minh giới hạn chiều cao logarit bảo đảm độ phức tạp $O(\log_2 n)$ trong trường hợp xấu nhất, đồng thời phân loại chi tiết các trường hợp hiệu chỉnh vi phạm bằng phép quay và lật màu. Chương trình mô phỏng được xây dựng bằng ngôn ngữ Java cung cấp công cụ trực quan hóa hiệu quả cho việc học tập và nghiên cứu các giải thuật cân bằng cây.