1
Phần 2: Các giải thuật nâng cao
Chương 3: Cây cân bằng
Balanced trees
PGS. TS. TRẦN CAO ĐỆ
Đại Học Cần Thơ
2013
2
Cây tìm kiếm nhị phân
binary search tree

Cây tìm kiếm nhị phân
(TKNP) là cây nhị phân mà
khoá tại mỗi nút lớn hơn
khoá của tất cả các nút
thuộc cây con bên trái và
nhỏ hơn khoá của tất cả các
nút thuộc cây con bên phải.
typedef <kiểu dữ liệu của khoá> KeyType;
typedef struct Node{
KeyType Key;
Node* Left;
Node* Right;
};
typedef Node* Tree;
20
10
175
15
35
22 42

22
35
25 42
24
20
10 35NULL
10
175
15
5
Xóa một nút trên cây TKNP
KeyType DeleteMin (Tree& Root ){
KeyType k;
if (Root->Left == NULL){
k=Root->Key; Root = Root->Right;
return k;
}
else return DeleteMin(Root->Left);
}
void DeleteNode(KeyType x,Tree& Root){
if (Root!=NULL)
if (x < Root->Key) DeleteNode(x,Root->Left);
else if (x > Root->Key) DeleteNode(x,Root->Right);
else if ((Root->Left==NULL) && (Root->Right==NULL)) Root=NULL;
else
if (Root->Left == NULL) Root = Root->Right;
else if (Root->Right==NULL) Root = Root->Left;
else Root->Key = DeleteMin(Root->Right);
}
6

nhất là 1.

Trên cây AVL các phép tìm
kiếm, thêm, xoa một nút là
O(log n), n là số nút

Chứng minh
Gọi N
h
số nút cây AVL có chiều cao h.
N
h
≥ N
h-1
+ N
h-2
+ 1
≥ 2N
h-2
+ 1
≥ 1 + 2(1 + 2N
h-4
)
= 1 + 2 + 2
2
N
h-4
≥ 1 + 2 + 2
2
+ 2

mất cân bằng.

Cân bằng lại
–
Xét cây AVL: tree T=(r,Tl,Tr) trong đó Tl có chiều cao hl và
Tr có chiều cao hr
–
Giả sử nút thêm vào trên Tr.

Nếu hl=hr+1: sau khi thêm vẫn cân bằng

Nếu hl=hr : sau khi thêm vẫn cân bằng

Nếu hl=hr-1 thì sau khi thêm sẽ mất cân bằngcân bằng lại.
–
Tương tự nếu thêm nút vào Tl
9
Single Rotation-RR
RR rotation
10
Single rotation
LL
LL
11
Double rotation-LR
LR
12
Double rotation-RL
RL
13


Nút v là d-nút: V có d≥2 nút con

Cây tìm kiếm đa phân (multi-
way search tree) là cây có thứ
tự với các tính chất sau:
–
Mỗi nút trong là một d-nút có ít
nhất 2 nút con.
–
Mỗi nút lưu trữ một tập hợp
các phần tử dạng (k,x),

k là khóa

x là giá trị kết hợp với khóa

Mỗi d-nút (có các nút con
v
1
, ,v
d
) sẽ lưu d-1 phần tử
dạng (k
1
,x
1
), …, (k
d-1
,x

Cây 2-3-4 hoặc cây (2,4)

Cây (2,4) là 4-cây cân
bằng:
–
Mỗi nút có tối đa 4 nút
con
–
Các nút lá cùng một độ
sâu

Định lý:
Cây (2,4) chứa n phần tử
có chiều cao Θ(logn)
25
5 15
50
0 3 6 7 9 17 19 20
40 70
20
Thêm 1 phần tử vào cây (2,4)
thêm 4,6,12,15,3,5,10,8
4
4, 6
4, 6, 12
4, 6, 12, 15
split
4, 6
12
15

Ta luôn có thể giả sử phần tử bị xóa nằm tại nút v là lá.

Nếu phần tử bị xóa là pt thứ i của nút z, tức là (k
i
,x
i
), là nút
trong, ta đổi (k
i
,x
i
) với một phần tử thích hợp:
–
Tìm nút cực phải trên cây con thứ i của z, gọi đó là nút v
–
Đổi chổ (k
i
,x
i
) với phần tử cuối cùng của v.

Việc xóa như trên:
–
bảo toàn độ sâu
–
Không bảo toàn điều kiện về số phần tử

chuyển phần tử từ anh em (3-nút, 4-nút) sang, hoặc

Kết hợp 2 nút

Gốc: đen
–
Nút ngoài: đen
–
Con nút đỏ là nút đen
–
Tất cả các nút ngoài (NIL)
có cùng độ sâu đen (cùng
số nút đen tiền bối)

Định lý: Cây đỏ-đen chứa n
nút sẽ có độ cao O(Logn)
–
CM: Tr172