BÀI TIỂU LUẬN
Đề tài “Cây đỏ đen – lý thuyết và mô phỏng ”
LÊ TRỌNG TÚ
1
MỤC LỤC
PHẦN MỞ ĐẦU
I.LÝ DO CHỌN ĐỀ TÀI.............................................................................................3
II.MỤC ĐÍCH CỦA ĐỀ TÀI......................................................................................4
III.NHIỆM VỤ NGHIÊN CỨU.................................................................................4
IV.PHƯƠNG PHÁP NGHIÊN CỨU.........................................................................4
V.BỐ CỤC BÀI BÁO CÁO.........................................................................................5
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC CÂY...................................................5
1.1 ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM.......................................................................................5
1.2 CÂY NHỊ PHÂN .......................................................................................................................10
CHƯƠNG 2: CÂY NHỊ PHÂN TÌM KIẾM.............................................................13
2.1 ĐỊNH NGHĨA CÂY NHỊ PHÂN TÌM KIẾM...........................................................................13
2.2 GIẢI THUẬT TÌM KIẾM..........................................................................................................14
2.3 PHÂN TÍCH ĐÁNH GIÁ...........................................................................................................16
2.4 THAO TÁC XOÁ TRÊN CÂY NHỊ PHÂN TÌM KIẾM..........................................................18
CHƯƠNG 3: CÂY ĐỎ ĐEN.....................................................................................21
3.1 ĐỊNH NGHĨA.............................................................................................................................21
3.2 CÁC TÍNH CHẤT......................................................................................................................22
3.3 THUẬN LỢI KHI SỬ DỤNG....................................................................................................23
3.4 CÁC PHÉP TOÁN TRÊN CÂY ĐỎ ĐEN................................................................................25
3.4.1PHÉP CHÈN..................................................................................................................25
3.4.2PHÉP XOÁ....................................................................................................................28
3.4.3TÌM KIẾM.....................................................................................................................32
PHẦN KẾT LUẬN
TÀI LIỆU THAM KHẢO
LÊ TRỌNG TÚ
2

thoả (unsuccessfull). Sau một phép tìm kiếm không thoả có khi xuất hiện yêu cầu bổ xung
thêm bản ghi mới có khoá bằng X vào bảng. Giải thuật thể hiện cả yêu cầu này được gọi là
giải thuật “tìm kiếm có bổ xung”.
Có nhiều phương pháp tìm kiếm cơ bản và phổ dụng, đối với dữ liệu ở bộ nhớ trong
nghĩa là tìm kiếm trong, đối với dữ liệu ở bộ nhớ ngoài là tìm kiếm ngoài. Đối với tìm
kiếm trong, tìm kiếm nhị phân là một phương pháp khá thông dụng, chi phí ít, đạt kết quả
tốt. Tuy nhiên khi sử dụng tìmkiếm nhị phân dãy khoá đã phải được sắp xếp rồi, nghĩa là
LÊ TRỌNG TÚ
3
thời gian chi phí cho sắp xếp cũng phải kể đến. Nếu dãy khoá luôn biến động thì lúc đó chi
phí cho sắp xếp lại nổi lên rất rõ và chính điều ấy bộ lộ nhược điểm của phương pháp này.
Để khắc phục nhược điểm vừa nêu trên đối với tìm kiếm nhị phân và đáp ứng yêu cầu
tìm kiếm đối với bảng biến động, một phương pháp mới được hình thành dựa trên cơ sở
bảng được tổ chức dưới dạng cây nhị phân mà ta gọi là cây nhị phân tìm kiếm.
Trong đó cây đỏ đen là một trong những cấu trúc dữ liệu hay, cùng với cây nhị phân
tìm kiếm là những cấu trúc dữ liệu có điểm mạnh trong việc lưu trữ và tìm kiếm dữ liệu.
Song cây đỏ đen có những đặc tính riêng mà nhờ đó nó đã làm nổi bật những điểm mạnh
của mình.
Trên cơ sở đó và với sự định hướng của thầy giáo hướng dẫn Th.S Nguyễn Hữu
Dung em đã chọn đề tài “Cây đỏ đen – lý thuyết và mô phỏng ”
II. MỤC ĐÍCH CỦA ĐỀ TÀI
Đề tài nhằm nghiên cứu lý thuyết về cây đỏ đen, một dạng cây tìm kiếm nhị phân tự
cân bằng để thấy được những điểm mạng của kiểu cấu trúc dữ liệu này. Trên cơ sở thực
hiện mô phỏng các phép toán chèn, xoá, tìm kiếm trên cây đỏ đen, đề tài nhằm khẳng định
những 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 hịên tìm kiếm trong bài toán tìm kiếm là một việc nên làm
III. NHIỆM VỤ NGHIÊN CỨU
 Nghiên cứu và làm rõ những khái niệm, tính chất về cấu trúc dữ liệu cây, cây
nhị phân, cây nhị phân tìm kiếm. Trên cơ sở đó xây dựng cấu trúc cây đỏ đen.
 Nghiên cứu các phép toán chèn, xoá , tìm kiếm trên cấu trúc dữ liệu cây đỏ

1. Một nút là một cây. Nút đó cũng là gốc của cây ấy.
2. Nếu T
1
, T
2
, ..., T
n
là các cây, với n
1
, n
2
, ... n
k
lần lượt là các gốc, n là một nút và n
có quan hệ cha - con với n
1
, n
2
, ... n
k
thì lúc đó một cây mới T sẽ được tạo lập, với n là gốc
LÊ TRỌNG TÚ
5
của nó. n được gọi là cha của n
1
, n
2
, ... n
k
; ngược lại n

1.3 ÁP DỤNG
1.3.1 CÂY BIỂU DIỄN BIỂU THỨC
1.3.2 CÂY BIỂU DIỄN CÁC TẬP
1.3.3 CÂY QUYẾT ĐỊNH
Ta có thể biểu diễn bằng một cây có dạng như sau:
LÊ TRỌNG TÚ
6
Hình 1.1
 Biểu thức số học x + y * (z – t) + u/v, ta có thể biểu diễn dưới dạng cây như hình
1.2
Hình 1.2
Các tập bao nhau như hình 1.3 có thể biểu diễn bởi cây như hình 1.4
LÊ TRỌNG TÚ
1
1.1 1.2
1.3.3
1.3
1.3.21.3.11.2.31.2.1 1.2.2
+
/+
v
u
x
*
y
-
z
t
7
Hình 1.3

 Gốc của cây có số mức (level) là 1. Nếu nút cha có số mức là i thì nút con có só
mức là i + 1 . Ví dụ nút A có số mức là 1.
o Các nút B, C, D cùng có số mức là 2
o Các nút E, F, I, H, G có số mức là 3
o Các nút K, J có số mức là 4
 Chiều cao (heigh) hay chiều xâu (depth) của một cây là số mức lớn nhất của nút
có trên cây đó.
o Cây ở hình 1.2 có chiều cao là 5
o Cây ở hình 1.4 có chiều cao là 4
 Nếu n
1
, n
2
, … , n
k
là dãy các nút mà n
i
là cha của n
i+1
với 1 ≤ i < k, thì dãy đó gọi
là đường đi (path) từ n
1
đến n
k
. Độ dài của đường đi (path length) từ nút n
k
đến n
q
là số nút
phải đi qua để đi từ n

Cây nhị phân là một dạng quan trọng của cấu trúc cây. Cây nhị phân có các đặc điểm
là: Mọi nút trên cây chỉ có tối đa là 2 con. Đối với cây con của một nút người ta cũng phân
biệt cây con trái (left subtree) và cây con phải (right subtree). Như vậy cây nhị phân là cây
có thứ tự.
Ví dụ : Cây ở hình 1.2 là cây nhị phân với toán tử ứng với gốc, toán hạng 1 ứng với
cây con trái, toán hạng 2 ứng với cây con phải. Các cây nhị phân sau đây là khác nhau,
xong chúng đều là cây nhị phân không có thứ tự (hình 1.6). LÊ TRỌNG TÚ
A
B
C D
E
A
B
C D
E
A
B
C D
E
A
B
C D
E
A
B
C D
E

D E F
G
H

I J
A
B C
D E F
G
A
B C
D E F G
H

IJ
11
g)
Hình 1.7
• Các cây a) b) c) d) được gọi là cây nhị phân suy biến (degenerate binary tree) vì
thực chất nó có dạng của một danh sách tuyến tính.
o Cây a) được gọi là cây lệnh trái
o Cây b) được gọi là cây lệnh phải
o Cây c) và cây d) được gọi là cây zic - zắc
• Cây e) được gọi là cây nhị phân hoàn chỉnh (complete binary tree). Ta nhận thấy :
các nút ứng với các mức trừ mức cuối cùng đều đạt tối đa và ở mức cuối cùng các
nút đều dạt về phía trái.
• Cây f) có các nút tối đa ở cả mọi mức nên còn gọi là cây nhị phân đầy đủ (full
binary tree). Cây nhị phân đầy đủ là một trường hợp đặc biệt của cây nhị phân
hoàn chỉnh.
• Cây g) gọi là cây gần đầy, khác với cây e) ở chỗ các nút ở mức cuối không dạt về

Giả sử kết quả đúng với mức i – 1 , nghĩa là ở mức này cây nhị phân có tối đa là 2
i-2
nút. Mỗi nút ở mức i – 1 sẽ có tối đa hai con, do đó 2
i-2
nút ở mức i – 1 sẽ cho:
2
i-2
x 2 = 2
i-1
nút tối đa ở mức i.
Tính chất 2) được chứng minh.
3) Ta biết rằng chiều cao của cây là số mức lớn nhất có trên cây.
Theo 2) ta suy ra số nút tối đa có trên cây nhị phân với chiều cao h là:
2
0
+ 2
1
+ 2
2
+ … + 2
h-1
= 2
h
-1
CHƯƠNG 2: CÂY NHỊ PHÂN TÌM KIẾM
2.1 ĐỊNH NGHĨA CÂY NHỊ PHÂN TÌM KIẾM
Cây nhị phân tìm kiếm ứng với n khoá k
1
, k
2