Bài giảng Cấu trúc dữ liệu 1 - Chương 5: Cây

(Node-Left-Right) - NLR
• Duyệt theo thứ tự giữa 
(Left- Node-Right) - LNR
• Duyệt theo thứ tự sau 
(Left-Right-Node) - LRN
5.2. Cây nhị phân
Duyệt cây nhị phân - NLR
voidNLR(TREE Root) 
{ 
if (Root != NULL)
{
;//Xử lý theo nhu cầu
NLR(Root->pLeft); 
NLR(Root->pRight); 
} 
}
5.2. Cây nhị phân
Duyệt cây nhị phân - NLR
-,/,x,+,3,1,3,+,-,9,5,2,+,x,3,-,7,4,6
(3 + 1)×3/(9 – 5 + 2) – (3×(7 – 4) + 6) = –13 5.2. Cây nhị phân
Duyệt cây nhị phân - LNR
void LNR(TREE Root) 
{ 
if (Root != NULL)
{ 
LNR(Root->Left);
; //Xử lý theo nhu cầu 
LNR(Root->Right);
} 
}
5.2. Cây nhị phân
Duyệt cây nhị phân - LNR
3,+,1,x,3,/,9,-,5,+,2,-,3,x,7,-,4,+,6
(3 + 1)×3/(9 – 5 + 2) – (3×(7 – 4) + 6) = –13 5.2. Cây nhị phân
Duyệt cây nhị phân - LRN
void LRN (TREE Root) 
{ 
if (Root != NULL)
{ 
LRN(Root->Left);
LRN(Root->Right);
; //Xử lý theo nhu cầu 
}
}
5.2. Cây nhị phân
Duyệt cây nhị phân - LRN
(3 + 1)×3/(9 – 5 + 2) – (3×(7 – 4) + 6) = –13
3,1,+,3,x,9,5,-,2,+,/,3,7,4,-,x,6,+,-
5.2. Cây nhị phân
• Hãy so sánh thời gian tìm kiếm cho ba 
loại cấu trúc dữ liệu: 
–Mảng
– Danh sách liên kết
– Cây nhị phân
5.3. Cây nhị phân tìm kiếm
• ðịnh nghĩa
• Các thao tác trên cây
– Duyệt cây
– Tìm một phần tử trên cây
– Thêm một phần tử vào cây
– Hủy một phần tử trên cây
– Tạo một cây nhị phân tìm kiếm
– Hủy toàn bộ cây nhị phân tìm kiếm
5.3. Cây nhị phân tìm kiếm
• Cây nhị phân tìm kiếm (CNPTK) là cây 
nhị phân trong ñó tại mỗi nút, khóa của 
nút ñang xét lớn hơn khóa của tất cả các 
nút thuộc cây con trái và nhỏ hơn khóa 
của tất cả các nút thuộc cây con phải 
• Nhờ ràng buộc về khóa trên CNPTK, việc 
tìm kiếm trở nên có ñịnh hướng. Hơn 
nữa, do cấu trúc cây việc tìm kiếm trở 
nên nhanh ñáng kể. Nếu số nút trên cây 
là N thì chi phí tìm kiếm trung bình chỉ
khoảng log2N 
ðịnh nghĩa Cây nhị phân tìm kiếm
5.3. Cây nhị phân tìm kiếm
Ví dụ về Cây nhị phân tìm kiếm
Dựng cây nhị phân
LNR: B C D F A G I H E
NLR: A C B F D H G I E
A
C H
B F G E
D I
5.3. Cây nhị phân tìm kiếm
• Thao tác duyệt cây trên cây nhị
phân tìm kiếm hoàn toàn giống 
như trên cây nhị phân. 
• Khi duyệt theo thứ tự giữa, 
trình tự các nút duyệt qua sẽ
cho ta một dãy các nút theo thứ
tự tăng dần của khóa. 
Thao tác – Duyệt cây
5.3. Cây nhị phân tìm kiếm
Thao tác – Tìm một phần tử trên cây
5.3. Cây nhị phân tìm kiếm
Thao tác – Tìm một phần tử trên cây
TNODE* SearchNode(TREE T, DataType X)
{
if(T)
{
if(T->Key == X)
return T;
if(XKey)
return SearchNode(T->pLeft, X);
else
return SearchNode(T->pRight, X);
}
return NULL;
}
ðệ quy
5.3. Cây nhị phân tìm kiếm
Thao tác – Tìm một phần tử trên cây
TNODE * searchNode(TREE Root, DataType x)
{
TNODE *p = Root;
while (p!= NULL) 
{
if(x == p->Key) 
return p;
else 
if(x Key)
p = p->pLeft;
else
p = p->pRight;
}
return NULL;
}
Sử dụng vòng lặp 
ñể tìm kiếm
5.3. Cây nhị phân tìm kiếm
Thao tác – Thêm một phần tử vào cây
• Việc thêm một phần tử X vào cây phải 
bảo ñảm ñiều kiện ràng buộc của 
CNPTK. 
• Ta có thể thêm vào nhiều chỗ khác 
nhau trên cây, nhưng nếu thêm vào 
một nút lá sẽ là tiện lợi nhất do ta có
thể thực hiên quá trình tương tự thao 
tác tìm kiếm. 
• Khi chấm dứt quá trình tìm kiếm cũng 
chính là lúc tìm ñược chỗ cần thêm. 
5.3. Cây nhị phân tìm kiếm
Thao tác – Thêm một phần tử vào cây
Lưu ý phần tử có khóa 55
Còn có 2 thành phần left,right
left==right==NULL (nút lá)
5.3. Cây nhị phân tìm kiếm
Thao tác – Thêm một phần tử vào cây
int insertNode(TREE &T, Data X)
{
if(T)
{
if(T->Key == X)
return 0; //ñã có
if(T->Key > X)
return insertNode(T->pLeft, X);
else
return insertNode(T->pRight, X);
} //Khi T==NULL thì thêm vào
T = new TNode;
if(T == NULL)
return -1; //thiếu bộ nhớ
T->Key = X;
T->pLeft =T->pRight = NULL;
return 1; //thêm vào thành công
}
5.3. Cây nhị phân tìm kiếm
Thao tác – Xóa một phần tử ra khỏi cây
• Có 3 trường hợp xảy ra
– X là nút lá. 
– X chỉ có 1 con (trái hoặc phải). 
– X có ñủ cả 2 con.
5.3. Cây nhị phân tìm kiếm
• X là nút lá: chỉ ñơn giản hủy X vì nó không móc 
nối ñến phần tử nào khác 
Thao tác – Xóa một phần tử ra khỏi cây
5.3. Cây nhị phân tìm kiếm
• X chỉ có 1 con (trái hoặc phải): trước khi hủy X ta 
móc nối cha của X với con duy nhất của nó
Thao tác – Xóa một phần tử ra khỏi cây
5.3. Cây nhị phân tìm kiếm
• X có ñủ cả 2 con: ta không thể hủy trực tiếp 
do X có ñủ 2 con ⇒ Ta sẽ hủy gián tiếp. 
Thay vì hủy X, ta sẽ tìm một phần tử thế
mạng Y. Phần tử này có tối ña một con. 
Thông tin lưu tại Y sẽ ñược chuyển lên lưu 
tại X. Sau ñó, nút bị hủy thật sự sẽ là Y 
giống như 2 trường hợp ñầu
• Vấn ñề là phải chọn Y sao cho khi lưu Y 
vào vị trí của X, cây vẫn là CNPTK. Có 2 
phần tử thỏa mãn yêu cầu: 
– Phần tử nhỏ nhất (trái nhất) trên cây con phải.
– Phần tử lớn nhất (phải nhất) trên cây con trái.
Thao tác – Xóa một phần tử ra khỏi cây
5.3. Cây nhị phân tìm kiếm
Thao tác – Xóa một phần tử ra khỏi cây
Có thể dùng 15 
ñể thế mạng
5.3. Cây nhị phân tìm kiếm
• Ta có thể tạo một cây nhị phân tìm kiếm 
bằng cách lặp lại quá trình thêm 1 phần 
tử vào một cây rỗng 
44,18,88,13,37,59,108,15,23,40,55,71
Thao tác – Tạo cây nhị phân tìm kiếm
5.3. Cây nhị phân tìm kiếm
• Việc toàn bộ cây 
có thể ñược thực 
hiện thông qua 
thao tác duyệt 
cây theo thứ tự
sau. Nghĩa là ta 
sẽ hủy cây con 
trái, cây con 
phải rồi mới hủy 
nút gốc.
void removeTree(TREE T)
{
if(T)
{
removeTree(T->pLeft);
removeTree(T->pRight);
delete(T);
}
}
Thao tác – Hủy toàn bộ cây
5.3. Cây nhị phân tìm kiếm
1. Khi nào thì cây thì cây suy 
biến thành danh sách liên kết?
2. ðể khắc phục ñiều này ta cần 
làm gì?
5.4. Cây nhị phân cân bằng
• Cây nhị phân cân bằng hoàn toàn
– ðịnh nghĩa
– ðánh giá
• Cây nhị phân cân bằng (AVL)
Adelson-Velskii và Landis (Nga - 1962)
– ðịnh nghĩa
– Chiều cao cây AVL
– Cấu trúc dữ liệu
– ðánh giá cây AVL
5.4. Cây nhị phân cân bằng
• ðịnh nghĩa: Cây cân bằng hoàn toàn là cây nhị
phân tìm kiếm mà tại mỗi nút của nó, số nút
của cây con trái chênh lệch không quá một so 
với số nút của cây con phải
Cây nhị phân tìm kiếm cân bằng hoàn toàn
Cây Cân Bằng Hoàn Toàn
Cây CCBHT thì h ~ log2n
5.4. Cây nhị phân cân bằng
• ðánh giá
– Một cây rất khó ñạt ñược trạng thái cân bằng 
hoàn toàn và cũng rất dễ mất cân bằng vì khi 
thêm hay hủy các nút trên cây có thể làm cây 
mất cân bằng (xác suất rất lớn), chi phí cân 
bằng lại cây lớn vì phải thao tác trên toàn bộ 
cây. 
– Trong trường hợp xấu nhất ta chỉ phải tìm 
qua log2n phần tử (n là số nút trên cây).
– Do CCBHT là một cấu trúc kém ổn ñịnh nên 
trong thực tế không thể sử dụng. Nhưng ưu 
ñiểm của nó lại rất quan trọng. Vì vậy, cần 
ñưa ra một CTDL khác có ñặc tính giống 
CCBHT nhưng ổn ñịnh hơn. 
Cây nhị phân tìm kiếm cân bằng hoàn toàn
5.4. Cây nhị phân cân bằng
• ðịnh nghĩa: Cây nhị phân tìm kiếm cân bằng là
cây mà tại mỗi nút của nó ñộ cao của cây con 
trái và của cây con phải chênh lệch không 
quá một. 
Cây nhị phân tìm kiếm cân bằng AVL
Cây AVL
5.4. Cây nhị phân cân bằng
Cây nhị phân tìm kiếm cân bằng AVL
5.4. Cây nhị phân cân bằng
• Chiều cao cây AVL
– Ta lại có: N(h-1) > N(h-2) nên: 
• N(h) > 2N(h-2)
• N(h) > 22N(h-4)
• …
• N(h) > 2iN(h-2i)
– Suy ra: N(h) > 2 (h-1)/2
– Hay h-1 < 2*log2(N(h)) 
tức là h < 2*log2(N(h)) + 1= 2*log2(n)+1
– Vậy cây AVL có chiều cao O(log2(n))
Cây nhị phân tìm kiếm cân bằng AVL
ðể h-2i=1 thì i=(h-1)/2
5.4. Cây nhị phân cân bằng
Cây nhị phân tìm kiếm cân bằng AVL
Cây AVL tối thiểu có chiều cao 4
5.4. Cây nhị phân cân bằng
struct AVLNode
{
char balFactor; 
Data key;
AVLNode* pLeft;
AVLNode* pRight;
};
typedef AVLNode *AVLTree;
• CSCB(p) = 0 
ðộ cao cây trái (p) = ðộ
cao cây phải (p)
• CSCB(p) = 1 
ðộ cao cây trái (p) < ðộ
cao cây phải (p)
• CSCB(p) =-1 
ðộ cao cây trái (p) > ðộ
cao cây phải (p)
Cấu trúc dữ liệu cho cây AVL
balFactor ==CSCB(p)
5.4. Cây nhị phân cân bằng
• ðánh giá
– Cây cân bằng là CTDL ổn ñịnh hơn hẳn 
CCBHT vì chỉ khi thêm hủy làm cây thay ñổi 
chiều cao các trường hợp mất cân bằng 
mới có khả năng xảy ra. 
– Cây AVL với chiều cao ñược khống chế sẽ
cho phép thực thi các thao tác tìm thêm 
hủy với chi phí O(log2(n)) và bảo ñảm 
không suy biến thành O(n). 
5.4. Cây nhị phân cân bằng
• Các trường hợp mất cân bằng
– Ta sẽ không khảo sát tính cân bằng của 1 
cây nhị phân bất kỳ mà chỉ quan tâm ñến 
các khả năng mất cân bằng xảy rakhi thêm 
hoặc hủy một nút trên cây AVL. 
– Như vậy, khi mất cân bằng, ñộ lệch chiều 
cao giữa 2 cây con sẽ là 2. Ta có 6 khả 
năng (chia làm 2 trường hợp).
Cây nhị phân tìm kiếm cân bằng AVL
5.4. Cây nhị phân cân bằng
• Trường hợp 1: cây T lệch về bên trái(có 3 khả 
năng) 
Cây nhị phân tìm kiếm cân bằng AVL
5.4. Cây nhị phân cân bằng
• Trường hợp 2: cây T lệch về bên phải(có 3 khả 
năng) 
Cây nhị phân tìm kiếm cân bằng AVL
5.4. Cây nhị phân cân bằng
• Hướng giải quyết của 2 trường hợp là tương tự
nhau nên ta chỉ giải quyết trường hợp 1
Cây nhị phân tìm kiếm cân bằng AVL
Quay ñơn Left - Left
5.4. Cây nhị phân cân bằng
Cây nhị phân tìm kiếm cân bằng AVL
Quay ñơn Left - Left
5.4. Cây nhị phân cân bằng
Cây nhị phân tìm kiếm cân bằng AVL
Quay kép Left - Right
Nội dung ôn thi
• Thực hành
– Thêm code vào các thuật toán ñể thực hiện 
một yêu cầu nào ñó
– Danh sách liên kết
• Tổ chức CTDL: phân số, ña thức 1 biến, quản lý 
sinh viên
• Sắp xếp theo một thứ tự nào ñó
Nội dung ôn thi
• Lý thuyết
– Thuật toán sắp xếp, tìm kiếm
• Tìm kiếm
• Thực hiện từng bước kết quả của thuật toán 
(HeapSort,MergeSort, …)
• ShakerSort có những cải tiến gì so với BubleSort
– Danh sách liên kết
• Lý do sử dụng CTDL ñộng
• Tổ chức dữ liệu cho một bài toán nào nào ñó -> nêu hướng 
giải quyết (từ ñiển, ña thức, …)
• Chuyển trung tố  hậu tố, ñịnh trị hậu tố
– Cây
• Dựng cây, Duyệt Cây
• Thêm, Xóa phần tử cho cây
• Hỏi cây