Cây 2-3-4 – Lý thuyết và mô phỏng Nghiên Cứu Khoa Học
MỤC LỤC----------------------------------------------------------------------------------1
LỜI MỞ ĐẦU
I. LÝ DO CHỌN ĐỀ TÀI---------------------------------------------------2
II. MỤC ĐÍCH NGHIÊN CỨU ĐỀ TÀI-----------------------------------2
III. NHIỆM VỤ NGHIÊN CỨU ĐỀ TÀI-----------------------------------3
IV. ĐỐI TƯỢNG NGHIÊN CỨU--------------------------------------------3
V. PHƯƠNG PHÁP NGHIÊN CỨU----------------------------------------3
PHẦN NỘI DUNG-------------------------------------------------------------------------4
CHƯƠNG 1. LÝ THUYẾT CÂY 2-3-4---------------------------------------------4
I. Giới thiệu về cây 2-3-4.-----------------------------------------------------4
II. Tổ chức cây 2-3-4.----------------------------------------------------------6
III. Tìm kiếm.---------------------------------------------------------------------8
IV. Tách node.-------------------------------------------------------------------8
1. Tách node con.------------------------------------------------------------8
2. Tách node gốc.----------------------------------------------------------11
3. Tách theo hướng đi xuống.--------------------------------------------12
V. Chèn node.------------------------------------------------------------------14
VI. Tính hiệu quả của Cây 2-3-4---------------------------------------------15
VII. Chuyển từ cây 2-3-4 sang cây đỏ đen.----------------------------------16
CHƯƠNG 2. MÔ PHỎNG THUẬT TOÁN TRÊN CÂY 2-3-4--------------21
I. Tổng quan về mô phỏng thuật toán.-------------------------------------21
1. Khái niệm thuật toán và các đặc trưng của thuật toán.----------21
2. Khái niệm mô phỏng thuật toán.-------------------------------------21
II. Các yêu cầu mô phỏng thuật toán.--------------------------------------22
III. Quá trình thiết kế nhiệm vụ mô phỏng thuật toán.--------------------23
IV. Mô phỏng thuật toán trên Cây 2-3-4------------------------------------23
1. Giới thiệu ngôn ngữ mô phỏng.--------------------------------------23
2. Phân tích và thiết kế thuật toán mô phỏng.------------------------24
a. Phân tích.-----------------------------------------------------------24
b. Thiết kế.-------------------------------------------------------------24

Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
2
Cây 2-3-4 – Lý thuyết và mô phỏng Nghiên Cứu Khoa Học
III .Nhiệm vu nghiên cứu đề tài.
Nghiên cứu tổng quan về mô phỏng thuật toán, các yêu cầu, phương pháp
tiếp cận, phương pháp thiết kế một mô đun mô phỏng thuật toán.
Thiết kế minh họa các mô đun minh họa các thuật toán trên Cây2-3-4.
IV. Đối tượng nghiên cứu.
Đề tài nghiên cứu đi sâu vào nghiên cứu và cài đặt một số thuật toán:
- Thuật toán tìm kiếm trên Cây 2-3-4
- Thuật toán chèn một node và chèn một giá trị vào Cây 2-3-4
- Thuật toán tách node trên Cây 2-3-4
- Thuật toán xóa node và xóa một giá trị trên Cây 2-3-4
V. Phưong pháp nghiên cứu.
Phương pháp nghiên cứu chủ yếu tham khảo các tài liệu tham khảo liên quan
đến Cây nhị phân tìm kiếm, Cây 2-3-4 thông qua các sách, tài liệu tham khảo và đặc
biệt là nguồn tài liệu phong phú trên mạng Internet.
PHẦN NỘI DUNG
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
3
Cây 2-3-4 – Lý thuyết và mô phỏng Nghiên Cứu Khoa Học
Chương I. Lý thuyết về Cây 2-3-4
I. Giới thiệu về cây 2-3-4.
Như chúng ta đã biết, các thuật toán về cây nhị phân luôn rất tốt cho nhiều ứng
dụng, tuy nhiên chúng lại có những khuyết điểm trong trường hợp xấu nhất. Chẳng
hạn như trường hợp Quicksort, trường hợp xấu nhất của nó lại là trường hợp dễ
xuất hiện trong thực tế nếu người dùng không chú ý đến nó.
Các tập tin đã được xắp xếp thứ tự, các tập tin với thứ tự ngược, các tập các
khoá lớn, nhỏ xen lẫn nhau hay các tập tin với sự phân đoạn lớn có cấu trúc đơn
giản có thể làm thuật toán tìm trên cây hoạt động rất tồi.

Một node với ba mục dữ liệu thì luôn luôn có 4 con.
Như vậy, một node không phải là lá phải luôn luôn có số node con nhiều hơn 1
so với số mục dữ liệu của nó. Nói cách khác, đối với mọi node với số con là c và số
mục dữ liệu là d, thì : c = d + 1. Sau đây là các ví dụ cụ thể:
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
5
Cây 2-3-4 – Lý thuyết và mô phỏng Nghiên Cứu Khoa Học
Hình 4.2. Các trường hợp của cây 2-3-4
Với mọi node lá thì không có node con nhưng có thể chứa 1, 2 hoặc 3 mục dữ
liệu, không có node rỗng.
Một cây 2-3-4 có thể có đến 4 cây con nên được gọi là cây nhiều nhánh bậc 4.
Trong cây 2-3-4 mỗi node có ít nhất là 2 liên kết ,trừ lnode lá (node không có
liên kết nào).
Hình 4.2 trình bày các trường hợp của cây 2-3-4. Một node với 2 liên kết gọi là
một 2-node, một node với 3 liên kết gọi là một 3-node, và một node với 4 liên kết
gọi là một 4-node, nhưng ở đây không có loại node nào là 1-node.
II. Tổ chức cây 2-3-4.
Các mục dữ liệu trong mỗi node được sắp xếp theo thứ tự tăng dần từ trái sang
phải (sắp xếp từ thấp đến cao).
Một đặc tính quan trọng của bất kỳ cấu trúc cây là mối liên hệ giữa các liên kết
với giá trị khóa của các mục dữ liệu. Trong cây tìm kiếm nhị phân, tất cả node của
cây con bên trái có khoá nhỏ hơn khóa của node đang xét và tất cả node của cây con
bên phải có khoá lớn hơn hoặc bằng khóa của node đang xét. Trong cây 2-3-4 thì
nguyên tắc cũng giống như trên, nhưng có thêm một số điểm sau:
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
6
Cây 2-3-4 – Lý thuyết và mô phỏng Nghiên Cứu Khoa Học
Với node có một mục dữ liệu. Tất cả các node con của cây con có gốc tại
node con thứ 1 thì có các giá trị khoá nhỏ hơn giá trị khoá 1 của node cha. Tất cả
các node con của cây con có gốc tại node con thứ 2 thì có các giá trị khoá lớn hơn

thấy mục dữ liệu, vì thế phải đi đến node con tiếp theo. Tại đây bởi vì 64 lớn hơn 60
nhưng nhỏ hơn 70 nên đi tiếp đến node con 1. Tại thời điểm chúng ta tìm được mục
dữ liệu đã cho với liên kết là 62/64/66.
IV. Tách node
1. Tách node con
Việc thêm vào sẽ trở nên phức tạp hơn nếu gặp phải một node đầy (node có số
mục dữ liệu đầy đủ) trên nhánh dẫn đến điểm thêm vào. Khi điều này xảy ra, node
này cần thiết phải được tách ra. Quá trình tách nhằm giữ cho cây cân bằng. Loại cây
2-3-4 mà chúng ta đề cập ở đây thường được gọi là cây 2-3-4 top-down bởi vì các
node được tách ra theo hướng đi xuống điểm chèn.
Giả sử ta đặt tên các mục dữ liệu trên node bị phân chia là A, B và C. Sau đây
là tiến trình tách (chúng ta giả sử rằng node bị tách không phải là node gốc; chúng
ta sẽ kiểm tra việc tách node gốc sau này):
Một node mới và rỗng được tạo. Nó là anh em với node sẽ được tách và được
đưa vào bên phải của nó.
Mục dữ liệu C được chuyển vào node mới.
Mục dữ liệu B được chuyển vào node cha của node được tách.
Mục dữ liệu A không thay đổi.
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
8
Cây 2-3-4 – Lý thuyết và mô phỏng Nghiên Cứu Khoa Học
Hai node con bên phải nhất bị hủy kết nối từ node được tách và kết nối đến
node mới.
⇒ Quá trình tách node con sẽ xảy ra các trường hợp sau đây:
 Node cha của node cần tách có một khóa.
1. Node cần tách là node con bên phải của node cha nó
Khi đó ta thêm một node mới có một mục dữ liệu, có giá trị khóa là
khóa thứ 3 của node đang tách. Chuyển giá trị khóa thứ 2 của node cần tách nên
node cha. Và gán lại quan hệ cha con của các node như hình dưới đây.


(ii) Sau khi chèn vào
2. Tách node gốc
Khi gặp phải node gốc đầy tại thời điểm bắt đầu tìm kiếm điểm chèn, kết quả
của việc tách thực hiện như sau:
Node mới được tạo ra để trở thành gốc mới và là cha của node được tách.
Node mới thứ hai được tạo ra để trở thành anh em với node được tách.
Mục dữ liệu C được dịch chuyển sang node anh em mới.
Mục dữ liệu B được dịch chuyển sang node gốc mới.
Mục dữ liệu A vẫn không đổi.
Hai node con bên phải nhất của node được phân chia bị hủy kết nối khỏi nó
và kết nối đến node mới bên phải.

Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
11
Cây 2-3-4 – Lý thuyết và mô phỏng Nghiên Cứu Khoa Học
Một ví dụ về việc tách node trình bày trên hình 4.5 cho ta thấy rõ hơn quá trình
tách node gốc.
Hình 4.5 Tách node gốc
i) Trước khi thêm vào
ii) Sau khi thêm vào
Hình 4.5 chỉ ra việc tách node gốc. Tiến trình này tạo ra một node gốc mới ở
mức cao hơn mức của node gốc cũ. Kết quả là chiều cao tổng thể của cây được tăng
lên 1.
Đi theo node được tách này, việc tìm kiếm điểm chèn tiếp tục đi xuống phía
dưới của cây. Trong hình 4.5 mục dữ liệu với khoá 41 được thêm vào lá phù hợp.
3. Tách theo hướng đi xuống
Chú ý rằng, bởi vì tất cả các node đầy được tách trên đường đi xuống nên việc
tách node không gây ảnh hưởng gì khi phải đi ngược lên trên của cây. Node cha của
bất cứ node nào bị tách phải đảm bảo rằng không phải là node đầy, để đảm bảo
node cha này có thể chấp nhận mục dữ liệu B mà không cần thiết nó phải tách ra.

node vì thế các khoá sẽ nằm với trật tự đúng sau khi mục dữ liệu mới được thêm
vào. Trong ví dụ này số 23 phải được đẩy sang phải để nhường chỗ cho 18.
Hình 4.3 Chèn vào không làm tách cây
(i) trước khi chèn vào
(ii) sau khi chèn vào
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
14