Bài giảng Thiết kế và đánh giá thuật toán - Cấu trúc cây - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán
Cấu Trúc Cây
TS. Lê Nguyên Khôi
Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung

 Khái niệm cơ bản

 Duyệt cây

 Cây nhị phân

 Cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân cân bằng

 Cây thứ tự bộ phận
1
Phân Loại Cây

 Cây tự do (Đồ thị)

 Đồ thị – mạng

 Vô hướng, có hướng

 Trọng số

 Liên thông

 Chu trình, phi chu trình

 Cây có gốc

 Có 1 đỉnh được coi là gốc

 Quan hệ cha - con
2
Cây Tự Do (Đồ Thị)
vô hướng định hướng
3
ĐHQG
Cầu Giấy
BX Kim Mã
Ngã tư Sở
ĐHQG
Cầu Giấy
BX Kim Mã
Ngã tư Sở
Cây Tự Do (Đồ Thị)
trọng số không trọng số
4
ĐHQG
Cầu Giấy
BX Kim Mã
Ngã tư Sở
5 7
11 15
ĐHQG
Cầu Giấy
BX Kim Mã
Ngã tư Sở
Cây Tự Do (Đồ Thị)
liên thông không liên thông
5
Cây Tự Do (Đồ Thị)
chu trình phi chu trình
6
Cây Tự Do (Đồ Thị)

 Mạng vận tải

 Mạng liên lạc

 Mạng thông tin

 Mạng xã hội

 Mạng phụ thuộc
7
Cây Có Gốc – Định Nghĩa

 Sử dụng khái niệm đồ thị có hướng

 Có một đỉnh đặc biệt được gọi là gốc cây

 Mỗi đỉnh C bất kỳ không phải là gốc, tồn 
tại duy nhất một đỉnh P có đường đi từ P 
đến C. Đỉnh Parent được gọi là cha của 
đỉnh Child, và Child là con của Parent.

 Có đường đi duy nhất từ gốc tới mỗi đỉnh 
của cây.
8
Cây Có Gốc – Ví Dụ
9
gốc
đỉnh trong
lá
A
B C D
E F G
mức 0
mức 1
mức 2
Cây Có Gốc – Thuật Ngữ

 Độ cao (height)

 của một đỉnh là độ dài đường đi dài nhất từ 
đỉnh đó tới một lá.

 độ cao của lá bằng 0.

 độ cao của cây là độ cao của gốc

 Độ sâu (depth)

 của một đỉnh là độ dài đường đi từ gốc tới 
đỉnh đó

 độ sâu của gốc bằng 0.
10
Cây Có Gốc – Độ Cao

 Độ cao của một đỉnh là độ dài 
đường đi dài nhất từ đỉnh đó 
tới một lá.

 Xác đinh độ cao của mỗi đỉnh
ℎ  = max
∀
ℎ(
) + 1
11
A
B C D
E F G
Cây Biểu Thức
12
*
+ -
/ 3 7 4
6 2
Duyệt Cây

 Thứ tự trước (preorder)

 Thứ tự trong (inorder)

 Thứ tự sau (postorder)
13
r
T1 T2 Tk
r1 r2 rk
Duyệt Cây – Thứ Tự Trước

 Thăm gốc r

 Duyệt lần lượt các cây
con T1,  , Tk theo thứ
tự trước

 Còn được biết đến là
kỹ thuật tìm kiếm theo
độ sâu
A-B-E-F-C-D-G
14
r
T1 T2 Tk
r1 r
2
rk
A
B C D
E F G
Duyệt Cây – Thứ Tự Trước – Mã Giả
Algorithm preOrder(p)
visit(p)
for each child ci of p
preOrder(ci)
15
Duyệt Cây – Thứ Tự Trong

 Duyệt cây con trái T1
theo thứ tự trong

 Thăm gốc r

 Duyệt lần lượt các cây
con T2,  , Tk theo thứ
tự trong
E-B-F-A-C-G-D
16
r
T1 T2 Tk
r1 r
2
rk
A
B C D
E F G
Duyệt Cây – Thứ Tự Trong – Mã Giả
Algorithm inOrder(p)
inOrder(c1)
visit(p)
for each child ci of p
inOrder(ci)
17
Duyệt Cây – Thứ Tự Sau

 Duyệt lần lượt các cây
con T1,  , Tk theo thứ
tự sau

 Thăm gốc r
E-F-B-C-G-D-A
18
r
T1 T2 Tk
r1 r
2
rk
A
B C D
E F G
Duyệt Cây – Thứ Tự Sau – Mã Giả
Algorithm postOrder(p)
for each child ci of p
postOrder(ci)
visit(p)
19
Cây Nhị Phân

 Mỗi đỉnh có nhiều nhất 2 đỉnh con

 Nhị phân chuẩn (full/proper binary tree)

Mỗi đỉnh có 0 hoặc 2 đỉnh con

 Nhị phân đầy đủ (complete binary tree)

 Các lá ở cùng mức

 Nhị phân gần đầy đủ (almost complete 
binary tree)

 Có con phải thì có con trái
20
Cây Nhị Phân Đầy Đủ

 Độ cao ℎ có 2 − 1 lá

  lá có độ cao log  + 1
21
Cây Tìm Kiếm Nhị Phân

 Cây tìm kiếm nhị phân là cây nhị phân 
lưu khóa ở các đỉnh trong của nó và thỏa 
mãn tính chất sau:

 Gọi , ,  là 3 đỉnh sao cho  nằm trong cây 
con trái của  và  nằm trong cây con phải 
của , thỏa mãn
 !(") ≤  !($) ≤  !(%)

 Duyệt cây tìm kiếm nhị phân theo thứ tự 
trong sẽ thăm các khóa theo thứ tự tăng dần
22
Cây Tìm Kiếm Nhị Phân

 Một số thao tác chính:

 Tìm kiếm:

đỉnh có khóa &

đỉnh trước/sau đỉnh có khóa &

đỉnh có khóa min/max

 Sửa đổi:

 thêm đỉnh có khóa &

xóa đỉnh có khóa &

 Mã giả

 Độ phức tạp
23
6
92
41 8
Cây Tìm Kiếm Nhị Phân Cân Bằng

 Cây tìm kiếm nhị phân cân bằng có cấu
trúc của cây tìm kiếm nhị phân nhưng
đảm bảo độ cao của cây là '(log )

 Ví dụ:

 Cây AVL

Tìm kiếm nhanh

 Cây Đỏ-Đen

Sửa đổi nhanh
24
Cây Thứ Tự Bộ Phận – Heap

 Cây nhị phân gần đầy đủ:

 Có tất cả các mức của cây đều không thiếu
đỉnh nào, trừ mức thấp nhất được lấp đầy kể
từ bên trái

 Độ cao là log 
25
2
35
79 8
0
1 2
3 4
5
Cây Thứ Tự Bộ Phận – Heap

 Min heap là cây nhị phân gần đầy đủ với
tính chất:

 Khóa của một đỉnh bất kỳ NHỎ hơn hoặc
bằng khóa của các đỉnh con của nó.

 Max heap là cây nhị phân gần đầy đủ với
tính chất:

 Khóa của một đỉnh bất kỳ LỚN hơn hoặc
bằng khóa của các đỉnh con của nó.
26
Cây Thứ Tự Bộ Phận – Min Heap 

 Một số thao tác chính:

 Tìm nhỏ nhất

 Xóa nhỏ nhất

 Chèn
27
2
35
79 8
0
1 2
3 4
5
Min Heap – Xóa Nhỏ Nhất

 Thay thế gốc bằng đỉnh cuối cùng

 Giải phóng đỉnh cuối cùng

 Khôi phục tính chất thứ tự bộ phận của heap

 Downheap khôi phục lại tính chất bằng cách đảo chỗ
đỉnh có khóa & dọc theo đường đi từ gốc xuống

 Downheap dừng khi & tiến tới một lá hay một đỉnh có
khóa con lớn hơn &

 Độ phức tạp: ((log )
28
2
35
79 8
0
1 2
3 4
5
Min Heap – Xóa Nhỏ Nhất

 Thay thế gốc bằng đỉnh cuối

 Downheap
29
2
35
79 8
0
1 2
3 4 5
8
35
79
0
1 2
3 4
3
85
79
0
1 2
3 4
8
35
79
0
1 2
3 4 5
Min Heap – Chèn

 Tìm tới vị trí để đưa phần tử mới vào

 Lưu phần tử có khóa & vào đỉnh đó

 Khôi phục tính chất thứ tự bộ phận của heap

 Upheap khôi phục lại tính chất bằng cách đảo chỗ
đỉnh có khóa & dọc theo đường đi từ đỉnh tới gốc

 Upheap dừng khi & tiến tới gốc hay một đỉnh có khóa
cha nhỏ hơn &

 Độ phức tạp: ((log )
30
2
35
79 1
0
1 2
3 4
5
Min Heap – Chèn

 Thêm đỉnh cuối mới

 Upheap
31
2
35
79
0
1 2
3 4 5
2
35
79
0
1 2
3 4 15
2
35
79
0
1 2
3 4 15
2
15
79
0
1 2
3 4 35
Sắp Xếp Cây Thứ Tự Bộ Phận

 Liên tục xóa nhỏ nhất của Min heap sẽ được
một dãy tăng dần

 Độ phức tạp: (( log )

 Xây dựng Min heap

 Lần lượt chèn các khóa vào cây Min heap, bắt đầu
từ cây Min heap rỗng

 Độ phức tạp: (( log )
32
2
35
79 8
0
1 2
3 4
5
Xây Dựng Min Heap – Cách Khác

 Chèn liên tục vào Min Heap, nhưng không khôi
phục tính chất thứ tự bộ phận.

 Khôi phục tính chất thứ tự bộ phận (sử dụng
downheap) bắt đầu từ đỉnh chính giữa

 Xem tr.158
33
Sắp Xếp Cây Thứ Tự Bộ Phận – So Sánh

 Giống sắp xếp gộp (merge sort)

 Độ phức tạp (  log 

 Giống sắp xếp chèn (insertion sort)

 In-place algortihm
34