Bài giảng Cấu trúc dữ liệu và giải thuật - Cấu trúc cây - Văn Chí Nam

US 2013 
15 
Tìm cha một đỉnh. 
• Parent(x) 
Tìm đỉnh con trái nhất. 
• EldestChild(x) 
Tìm đỉnh kề phải. 
• NextSibling(x) 
b c 
h g d 
i 
e f 
Parent(b) = a 
Parent(a)? 
Eldest- 
Child(c) = g 
NextSibling(g) = h 
NextSibling(h)? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
16 
Duyệt trước 
• a b d e i j c f g k h 
Duyệt giữa 
• d b i e j a f c k g h 
Duyệt sau 
• d i j e b f k g h c a 
Duyệt theo chiều sâu 
b c 
h f d 
i j 
e g 
k 
void Preorder(NODE A) 
{ 
 NODE B; 
 Visit(A); 
 B = EldestChild(A); 
 while (B != ) { 
 Preorder(B); 
 B = NextSibling(B); 
 } 
} 
void Postorder(NODE A) 
{ 
 NODE B; 
 B = EldestChild(A); 
 while (B != ) { 
 Postorder(B); 
 B = NextSibling(B); 
 } 
 Visit(A); 
} 
17 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
Pre-order Post-order 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
18 
In-Order 
void Inorder(NODE A) 
{ 
 NODE B; 
 B = EldestChild(A); 
 if (B != ) { 
 Inorder(B); 
 B = NextSibling(B); 
 } 
 Visit(A); 
 while (B != ) { 
 Inorder(B); 
 B = NextSibling(B); 
 } 
} 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
19 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
20 
b c 
h f d 
i j 
e g 
k 
info child 
1 a 
2 b 
3 c 
4 d 
5 e 
6 f 
7 g 
8 h 
9 i 
10 j 
11 k 
id next 
2 
4 
6 
9 
11 
5 
7 
10 
3 
8 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
21 
A 
B C 
D E F 
I J K 
G H 
Root 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
22 
Info Eldest Child Next Sibling 
1 a 2 0 
2 b 4 3 
3 c 6 0 
4 d 0 5 
5 e 9 0 
6 f 0 7 
7 g 11 8 
8 h 0 0 
9 i 0 10 
10 j 0 0 
11 k 0 0 
b c 
h f d 
i j 
e g 
k 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
23 
A 
B C 
D E F 
I J K 
G H 
Root 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
24 
Info Parent 
1 a 0 
2 b 1 
3 c 1 
4 d 2 
5 e 2 
6 f 3 
7 g 3 
8 h 3 
9 i 5 
10 j 5 
11 k 7 
b c 
h f d 
i j 
e g 
k 
Binary tree 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
25 
 Là cây mà mỗi đỉnh 
có bậc tối đa bằng 2. 
 Các cây con được 
gọi là cây con trái và 
cây con phải. 
 Có toàn bộ các thao 
tác cơ bản của cây. 
26 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
b c 
f d 
h i 
e g 
j 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
27 
 Cây nhị phân hoàn chỉnh (complete binary tree) 
 Cây nhị phân có chiều cao là h thì có đầy đủ các node 
từ mức 1 đến mức h-1. Các node ở mức h sẽ được lấp 
từ trái sang phải. 
 Cây nhị phân đầy đủ (full binary tree) 
 Cây nhị phân có chiều cao là h thì tất cả các node nằm 
ở mức từ 1 đến h-1 đều có 2 node con. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
28 
b c 
f d 
h i 
e g 
j 
a 
b c 
f d e g 
Cây nhị phân hoàn chỉnh Cây nhị phân đầy đủ 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
29 
 Cây tổ chức thi đấu 
 Cây biểu thức số học 
 Lưu trữ và tìm kiếm 
thông tin. 
* + 
1 4 
3 4 
- sin 
30 
Cây biểu thức: 
4 * (3 – 4) + (1 + sin(30)) 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
30 
 Cây nhị phân tìm kiếm là cây nhị phân thỏa mãn 
các điều kiện sau: 
1. Khóa của các đỉnh thuộc cây con trái nhỏ hơn 
khóa gốc. 
2. Khóa của gốc nhỏ hơn khóa các đỉnh thuộc 
cây con phải. 
3. Cây con trái và cây con phải của gốc cũng là 
cây nhị phân tìm kiếm. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
31 
4 10 
9 2 
5 7 
6 23 
20 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
32 
 Đặc điểm: 
 Có thứ tự 
Không có phần tử trùng 
Dễ dàng tạo dữ liệu sắp xếp, và tìm kiếm 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
 Thêm phần tử (khóa) 
 Tìm kiếm phần tử (khóa) 
 Xóa phần tử (khóa) 
 Sắp xếp 
 Duyệt cây 
 Quay cây 
34 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
35 
 Bước 1: Bắt đầu từ gốc 
 Bước 2: So sánh dữ liệu (khóa) cần thêm với 
dữ liệu (khóa) của node hiện hành. 
Nếu bằng nhau => Đã tồn tại. Kết thúc 
Nếu nhỏ hơn => Đi qua nhánh trái, Tiếp bước 2. 
Nếu lớn hơn => Đi qua nhánh phải, Tiếp bước 2. 
 Bước 3: Không thể đi tiếp nữa => Tạo node mới 
với dữ liệu (khóa) cần thêm. Kết thúc 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
36 
 Bước 1: Bắt đầu từ gốc 
 Bước 2: So sánh dữ liệu (khóa) cần tìm với dữ 
liệu (khóa) của node hiện hành. 
Nếu bằng nhau => Tìm thấy. Kết thúc 
Nếu nhỏ hơn => Đi qua nhánh trái, Tiếp bước 2. 
Nếu lớn hơn => Đi qua nhánh phải, Tiếp bước 2. 
 Bước 3: Không thể đi tiếp nữa => Không tìm 
thấy. Kết thúc. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
37 
 Tìm đến node chứa dữ liệu (khóa) cần xóa. 
 Xét các trường hợp: 
Node lá 
Node chỉ có 1 con 
Node có 2 con: dùng phần tử thế mạng để xóa thế. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
38 
 Cho cây nhị phân tìm kiếm 
 Thứ tự duyệt các node 
nếu sử dụng Duyệt giữa? 
 Nêu nhận xét 
Có thể dễ dàng tạo dữ liệu sắp xếp 
nếu dùng phép duyệt giữa 
8 19 
16 1 
14 
13 
9 
18 
8 19 1 9 13 14 15 16 18 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
39 
 Duyệt trước 
4 
2 
1 3 25 
20 
23 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
40 
 Duyệt giữa 
4 
2 
1 3 25 
20 
23 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
41 
 Duyệt sau 
4 
2 
1 3 25 
20 
23 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
42 
P P Quay trái cây P 
18 
8 35 
20 
18 
35 
8 20 
50 
55 
55 
50 
P 
Quay trái cây P 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
43 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
44 
P P 
Quay phải cây P 
50 
55 40 
37 45 
36 
40 
50 37 
55 36 45 
Quay phải cây P 
P 
65 
65 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
45 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
46 
 Đối với phép tìm kiếm: 
 Trường hợp tốt nhất: mỗi nút (trừ nút lá) đều có 2 con: 
O(log2n) (chính là chiều cao của cây). 
 Trường hợp xấu nhất: cây trở thành danh sách liên kết: 
O(n). 
 Trường hợp trung bình là bao nhiêu? 
 O(log2n) 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
47 
 Tạo cây nhị phân tìm kiếm theo thứ tự nhập 
như sau: 1, 8, 9, 12, 14, 15, 16, 18, 19 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
48 
 Tạo cây nhị phân tìm kiếm theo thứ tự nhập 
như sau: 1, 8, 9, 12, 14, 15, 16, 18, 19 
8 
19 
1 
9 
12 
14 
15 
16 
18 
AVL tree 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
49 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
50 
 Do G.M. Adelsen Velskii và E.M. Lendis đưa ra 
vào năm 1962, đặt tên là cây AVL. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
51 
 Cây cân bằng AVL là cây nhị phân tìm kiếm mà 
tại mỗi đỉnh của cây, độ cao của cây con trái và 
cây con phải không chênh lệch quá 1. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
52 
 Ví dụ : 
12 
8 
5 11 
18 
17 
4 7 
2 
12 
8 
5 11 
18 
17 
4 7 
Cây AVL? Cây AVL? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
53 
 Việc xây dựng cây cân bằng dựa trên cây nhị 
phân tìm kiếm, chỉ bổ sung thêm 1 giá trị cho 
biết sự cân bằng của các cây con như thế nào. 
 Trong đó giá trị bal (balance, cân bằng) có thể 
là: 0: cân bằng; 1: lệch trái; 2: lệch phải 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
54 
 Mất cân bằng trái-trái (L-L) 
 Mất cân bằn trái-phải (L-R) 
 Mất cân bằng phải-phải (R-R) 
 Mất cân bằng phải-trái (R-L) 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
55 
 Mất cân bằng trái-trái (L-L) 
12 
5 
18 
17 
4 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
56 
 Mất cân bằng trái-phải (L-R) 
12 
5 
18 
17 
7 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
57 
 Mất cân bằng phải-phải (R-R) 
12 
8 
5 11 
4 7 
22 
25 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
58 
 Mất cân bằng phải-trái (R-L) 
12 
8 
5 11 
4 7 
22 
20 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
59 
 Giả sử tại một node cây xảy ra mất cân bằng 
bên phải (cây con phải chênh lệch với cây con 
trái hơn một đơn vị): 
Mất cân bằng phải-phải (RR) 
Quay trái 
Mất cân bằng phải-trái (R-L) 
Quay phải 
Quay trái 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
60 
 P mất cân bằng phải-phải (RR): 
h 
h+1 h 
P 
Q 
h 
h+1 
h 
P Quay trái cây P 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
61 
 P mất cân bằng phải-phải (RR): 
18 
8 35 
20 
18 
35 
8 20 
50 
55 
55 
50 
P 
Q 
Quay trái cây P 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
62 
 P mất cân bằng phải-trái (RL): 
 Bước 1: quay phải Q 
 Bước 2: quay trái cây P 
h 
h-1 h 
P 
Q 
h 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
63 
 P mất cân bằng phải-trái (RL): 
 Bước 1: quay phải cây Q 
h 
h-1 h 
P 
Q 
h 
h 
h h- 1 
P 
Q 
h 
Quay phải cây Q 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
64 
 P mất cân bằng phải-trái (RL): 
 Bước 2: quay trái cây P 
h h h- 1 
P 
h 
h 
h h- 1 
P 
Q 
h 
Quay trái cây P 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
65 
 P mất cân bằng phải-trái (RL) – Bước 1: 
18 
35 
8 20 
50 
55 40 
37 45 
36 
18 
35 
8 20 
40 
50 37 
55 36 45 
Quay phải cây Q P 
Q 
65 
65 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
66 
 P mất cân bằng phải-trái (RL) - Bước 2: 
18 
35 
8 20 
40 
50 37 
55 36 45 
35 
40 
50 
55 
65 8 20 
37 
36 
18 
45 
Quay trái cây P P 
Q 
65 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
67 
 Khi một node cây xảy ra mất cân bằng bên trái 
(cây con trái chênh lệch với cây con phải hơn 
một đơn vị): (thực hiện đối xứng với trường hợp 
mất cân bằng bên phải) 
Mất cân bằng trái-trái (LL) 
Quay phải 
Mất cân bằng trái-trái (L-R) 
Quay trái 
Quay phải 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
68 
Theo Wikipedia 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
69 
 Thực hiện hoàn toàn tương tự cây nhị phân tìm 
kiếm. 
4 10 
9 2 
5 7 
6 23 
20 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
70 
 Thực hiện tương tự với việc thêm phần tử của 
cây nhị phân tìm kiếm. 
 Nếu xảy ra việc mất cân bằng thì xử lý bằng các 
trường hợp mất cân bằng đã biết. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
71 
 Thực hiện tương tự cây nhị phân tìm kiếm: xét 3 
trường hợp, và tìm phần tử thế mạng nếu cần. 
 Sau khi xóa, nếu cây mất cân bằng, thực hiện 
cân bằng cây. 
 Lưu ý: việc cân bằng sau khi hủy có thể xảy ra 
dây chuyền. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
72 
 Ví dụ: xóa 35 
35 
40 
50 
55 
65 8 20 
37 
36 
18 45 
36 
40 
50 
55 
65 8 20 
37 18 45 
Phần tử thế mạng là 36 
Cây vẫn cân bằng nên 
không phải hiệu chỉnh 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
73 
 Xóa phần tử 45 
36 
40 
50 
55 
65 8 20 
37 18 45 
36 
40 
50 
55 
8 20 
37 18 
Node 50 bị lệch phải !!! 
65 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
74 
 Xóa phần tử 45: cân bằng lại cây 
36 
40 
50 
55 
8 20 
37 18 
65 
Quay trái tại node 50 
36 
40 
55 
65 
8 20 
37 18 50 
AA tree 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
75 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
76 
 Được đặt tên theo tác giả Arne Anderson (Thụy 
Điển). 
 Công trình được công bố năm 1993 (Balanced 
Search Trees Made Simple). 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
77 
 Mức của node 
 Liên kết ngang 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
78 
 Mức của node: 
 Số liên kết trái từ node đó đến node NULL. 
Mức của NULL là 0. 
Mức của node lá là 1. 
5 10 
15 
20 
Mức 1 
Mức 2 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
79 
 Liên kết ngang: 
 Liên kết giữa node cha và node con có cùng mức. 
5 10 
15 
20 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
80 
 Cây AA là cây nhị phân tìm kiếm thỏa mãn các tính chất 
sau: 
[1] Mức của node con trái bắt buộc phải nhỏ hơn mức của node 
cha. 
[2] Mức của node con bên phải nhỏ hơn hoặc bằng mức của node 
cha. 
 Liên kết ngang bắt buộc hướng sang phải. 
[3] Mức của node cháu bên phải bắt buộc nhỏ hơn mức của node 
ông. 
 Không tồn tại 2 liên kết ngang liên tiếp. 
[4] Mọi node có mức lớn hơn 1 phải có 2 node con. 
[5] Nếu một node không có liên kết ngang phải thì cả hai node con 
của nó phải cùng mức. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
81 
30 70 
85 
5 
60 
80 
10 
90 
15 
20 
50 
35 40 65 55 
Mức của các node? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
82 
30 70 
85 
5 
60 
80 
10 
90 
15 
20 
50 
35 40 65 55 
So sánh mức của node con trái với mức của node cha trực tiếp của nó? 
Các cặp node: 15 và 30, 5 và 15, 50 và 70, 35 và 50, 55 và 60, 80 và 85 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
83 
30 70 
85 
5 
60 
80 
10 
90 
15 
20 
50 
35 40 65 55 
Các liên kết ngang? 
Hướng của liên kết ngang? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
84 
30 70 
85 
5 
60 
80 
10 
90 
15 
20 
50 
35 40 65 55 
Có tồn tại 2 liên kết ngang liên tiếp? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
85 
30 70 
85 
5 
60 
80 
10 
90 
15 
20 
50 
35 40 65 55 
Mọi node có mức lớn hơn 1 đều có 2 node con? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
86 
30 70 
85 
5 
60 
80 
10 
90 
15 
20 
50 
35 40 65 55 
So sánh mức của các node con của các node: 15, 70, 60, 85? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
87 
 Skew 
 Split 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
88 
 Skew: 
Dùng để loại bỏ liên kết ngang trái. 
P X 
A B C 
P X 
A B C 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
89 
 Split: 
Dùng để loại bỏ 2 liên kết ngang liên tiếp 
X P 
A B 
G 
X 
P 
A B 
G 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
90 
 Skew: dùng để loại bỏ liên kết ngang bên trái. 
 Split: dùng để loại bỏ 2 liên kết ngang (phải) liên 
tiếp. 
 Biến đổi theo thứ tự Skew -> Split (nếu có). 
 Khi thực hiện thao tác Split, node giữa được 
tăng thêm một mức. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
91 
 Duyệt cây, Tìm kiếm: 
 Tương tự cây nhị phân tìm kiếm 
 Thêm phần tử 
 Xóa phần tử 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
92 
 Thực hiện tương tự trên cây nhị phân tìm kiếm. 
 Phần tử được thêm vào luôn ở mức 1. 
 Sau khi thêm, thực hiện các thao tác Skew 
và/hoặc Split để đảm bảo tính chất của cây. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
93 
 Vẽ cây AA theo thứ tự nhập sau đây: 
 4, 7, 6, 3, 5, 9, 15, 27, 8, 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
94 
6 
9 
3 
4 
5 7 
27 
15 8 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
95 
 Hãy vẽ cây AA theo thứ tự nhập sau đây: 
 40, 8, 27, 15, 9, 5, 3, 6, 7, 4 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
96 
9 
27 
5 7 
3 4 6 8 15 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
97 
 Nếu không phải là node lá (mức của node là 1), 
tìm phần tử thế mạng: 
 Phần tử lớn nhất bên nhánh trái (node lá). 
 Xóa node lá: 
Giảm mức của node cha nếu mức của node lá nhỏ hơn. 
 Thực hiện các thao tác Skew, Split cần thiết 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
98 
 Xóa phần tử 8 
6 
9 
3 
4 
5 7 
27 
15 8 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
99 
 Xóa phần tử 8 
6 
9 
3 
4 
5 7 
27 
15 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
100 
 Xóa phần tử 5 
6 
9 
3 
4 
5 7 
27 
15 8 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
101 
 Xóa phần tử 5 
6 
9 
3 
4 
7 
27 
15 8 40 
Giảm mức của 4 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
102 
 Xóa phần tử 5 
6 
9 3 4 
7 
27 
15 8 40 
Skew tại 4 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
103 
 Xóa phần tử 5 
6 
9 4 3 
7 
27 
15 8 40 
Giảm mức 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
104 
 Xóa phần tử 5 
6 9 
4 3 7 
27 
15 8 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
105 
 Xóa phần tử 5 
6 9 
4 3 7 
27 
15 8 40 
Split tại 6 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
106 
 Xóa phần tử 5 
6 
9 
4 3 7 
27 
15 8 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
107 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
108 
1. Xây dựng giải thuật xóa một đỉnh với khóa cho 
trước ra khỏi cây nhị phân tìm kiếm. 
2. Hãy chứng tỏ rằng trường hợp tìm kiếm trung 
bình cho cây nhị phân tìm kiếm là O(log2n)? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
109 
3. Biểu diễn tình trạng cây nhị phân tìm kiếm sau 
khi thực hiện các thao tác sau: 
 Lần lượt thêm các node theo trình tự: M G B K S P D 
C A H L F X N T W R. 
Xóa M. 
Xóa S. 
 Cho biết kết quả sau khi duyệt cây theo các trình tự 
giữa, trước và sau. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
110 
4. Xây dựng giải thuật thực hiện các thao tác sau 
trên cây nhị phân tìm kiếm: 
 - Đếm số node lá. 
 - Tính độ cao cây. 
 - Tính độ cao của 1 node trong cây. 
 - Xuất ra các node có cùng độ cao. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
111 
5. Biểu diễn tình trạng cây cân bằng AVL sau khi 
thực hiện các thao tác sau: 
 Lần lượt thêm các node theo trình tự: 13 7 2 11 19 16 4 
3 1 8 12 6 24 14 20 23 18 
Xóa 13. 
Xóa 19 
Lưu ý: cho biết các trường hợp mất cân bằng. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
112 
6. Hãy vẽ cây AVL với 12 nút có chiều cao cực đại 
trong tất cả các cây AVL 12 nút. 
7. Tìm 1 dãy N khoá sao cho khi lần lượt dùng 
thuật toán thêm vào cây AVL sẽ phải thực hiện 
mỗi thao tác cân bằng (LL, LR, RL, RR) lại ít 
nhất 1 lần. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
113 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
114 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
115 
 Vẽ cây AA theo thứ tự nhập sau đây: 
 4, 7, 6, 3, 5, 9, 15, 27, 8, 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
116 
4 
Thêm 4 
Chuẩn bị: Thêm 7 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
117 
4 
7 
Thêm 7 
Chuẩn bị: Thêm 6 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
118 
4 
7 
6 
Thêm 6 
Quan sát các liên kết mới thêm 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
119 
4 
7 6 
Thêm 6 
Quay phải nút 7 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
120 
4 
6 
7 
Kết quả sau khi quay phải nút 7 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
121 
4 6 7 
Hai liên kết ngang liên tiếp 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
122 
6 
7 4 
Chuẩn bị: Thêm 3 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
123 
6 
7 4 
3 
6 
7 4 3 
Thêm 3 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
124 
6 
7 4 3 
Chuẩn bị: Thêm 5 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
125 
6 
7 4 3 
5 
Thêm 5 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
126 
6 
7 4 3 5 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
127 
6 
7 
3 
4 
5 
Mức hiện hành của 4, 6? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
128 
6 
7 3 
4 
5 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
129 
6 
7 3 
4 
5 
Chuẩn bị: Thêm 9 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
130 
6 
7 3 
4 
5 
9 
Thêm 9 
Chuẩn bị: Thêm 15 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
131 
6 
7 3 
4 
5 
9 
15 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
132 
6 
7 3 
4 
5 9 15 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
133 
6 
9 3 
4 
5 
7 15 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
134 
6 9 
3 
4 
5 
7 15 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
135 
6 
9 
3 
4 
5 7 15 
Chuẩn bị: Thêm 27 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
136 
6 
9 
3 
4 
5 7 15 
27 
Thêm 27 
Chuẩn bị: Thêm 8 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
137 
6 
9 
3 
4 
5 7 15 
27 8 
Thêm 8 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
138 
6 
9 
3 
4 
5 7 15 27 8 
Chuẩn bị: Thêm 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
139 
6 
9 
3 
4 
5 7 15 27 8 
40 
Thêm 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
140 
6 
9 
3 
4 
5 7 15 27 8 40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
141 
6 
9 
3 
4 
5 7 27 
15 
8 
40 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
142 
6 
9 
3 
4 
5 7 
27 
15 8 40