CÂY NH PHÂNỊ
TMT
1
CÁC KHÁI NIỆM
1. Cấu trúc cây nhị phân
2. Các loại cây nhị phân
a/ Cây nhị phân đúng (Strictly Binary Tree):
Tất cả các nút đều có đúng hai con (ngoại
trừ nút lá).
2
B
A
C
X F
H I
D E
G
Y
B
A
C
X F
H I
D E
G
Y
CÁC KHÁI NIỆM
b/ Cây nhị phân đầy (Complete Binary
Tree): là cây nhị phân đúng và tất cả các
nút lá ở cùng mức.
3
B
A
C
F
G
N O
D
E
J
KL
M
H I
B
A
C
F
G
N O
D
E
J
KL
M
H I
ĐẶC ĐIỂM CÂY NHỊ PHÂN TÌM KIẾM
Là cây nhị phân
Giá trị của một node
bất kỳ luôn lớn hơn
giá trị của tất cả các
node bên trái và nhỏ
hơn giá trị tất cả các
node bên phải
Nút có giá trị nhỏ
nhất nằm ở trái nhất
của cây
Nút có giá trị lớn
nhất nằm ở phải nhất
của cây
7
7
3 36
1 6 15 40
234
4
Cây nhị phân cân bằng (AVL): Một cây nhị
phân được gọi là cây nhị phân cân bằng nếu
và chỉ nếu đối với mọi nút của cây thì
chiều cao của cây con bên trái và chiều
cao của cây con bên phải hơn kém nhau
nhiều nhất là 1 (Theo Adelson - Velski và
Landis).
5
B
A
C
E
F
I J
D
G H
B
A
C
E
F
I J
D
G H