TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2 KHOA CÔNG NGHỆ
THÔNG TIN
* * * * * * * * *****
TRẦN THỊ SIM
XÂY DƯNG CHƯƠNG TRÌNH MÔ PHỎNG
CÁC THUÃT TOÁN cơ BẢN TRÊN CÂY ĐỎ
ĐEN
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
• • • •
Chuyên ngành: Khoa học máy tính
TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2 • • • •
KHOA CÔNG NGHỆ THÔNG TIN
*************
HÀ NỘI - 2015
TRẦN THỊ SIM
XÂY DựNG CHƯƠNG TRÌNH MÔ PHỎNG
CÁC THUẬT TOÁN cơ BẢN TRÊN CÂY ĐỎ
ĐEN
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
• • • •
Chuyên ngành: Khoa học máy tính
Người hướng dẫn khoa học PGS. TS. BÙI THẾ HỒNG
Lời đầu tiên em xin chân thành cảm ơn sự hướng dẫn tận tình của thầy giáo
PGS. TS Bùi Thế Hồng, đã trực tiếp hướng dẫn và chỉ bảo tận tình cho em hoàn
thành khóa luận này.
Em cũng xin chân thảnh cảm ơn các thầy, cô giáo trong khoa Công nghệ
thông tin, cũng như các thầy, cô giáo trong trường đã giảng dạy và giúp đỡ em
trong các năm học vừa qua. Chính các thày, cô giáo đã xây dựng cho chúng em
HÀ NỘI - 2015
những kiến thức nền tảng và kiến thức chuyên môn để em có thể hoàn thành khóa
luận tốt nghiệp và chuẩn bị cho những công việc của mình sau này.

1.7. Cây nhị phân đầy đủ
1.8. Cây nhị phân gần đầy
1.9. Cây nhị phân tìm kiếm
1.10. Tìm nút trên cây với khóa x=55
1.11. Xóa nút trên cây với khóa X =40
1.12. Xóa một nút trên cây với khóa X = 37
1.13. Xóa một nút với khóa X = 18
1.14. Thêm một nút với khóa X = 10 vào cây
1.15. Cây nhị phân ban đầu
1.16. Thêm nút có khóa X = 7
1.17. Tái cân bằng lại cây khi thêm nút với khóa X = 7
2.1. Các nút được chèn theo thứ tự tăng dần
2.2. Ví dụ về cây đỏ đen
2.3. Lật màu
2.4. Các biến dạng của nút khi được chèn với X là cháu ngoại
2.5. Các biến dạng của nút khi được chèn với X là cháu nội
2.6. Các khả năng khi chèn nút
2.7. Nút p đỏ và X là cháu ngoại
2.8. p đỏ và X là nút cháu nội
2.9. Minh họa trường họp 2
2.10 Minh họa trường hợp 3
2.11. Minh họa trường hợp 4
MỞ ĐÀU
1. Lý do chọn đề tài
Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu ừong
máy tính sao cho nó có thể được sử dụng một cách hiệu quả. Thông thường,
một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu
quả hom. Việc chọn cấu trúc dữ liệu thường bắt đầu từ việc chọn một cấu trúc
dữ liệu trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện
nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ

3. 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, xóa, tìm kiếm trên cấu trúc dữ liệu cây
đỏ đen, đánh giá chúng so với cây nhị phân tìm kiếm.
Mô phỏng các phép toán chèn, xóa, tìm kiếm một node trên cây đỏ đen.
4. Đổi tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu: Cây đỏ đen
Phạm vi nghiên cứu: Các phép chèn, xóa, tìm kiếm các node trên cây đỏ
đen.
5. Ý nghĩa khoa học và thực tiễn
Ỷ nghĩa khoa học: Cây đỏ đen ra đời, phát triển và có cơ sở khoa học
vững chắc đã giúp cho việc nghiên cứu chứng minh được việc sử dụng phương
pháp cây đỏ đen vào việc lưu trữ dữ liệu và thực hiện việc tìm kiếm trong bài
toán tìm kiếm là việc nên làm. Hiện nay, việc làm thế nào để giảm thiểu chi phí
tìm kiếm là một lĩnh vực đang được các chuyên gia nghiên cứu và phát triển.
Ý nghĩa thực tiễn: Chương trình thử nghiệm nếu thành công sẽ biết được
hình dạng của cây phát triển như thế nào và đó là một cây nhị phân tìm kiếm
8
cân bằng từ đó giảm thiểu chi phí tìm kiếm dữ liệu đối với dữ liệu trong một
danh sách tuyến tính .
6. Phương pháp nghiên cứu
+ Phương pháp nghiên cứu lý luận
Nghiên cứu qua việc đọc sách, báo và các tài liệu liên quan nhằm xây dựng
cơ sở lý thuyết của khóa luận và các biện pháp cần thiết để giải quyết các vấn
đề của khóa luận.
+ Phương pháp chuyên gia
Tham khảo ý kiến của các chuyên gia để có thể thiết kế chương trĩnh phù
hợp với yêu cầu thực tiễn. Nội dung xử lý nhanh đáp ứng được yêu cầu ngày

Cây là một tập hợp các nút (các đinh) và các cạnh, thỏa mãn một số yêu
càu nào đó. Mỗi nút của cây đều có một định danh và có thể mang thông tin nào
đó. Các cạnh dùng để liên kết các nút với nhau. Một đường đi trong cây là một
danh sách các đinh phân biệt mà đỉnh trước có liên kết với đinh sau.
Một tính chất quan trọng hình thành nên cây, đó là có đúng một đường đi
nối hai nút bất kì trong cây. Nếu tồn tại hai nút trong cây mà có ít hoặc nhiều
hơn một đường đi thì lúc đó có một đồ thị.
Mỗi cây thường có một nút được gọi là nút gốc. Mỗi nút đều có thể coi là
nút gốc của cây con bao gồm chính nó và các nút bên dưới nó. Trong biểu diễn
hình học của cây, nút gốc thường nằm ở vị trí cao nhất, tiếp theo là các nút kế
tiếp.
1
0
Hình 1.1. Hình ảnh một cây Như vậy có thể thấy rằng
cây bao gồm gốc và các cây con nối với gốc. Qua đó, có thể định nghĩa cây
dưới dạng đệ qui như sau. Cây có thể là:
+ Một nút đứng riêng lẻ (và nó chính là gốc của cây).
+ Hoặc một nút kết họp với một số cây con bên dưới.
Mỗi nút trong một cây (trừ nút gốc) có đúng 1 nút nằm trên nó, gọi là
nút cha (parent). Các nút nằm ngay dưới nút đó được gọi là nút con (subnode).
Các nút nằm cùng cấp được gọi là các nút anh em (sibling). Nút không có nút
con nào được gọi là nút lá (leaf) hoặc nút tận cùng.
Chiều cao của nút là đường đi dài nhất từ nút tới nút lá. Chiều cao của
cây chính là chiều cao của nút gốc. Độ sâu của 1 nút là độ dài đường đi duy
nhất giữa nút gốc và nút đó.
1.2. Cây nhị phâ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 nút con. Đối với mỗi cây
con của mỗi nút thì phân biêt cây con trái và cây con phải.
Hình 1.2. Cây nhị phân Cây nhị phân là loại cây có cấu

hoặc cây nhị phân gàn đây có chiều cao nhỏ nhất, loại cây này cũng là
cây có dạng “cân đối” nhất.
+ Số lượng tối đa các nút ở mức i trên cây nhị phân là 2
i_1
, tối thiểu là 1
(i>l).
+ Số lượng tối đa các nút trên cây một cây nhị phân có chiều cao là 2
h
-l,
tối thiểu là h (h>l).
+ Cây nhị phân hoản chỉnh, không đầy đủ, có n nút thì chiều cao của nó
là: h =[log
2
( n + 1)] + 1
+ Cây nhị phân đầy đủ, có n nút, thì chiều cao của nó là h = log
2
(n + 1)
1.3. Cây nhị phân tìm kiếm
Cây nhị phân tìm kiếm ứng với n khóa là một cây nhị phân mà mỗi nút của
nó đều được gán một giá tñ khóa nào đó trong các giá tñ khóa đã cho và đối với
mọi nút trên cây tính chất sau đây luôn được thỏa mãn:
1
5
+ Mọi khóa thuộc cây con trái nút gốc đều nhỏ hơn khóa ứng với nút
đó.
+ Mọi khóa thuộc cây con phải nút gốc đều lớn hơn khóa ứng với nút
đó.
Ở đây thứ tự chọn quy ước là thứ tự tăng dần đối với số và thứ tự từ điển
đối với chữ.
Hình 1.9. Cây nhị phân tìm kiếm Nhờ ràng buộc về khóa

if( p->data ==x) retum p; elseif(x<p->data)
p = p->left;
else p = p->right;
}
retum NULL;
}
1.4.2. Xóa một nút trên cây tìm kiếm
1
7
Việc hủy một phần tử X ra khỏi cây phải bảo đảm điều kiện ràng buộc
của CNPTK (cây nhị phân tìm kiếm).
Có 3 trường họp khi hủy nút X có thể xảy ra:
+ X - nút lá.
+ X - chỉ có 1 cây con (trái hoặc phải).
+ X - có đủ cả 2 cây con Trường họp thứ nhất: Chỉ đơn giản
hủy X vì nó không móc nối đến phần tử nào khác.
Hình 1.11. Xóa nút trên cây với khóa X =40 Trường họp thứ
hai: Trước khi xóa X thì phải móc nối cha của X với con duy nhất của nó.
Hình 1.12. Xóa một nút trên cây với khóa X = 37 Trường họp cuối
cùng: Không thể hủy trực tiếp do X có đủ hai con mà sẽ hủy gián tiếp. Thay vì hủy
X, mà là tìm một phần tử thế mạng y. Phần tử này có tối đa một con. Thông tin lưu
tại y sẽ chuyển lên lưu tại X. Sau đó, nút bị hủy thật sẽ là y giống như hai trường
hợp đàu.
Vấn đề là phải chọn y sao cho khi lưu y vào vị trí của X, cây vẫn là cây nhị
phân tìm kiếm.
Có 2 phần tử thỏa mãn yêu cầu:
+ Phần tử nhỏ nhất (trái nhất) trên cây con phải.
1
8
+ Phần tử lớn nhất (phải nhất) trên cây con trái.

1
9
+ X trùng với khóa gốc
+ X nhỏ hơn khóa gốc: Tìm kiếm thực hiện tiếp tục bằng cách
xét cây con trái của gốc với cách làm tương tự.
+ X lớn hom khóa ở gốc: Tìm kiếm được thực hiện tiếp tục
bằng cách xét cây con phải của gốc với cách làm tương tự.
2
0
a) Cây ban đâu
b) Sau khi nút với khóa X =10 Hình 1.14. Thêm một nút với
khóa X = 10 vào cây Như với cây ở hình 1.14, nếu X =10
thì sẽ thực hiện :
+ So sánh X với 5: x>5 vậy phải chuyển sang cây con phải.
+ So sánh X với 8: x>8 vậy phải chuyển sang cây con phải.
+ So sánh X với 9: x>9 cho nên thêm một nút với khóa x= 10 vào bên phải.
Thuật toán thêm nút vào cây nhị phân tìm kiếm sẽ như sau: Cay themnut
(Cay &p, int x)
{
Cay t = tao nut (x);
Cay q,f; if (p = NULL)
{
t=p;
}
else
{
t = q; f = NULL; while (q !=NULL)
{
f=q;
if (x<q->data)

thiếu tin tưởng vào phương pháp tìm kiếm này.
Tới đây cũng có thể xuất hiện thêm câu hỏi là: Tại sao không tìm cách
dựng một cây nhị phân tìm kiếm luôn cân bằng để có thể đạt chi phí tối thiểu?
2
2
Hình 1.15. Cây nhị phân ban đầu Tìm kiếm với khóa X
= 7 trên hình 1.15. Như phép tìm kiếm với X như trên sẽ không được thỏa mãn
và phải chèn thêm nút có khóa bằng 7 vào cây trên hình 1.11. Như vậy, cây sẽ
không còn cân đối nữa như (hình 1.16).
Khi thêm nút có khóa X = 7 vào cây thì cây trở nên không cân bằng
nữa, việc này làm cho chi phí tìm kiếm trở lên tốn kém hơn. Điều tất nhiên
đặt ra lúc này là phải “tái cân bằng” lại để được cây cân bằng như hình
1.17
2
3
Hình 1.17. Tái cân bằng lại cây khi thêm nút với khóa X = 7.
2
4
CHƯƠNG 2.
CÂY ĐỎ ĐEN
2.1. Giới thiệu
Cây tìm kiếm nhị phân là một cấu trúc lưu trữ dữ liệu tốt với tốc độ tìm
kiếm nhanh. Tuy nhiên trong một số trường hợp cây tìm kiếm nhị phân có một số
hạn chế. Nó hoạt động tốt nếu dữ liệu được chèn vào cây theo thứ tự ngẫu nhiên.
Nhưng nếu dữ liệu được chèn vào theo thứ tự đã đuợc sắp xếp sẽ không hiệu quả.
Khi các trị số càn chèn đã đuợc sắp xếp thì cây nhị phân trở nên không cân bằng.
Khi cây không cân bằng, nó mất đi khả năng tim kiếm nhanh (hoặc chèn hoặc
xóa) một phần tử đã cho. Chúng ta khảo sát một cách giải quyết vấn đề của cây
không cân bằng: Đó là cây đỏ đen (cây tìm kiếm nhị phân có thêm một vài đặc
điểm).