
Nội dung:
CÂY ĐỎ ĐEN (Red-Black Trees)
CÁC THÀNH VIÊN NHÓM 3:
•
Đinh Như Du (Trưởng nhóm)
•
Trương Thị Mỹ Lê
•
Nguyễn Thị Liên
•
Lê Văn Trường
TIỂU LUẬN MÔN HỌC
THIẾT KẾ & PHÂN TÍCH THUẬT TOÁN
Giảng viên hướng dẫn: TS. Hoàng Quang
NỘI DUNG BÁO CÁO:
Đặt vấn đề:
Các thao tác trên cây nhị phân tìm kiếm có độ phức
tạp là O(h). Trong trong hợp xấu nhất, khi cây không
cân bằng (lệch trái hoặc lệch phải) thì độ phức tạp là
O(n).

Ví dụ: Các nút được chèn theo thứ tự tăng dần.

⇒ Một số biện pháp giữ cây cân bằng như: AVL Trees,
B – Trees, Red - Black Trees.
13.1. Các tính chất của cây đỏ đen
1.Mọi nút là đỏ hoặc đen.
2. Nút gốc là đen.
3. Mọi nút lá (NIL) là đen.
4. Nếu một nút là đỏ, thì cả hai con của nó là đen.

b. Chiều cao đen 
 !"#!$%!#&'!#(!"#)!!"*
+!,-
Sử dụng cờ hiệu nil[T] để biểu thị cho nút lá NIL
và nút cha của gốc.
3
26
3 2
17 41
2 2 2
14 21 30
1
47
1 1
2
10 16 19
1
23 28
1 1
38
1
1
1
7
1
12
1
15 20 35 39
1
1

d. Một số thao tác cơ bản trên cây đỏ đen:
i) Thao tác tìm kiếm nút có giá trị khóa k:
Function SEARCH (
T:
TRBNodeP
, k:bye):
TRBNodeP;
Begin
if (
T=
nil[T]
) or (k = T^.key)
then
SEARCH:=
T
else
if
k < T^.key then

SEARCH:= SEARCH(T^.
left, k)

else SEARCH:= SEARCH(T^.
right, k)
End;
Giải
Giải
thuật:
thuật:
Ví dụ, tìm khóa k=13 trong cây, có đường tìm kiếm:

Nút kế trước của 13 là 9
Nút kế trước của 2 là nil[T]
!!
"#
$%
&'()*+
!!,&'
!
$%
#,&'-
#()*+,#&'
$%
,##,#&'-

 !!,#


iv) Nút kế sau (SUCCESSOR) của x:
SUCCESSORx)
right[x] ≠ nil[T]
right[x])
y ← p[x]
:y ≠ nil[T]) and (x = right[y]) 
5 x ← y
y ← p[y]
.y


 
 

Các phép quay (ROTATIONS):
Right_Rotato(T, Y)
O(1) time.
Y X
Left_Rotato(T, X)
X
Y
γ α
α β
β γ
Tính chất quan trọng:
phép quay cho phép duy trì các tính chất
của cây nhị phân tìm kiếm.
 
13.2.1. Phép quay trái (Left_rotate)
O(1) time.
Y X
Left_Rotato(T, X)
X
Y
γ α
α β
β γ
Phép quay trái trên một nút x, y<>nil thực hiện việc:

x thành con trái của y.

con trái của y thành con phải của x.

y trở thành nút gốc của cây con mới.

9
18
19
14

#Giải
Giải
thuật:
thuật:
=1>?,,(T, X) Thủ tục Left_Rotato(x)
Thủ tục Left_Rotato(x)
11
9
18
1914

#
13.2.2. Phép quay phải (Right_rotate)
;$,6<$?>?,@9JA23!K
B!

!,!DECA0

A$F!!" CGA,!H0

#

00
9
18
19
14
#
Giải
Giải
thuật:
thuật:Thủ tục Right_Rotato(T,
Thủ tục Right_Rotato(T,
x)
x)
1-2
1-2
Tính chất:
h<= 2 * bh(T), T: nút gốc
Theo tính chất 4 của các cây đỏ đen ít nhất phân nửa các
nút trên đường đi đơn giản bất kỳ từ gốc đến một lá, không
kể gốc phải là đen. Do vậy, chiều cao đen của gốc phải ít
nhất là h/2;
•

Ta cần chứng minh chiều cao của cây là 2
bh(x)
-1
Do đó, Cây con có gốc tại x chứa ít nhất:
(2
bh(x)-1
- 1) +( 2
bh(x)-1
- 1 ) +1 = 2
bh(x)
- 1 nút trong. (đpcm)