Đề tài cuối kì
Môn: Cấu trúc dữ liệu 2

Lớp 0811cl2
Nhóm thực hiện:
- Vũ Chí Phương
- Nguyễn Nhân Nghĩa


Phần I - Cây đỏ đen (Red Black Tree)
 Cây đỏ đen là một dạn cây tìm kiếm nhị phân tự cân

bằng.
 Cấu trúc ban đầu của nó được đưa ra vào năm 1972 bởi

Rudolf Bayer với tên là “B-cây cân bằng” còn tên hiện nay
được đưa ra từ 1978 bởi Leo J. Guibas và Robert
Sedgewick.
 Nó là một cấu trúc phức tạp nhưng cho kết quả tốt về thời

gian thực hiện trong trường hợp xấu nhất.
 Các phép toán như tìm kiếm (search), chèn ( insert), và xóa

(delete) thực hiện trong thời gian O(log n).
 Thay vì thời gian là O (n) như cây nhị phân thông thường

trong trường hợp dữ liệu đã được sắp xếp trước khi chèn.


Quy tắc của cây đỏ đen
 Cây đỏ đen là một cây nhị phân tìm kiếm( BST) tuân

thủ các quy tắc sau:
 Mọi node phải là đỏ hoặc đen.
 Node gốc và các node lá phải luôn luôn đen.
 Nếu một node là đỏ, những node con của nó phải
đen.
 Mọi đường dẫn từ gốc đến một lá phải có cùng số
lượng node đen hay có cùng chiều cao đen black
height(bh).


Cây đỏ đen

 Các lá của cây đỏ đen khác với cây nhị phân thông
thường, chúng là các lá NULL, không chứa dữ liệu và
được gán màu đen.
 Chiều cao cây đỏ đen (height):
- Height <= 2*log(n+1)
- Height <= 2*bh


Cấu trúc cây đỏ đen
 Khai báo một nút:

typedef struct NodeTag {
struct NodeTag *left; /* Con trái */
struct NodeTag *right; /* Con phải */
struct NodeTag *parent; /* Cha */
nodeColor color; /* Màunode (BLACK, RED) */
KeyType key; /* Khoá sử dụng tìm kiếm */

NIL
RecType rec; /* Dữ liệu node */
} NodeType;
 Khai báo một nút lá NULL
NIL
#define NIL &sentinel /* Node cầm canh */
static NodeType sentinel = { &sentinel, &sentinel, 0, BLACK, 0};

NIL


Cấu trúc cây đỏ đen
 Tạo một nút mới :

NodeType *CreateNode(NodeType parent, KeyType key, RecType *rec) {
NodeType*p = new NodeType;
if(!p) exit(1);
x->parent = parent;
x->left = x->right = NIL;
x->color = RED; //Nút thêm vào luôn được gán màu đỏ
x->key = key;
x->rec = *rec;
}
 Khai báo một cây mới.
static NodeType *root = NIL;


Các thuật toán cơ bản của cây đỏ đen
1. Thêm một nút mới vào cây.
2. Xóa một nút khỏi cây.


3. Tìm kiếm một nút trên cây
4. In cây ra màn hình
5. Xóa cây.


1. Thêm một nút mới
- Việc chèn hay xóa được thực hiện giống với cây
nhị phân thông thường
- Tuy nhiên quá trình này, các quy tắc của cây đỏ
đen có thể bị vi phạm, chúng ta sẽ thực hiện các thao
tác sau đây để khôi phục tính chất cây đỏ đen:
 Các phép lật màu trên đường đi xuống.
 Các phép quay trên đường đi xuống.
Thực tế chỉ cần không quá O (log n) phép đổi màu
và không quá 2 phép quay cho phép chèn và 3 cho
phép xóa.


Các thao tác khôi phục cây

 Các thao tác này chỉ được thực hiện khi cây xuất hiện

xung đột đỏ-đỏ ( vi phạm quy tắc con của nút đỏ phải
là đen).
 Khi giải quyết xung đột đỏ-đỏ thì các xung đột khác
cũng được giải quyết đồng thời:
Nút gốc luôn luôn đen.
Chiều cao đen từ gốc đến lá là như nhau



Các trường hợp vi phạm chính
 Tính chất cây đỏ đen bị vi phạm khi xuất hiện xung

đột đỏ-đỏ, ta có thể chia làm 3 trường hợp chính:
1. Nút N đỏ có cha P đỏ và có nút chú bác U đỏ.

2. Nút N đỏ có cha P đỏ và có nút chú bác U đen, G là
ông nội của N.(N khác phía với P).
3. Nút N đỏ có cha P đỏ và có nút chú bác U đen, G là
ông ngoại của N. (N cùng phía với P).
( Nút G có màu đen)


1. Nút N đỏ có cha P đỏ và có nút chú bác U đỏ.
Trường hợp này chỉ cần dùng phép lật màu để giải quyết
- Có 4 vị trí để thêm N

G

U
P

N

U
P

N


N

N

- Khi thêm N thì xuất hiện xung đột đỏ đỏ, ta thực hiện phép lật màu
3 nút G,P,U:
P  BLACK, U  BLACK.
- Nếu nút G là nút gốc thì giữ nguyên màu đen. Nếu G bị chuyển sang
màu đỏ thì có thể vi phạm quy tắc đỏ-đỏ, khi đó coi G như N và xét lại.


2. Nút N đỏ có cha P đỏ và có nút chú bác U đen,
nhưng N có ông nội G.(N khác phía với P).
 Trước tiên ta định nghĩa N là cháu ngoại và cháu nội:

-N là cháu ngoại của G nếu nó cùng phía với P
-N là cháu nội của G nếu nó khác phía với P.
G

P

Cháu ngoại

P

N

N
N


Cháu nội

N

Cháu ngoại


2. Nút N đỏ có cha P đỏ và có nút chú bác U đen,
nhưng N có ông nội G.(N khác phía với P).
 Ta thực hiện phép một phép quay để tạo một cháu

mới là cháu ngoại, nghĩa là chuyển về trường hợp 3.
G

P

G

U

N

Rotate Left

U

P

N


Rotate Right


3. Nút N đỏ có cha P đỏ và có nút chú bác U đen,
nhưng N có ông ngoại G. (N cùng phía với P).
 Ta thực hiện đổi màu hai nút G và P, và dùng một

phép xoay để giải quyết xung đột đỏ-đỏ.
G
P

Đổi màu

N
P

G
P

U
G

U
G

U

N

Rotate Right


Đổi màu

N
P

U

N

Rotate Left


Nhận xét khi chèn
 Các nút chèn vào luôn là đỏ để chiều cao đen không

đổi.
 Quá trình khôi phục tính chất của cây đỏ đen được
thực hiện như sơ đồ sau:

Trường hợp 1

End

Trường hợp 2

Trường hợp 3

End



Phép xóa một nút
 Ta tìm vị trí nút cần xóa như cây nhị phân.
 Nếu nút cần xóa có 2 con thì ta tìm phần tử thế mạng (có thể

là nút lớn nhất bên trái hoặc nhỏ nhất bên phải). Phần tử thế
mạng có thể không có con hoặc chỉ có một con.
 Do đó ta chỉ cần xét chung trường hợp nút bị xóa không có
con hoặc chỉ có một con. Gọi nút đó là y.
 Nếu nút bị xóa y màu đỏ thì chắc chắn con và cha của nó phải
là nút đen. Việc xóa y được thực hiện bình thường.
 Trường hợp phức tạp xảy ra khi nút bị xóa y màu đen. Ta thực
hiện thay nó bằng con của nó hoặc bằng nút lá NULL (nếu nó
không có con). Việc này sẽ làm giảm chiều cao đen của những
nhánh chứa y. Nếu y không phải là gốc thì ta phải thực hiện
khôi phục lại thuộc tính đỏ đen của cây.


Phép xóa một nút
 Gọi nút mới thay thế cho y là N.
 Nếu N là màu đỏ thì chỉ cần đổi màu của N thành đen là

thuộc tính của cây đỏ đen sẽ phục hồi.
 Nếu N là màu đen thì không thể đổi màu N. Phải thực hiện
bằng cách khác. Có 4 trường hợp xảy ra:
+ Nút anh em với N màu đỏ.
+ Nút anh em với N màu đen và nút này có 2 con là đen
+ Nút anh em với N màu đen và có một con màu đỏ là cháu
nội của P, một con màu đen.
+ Nút anh em với N màu đen và có một con màu đỏ là cháu

ngoại của P.


Nút anh em với N màu đỏ.
 Ta thực hiện đổi màu 2 nút S và P, rồi xoay nút cha của N

để chuyển về các trường hợp khác với SL là anh em mới của
N.
Đổi màu

P
S

N
P

N

Xoay

P
S

SSR

SL

SSL

SR


SL

Đổi màu

N
P

SR

N


Nút anh em với N màu đen và nút này có 2 con là
đen
 Ta thực hiện đổi màu nút S, như thế chiều cao đen của

nhánh bên phải P và bên trái P là như nhau. Nhưng tại P thì
chiều cao đen lại giảm đi 1. Coi P là N và xét lại từ đầu.
P

N

P

Đổi màu

S

SL


S

SR

SL

N

SR


Nút anh em với N màu đen và có một con màu đỏ
là cháu nội của P , một con màu đen.
 Ta thực hiện đổi màu, rồi quay nút S để chuyển về

trường hợp 4.
P

N

P

Đổi
Xoay
màu

SSL

SL


SSR

SSL

SSR

SR

SL

N

SR


Nút anh em với N màu đen và có một con màu đỏ là
cháu ngoại của P
 Đổi màu S thành màu của P , màu của P thành đen,

và màu của S con đỏ thành đen rồi xoay P sang trái.
P
S

N
P

N

P

S

Đổi
Xoay
màu
SSR

SLSL

SSL

SR

SL

N
P

SRSR

N


Phần II - AA Tree
1. Giới thiệu chung:
 AA Tree được đưa ra bởi Arne Andersson và lấy
theo tên ông.
 AA Tree là một biến dạng của cây đỏ đen. Nó cũng
là một cây nhị phân tìm kiếm nhưng khác với cây
đỏ đen là nó chỉ cho phép có con phải màu đỏ.

 Ngoài ra các nút sẽ được gắn một cấp độ(mức) xác
định thay vì màu như cây đỏ đen.
 Để đảm bảo cây cân bằng thì các nút phải tuân theo
các quy tắc được đặt ra.


1. Giới thiệu chung:
 Các quy tắc của AA Tree:
1.
2.
3.
4.

5.

Các nút lá có mức bằng 1.
Mức của nút con trái luôn nhỏ hơn mức của nút
cha.
Nút con phải có mức nhỏ hơn hoặc bằng nút cha.
Nút cháu phải có mức nhỏ hơn nút ông.
Mọi nút có mức lớn hơn 1 phải có 2 con.

(Nguồn: />

1. Giới thiệu chung:
 Thông thường, cây đỏ đen phải xét đến 7 trường hợp

để cân bằng lại cây.

 Nhưng AA Tree thì chỉ cần xét 2 trường hợp chính:



2. Các thao tác chính.
 Tương ứng với 2 trường hợp chính thì ta có 2 thao

tác được sử dụng khi vi phạm các quy tắc.
 Đó là skew và split. Skew giống như phép xoay phải
và split giống như phép quay trái của cây đỏ đen.
 Skew sử dụng khi xuất hiện nút con trái cùng mức
với nút cha.
 Split sử dụng khi xuất hiện nút cháu phải cùng mức
với nút ông.