Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Cây (Tree) - Đỗ Ngọc Như Loan

Cây (Tree) 
GV: Đỗ Ngọc Như Loan 
Khái niệm 
Cây là một tập hữu hạn các nút (đỉnh) trong đó có một nút đặc biệt gọi là gốc (root) 
Giữa các nút có quan hệ phân cấp gọi là “quan hệ cha con ” và được biểu diễn bởi một cung (cạnh) từ cha đến con 
A 
X 
Y 
Z 
(Hình 1) 
(Hình 2) 
(Hình 3) 
(Hình 4) 
KHÁI NIỆM 
Cây được định nghĩa một cách đệ qui: 
Một nút là một cây, nút đó cũng là gốc của cây 
Nếu r là một nút và T1, T2, , Tk là các cây với x1, x2, , xk lần lượt là các gốc thì một cây mới T sẽ được tạo lập bằng cách cho r trở thành cha của các nút x1, x2, , xk 
Lúc này r là gốc còn T1, T2, , Tk là các cây con ( subtrees) của gốc (x1, x2, , xk là con của nút r) 
KHÁI NIỆM 
Qui ước cho phép tồn tại cây không có nút nào và gọi đó là cây rỗng (null tree ) 
Nút gốc không có cha, các nút không có con gọi là các nút lá (leaf node), các nút có ít nhất 1 con là các nút trong (internal node ) 
Số con của một nút x trong cây T gọi là bậc (degree) của x 
Độ dài đường đi (số cạnh) từ nút gốc r đến một nút x gọi là độ sâu (depth) của x trong T. Mức (level) của x = Độ sâu + 1. 
Độ sâu lớn nhất của các nút trong T gọi là chiều cao (height ) của T. Cây rỗng có chiều cao là -1. 
Ví dụ 
CÂY NHỊ PHÂN (BINARY TREE) 
Cây mà mỗi nút chỉ có tối đa hai con gọi là cây nhị phân 
Ví dụ: 
(Hình 1) 
(Hình 2) 
(Hình 3) 
(Hình 4) 
X 
Y 
Z 
Khái niệm 
Một cây được gọi là m-phân nếu số con nhiều nhất của một nút của cây là m. 
Một cây được gọi là m-phân đầy đủ nếu mọi nút trong có đúng m con. 
Một cây nhị phân là cân bằng nếu tại mọi nút của cây, độ cao của cây con trái và cây con phải chênh lệch nhau không quá 1. 
Nếu h là chiều cao của cây nhị phân cân bằng có n nút thì h 
X 
Y 
Z 
(Hình 1) 
(Hình 2) 
(Hình 3) 
(Hình 4) 
Biểu diễn cây nhị phân 
Mỗi nút x, (ngoài thông tin dữ liệu được biểu diễn như một khóa ), có hai con trỏ left và right chỉ đến con trái và con phải của nó trong cây nhị phân T 
Nếu left[x] = NULL thì x không có con trái 
Nếu right[x] = NULL thì x không có con phải 
Nút gốc của cây T được trỏ bởi root[T] 
Nếu root[T] = NULL thì cây T là rỗng 
Biểu diễn cây nhị phân 
Nếu mỗi nút của cây biểu diễn một đối tượng có khóa là một số nguyên , có thể định nghĩa CTDL cây nhị phân trong C++ như sau: 
typedef struct CELL *TREE; 
struct CELL { 
	int key; //trong thực tế có thêm nhiều dữ liệu khác 
	TREE left, right; 
}; 
TREE T; 
Duyệt cây nhị phân 
Có ba thứ tự duyệt cơ bản 
Duyệt theo trung thứ tự (inorder tree walk-LNR) 
Duyệt theo tiền thứ tự (preorder tree walk-NLR) 
Duyệt theo hậu thứ tự (postorder tree walk-LRN) 
Inorder tree walk 
void InorderTreeWalk(TREE x ) 
{ 
	if(x !=NULL) 
	{ 
	InorderTreeWalk(x- >left); 
	cout key)<<' '; //thăm (xử lý) nút x 
	InorderTreeWalk(x- >right); 
	} 
} 
Cây nhị phân tìm kiếm (Binary search tree - BST) 
Là mô hình dữ liệu có nhiều ứng dụng trong thực tế 
Khoá của các phần tử được lưu trữ thỏa mãn tính chất cây nhị phân tìm kiếm (binary search tree property) 
Nếu y là một nút trong cây con trái của nút x thì key[y]< key[x] 
Nếu y là một nút trong cây con phải của nút x thì key[y]> key[x ] 
Các thao tác trên bst 
Khởi tạo cây 
Các thao tác tìm kiếm 
Chèn một nút vào cây 
Xóa một núy trên cây 
treeinitialize 
void TreeInitialize(TREE &T) 
{ 
	T=NULL ; 
} 
Các thao tác tìm kiếm 
TreeSearch : Tìm một phần tử theo khoá cho trước 
TreeMinimum : Tìm phần tử có khoá nhỏ nhất 
TreeMaximum : Tìm phần tử có khoá lớn nhất 
treesearch 
Đầu vào là một pointer x chỉ đến gốc của cây nhị phân tìm kiếm và khoá k của phần tử cần tìm 
Thủ tục trả về pointer chỉ đến nút có khoá k hoặc NULL 
Dựa vào tính chất của cây nhị phân tìm kiếm để xác định nút nào phải tìm kế tiếp trong các con trái và phải của x 
Nếu k < key[x], tìm tiếp trong cây con trái 
Ngược lại, tìm tiếp trong cây con phải 
treesearch 
TREE TreeSearch(TREE x,int k) 
{ 
	if(x ==NULL||k==x->key) return x; 
	if(kkey) return TreeSearch(x->left,k); 
	else return TreeSearch(x->right,k); 
} 
TREEMINIMUM 
Đầu vào là một pointer x chỉ đến gốc của cây nhị phân tìm kiếm 
Thủ tục trả về pointer chỉ đến nút có khoá nhỏ nhất 
Dựa vào tính chất của cây nhị phân tìm kiếm, phần tử có khoá nhỏ nhất được tìm kiếm theo các pointer chỉ đến con trái bắt đầu từ gốc cho đến khi pointer này là NULL 
TREEMINIMUM 
TREE TreeMinimum(TREE x) 
{ 
	if(x !=NULL) 
	 	while(x- >left!=NULL) 
	 	x=x- >left; 
	return x; 
} 
TREEMAXIMUM 
Đầu vào là một pointer x chỉ đến gốc của cây nhị phân tìm kiếm 
Thủ tục trả về pointer chỉ đến nút có khoá lớn nhất 
Phần tử có khoá lớn nhất được tìm kiếm theo các pointer chỉ đến con phải bắt đầu từ gốc cho đến khi pointer này là NULL 
TREEMAXIMUM 
TREE TreeMaximum(TREE x) 
{ 
	if(x !=NULL) 
	 	while(x- >right!=NULL) 
	 	x=x- >right; 
	return x; 
} 
Độ phức tạp 
Các thao tác tìm kiếm trên cây nhị phân tìm kiếm có độ phức tạp là O(h), trong đó h là chiều cao của cây 
treeinsert 
Thủ tục TreeInsert(T, k) tìm một vị trí thích hợp để chèn nút có khóa k vào cây T 
Nếu T là rỗng, nút có khóa k được chèn sẽ là nút gốc của cây 
Ngược lại chèn nút có khóa k vào cây như là một nút con của một nút lá của cây con bên trái hoặc bên phải của cây T 
treeinsert 
Chèn một phần tử có khoá 13 vào cây, các nút được làm sáng chỉ đường đi từ gốc đến vị trí cần chèn . 
treeinsert 
void TreeInsert(TREE &T, int k) 
{ 
	if(T ==NULL) 
	{ 
	T=new(CELL ); T->key=k; 
	 	T- >left=NULL; T->right=NULL; 
	} 
	else if(kkey) TreeInsert(T->left, k); 
	else if(k>T->key) TreeInsert(T->right, k); 
} 
treedelete 
TreeDelete(T, k) tìm và xoá z có khóa k, xét ba trường hợp : 
Nếu z không có con, sửa con trỏ của cha z đến z thành NULL 
Nếu z chỉ có một con, loại bỏ z bằng một liên kết mới giữa cha và con của nó 
Nếu z có hai con, loại phần tử có khóa nhỏ nhất y trong cây con phải của z và thay thế khóa (dữ liệu) của z bởi khóa ( dữ liệu ) của y 
treedelete 
treedelete 
treedelete 
treedelete 
treedelete 
void TreeDelete(TREE &T, int k) 
{ 
	if(T !=NULL) 
	 if(kkey) TreeDelete(T->left,k); 
	 else if(k>T->key) TreeDelete(T->right,k); 
	 else if(T->right==NULL) T=T->left; 
	 else if(T->left==NULL) T=T->right; 
	 else T->key=DeleteMin(T->right); 
} 
deletemin 
int DeleteMin(TREE &T) 
{ 
	int min; 
	if(T- >left==NULL) 
	{ 
	min=T- >key; 
	T=T- >right; 
	return min; 
	} 
	else return DeleteMin(T->left); 
} 
Độ phức tạp 
Định Lý 1: Các thao tác chèn (TreeInsert) và xóa (TreeDelete ) thực hiện trong thời gian O(h) trên một cây nhị phân tìm kiếm độ cao h 
Độ cao của cây nhị phân tìm kiếm biến đổi thông qua các thao tác chèn và xoá các nút trên cây 
Thời gian thao tác là O(h), vì vậy khi cây suy biến và có chiều cao là n-1 (n là số nút trên cây) thì các thao tác này sẽ không còn hiệu quả 
Xác suất để xẩy ra sự suy biến khi chèn, xoá một cách ngẩu nhiên là rất nhỏ 
Độ phức tạp 
Định Lý 2: Độ cao trung bình của một cây nhị phân tìm kiếm được xây dựng ngẩu nhiên trên n khoá phân biệt là O(log 2 n ) 
Định Lý 3: Độ phức tạp trung bình của các thao tác tìm kiếm , chèn và xóa trên một cây nhị phân tìm kiếm n nút có khóa phân biệt là O(log 2 n ) 
Yêu cầu: Cho dãy số nguyên gồm n số đôi một khác nhau và số k . Hãy kiểm tra xem có giá trị k trong dãy không? 
Input: Dữ liệu vào từ file TREE1 .INP gồm 2 dòng: 
+ Dòng 1: Gồm 2 số nguyên n và k (n<=1000) 
+ Dòng 2 chứa dãy số nguyên n phần tử 
Output: Xuất ra file TREE1 .OUT , g ồm 1 dòng chứa YES nếu tìm được, NO nếu không tìm được. 
Ví dụ: 
TREE1. INP 
5 3 
5 7 1 3 4 
TREE1 .OUT 
YES 
Giải bài toán này bằng cách sử dụng CÂY NHỊ PHÂN TÌM KIẾM 
Yêu cầu: Cho dãy số nguyên gồm n số đôi một khác nhau và số k . Hãy xóa số k ra khỏi dãy và xuất ra kết quả dãy đã được sắp xếp theo thứ tự tăng dần. 
Input: Dữ liệu vào từ file TREE2 .INP gồm 2 dòng: 
+ Dòng 1: Gồm 2 số nguyên n và k (n<=1000) 
+ Dòng 2 chứa dãy số nguyên n phần tử 
Output: Xuất ra file TREE2 .OUT , g ồm 1 dòng chứa dãy số đã xóa k và được sắp xếp theo thứ tự tăng dần. 
Ví dụ: 
TREE2. INP 
5 3 
5 7 1 3 4 
TREE2 .OUT 
1 4 5 7 
Giải bài toán này bằng cách sử dụng CÂY NHỊ PHÂN TÌM KIẾM 
CÂY NHỊ PHÂN TÌM KiẾM CÂN BẰNG 
Một cây nhị phân được gọi là cân bằng hoàn toàn nếu tại mỗi nút, cây con trái và cây con phải của nó có số nút chênh lệch nhau không quá 1 
Một cây nhị phân được gọi là cân bằng nếu tại mỗi nút, cây con trái và cây con phải của nó có độ cao chênh lệch nhau không quá 1 
Chiều cao cây cân bằng n nút luôn luôn là 
Cây cân bằng còn được gọi là cây AVL 
ĐỊNH NGHĨA 
// các hằng số biểu diễn hệ số cân bằng 
#define LH -1 //Cây con trái cao hơn 
#define EH 0 //Hai cây con có chiều cao bằng nhau 
#define RH 1 //Cây con phải cao hơn 
typedef struct AVLNode *AVLTree; 
struct AVLNode { 
	int balFactor; // hệ số cân bằng 
	int key; 
	AVLTree pLeft, pRight; 
}; 
AVLTree T; 
Các trường hợp mất cân bằng 
Các trường hợp mất cân bằng 
Các trường hợp mất cân bằng 
Các trường hợp mất cân bằng 
Các trường hợp mất cân bằng 
Khi cây T mất cân bằng, chênh lệch độ cao các cây con của T là 2 
Cây T lệch bên trái (3 trường hợp) 
Cây T lệch bên phải (3 trường hợp) 
Cây lệch bên trái 
Cây lệch bên phải 
Cân bằng cây lệch bên trái 
T1 lệch phải, sử dụng phép quay left-right 
QUAY LEFT-LEFT 
void rotateLL(AVLTree &T) 
{ 
	AVLTree T1=T->pLeft; 
	T->pLeft=T1->pRight; 
	T1->pRight=T; 
	switch(T1->balFactor) { 
	case LH: T->balFactor=EH; T1->balFactor=EH; 	break; 
	case EH: T->balFactor=LH; T1->balFactor=RH; 	break; 
	} 
	T=T1; 
} 
QUAY RIGHT-RIGHT 
void rotateRR(AVLTree &T) 
{ 
	AVLTree T1=T->pRight; 
	T->pRight=T1->pLeft; 
	T1->pLeft=T; 
	switch(T1->balFactor) { 
	case RH: T->balFactor=EH; T1->balFactor=EH; 	break; 
	case EH: T->balFactor=RH; T1->balFactor=LH; 	break; 
	} 
	T=T1; 
} 
QUAY LEFT-RIGHT 
void rotateLR(AVLTree &T) 
{ 
	AVLTree T1=T->pLeft, T2=T1->pRight; 
	T->pLeft=T2->pRight; 
	T2->pRight=T; 
	T1->pRight=T2->pLeft; 
	T2->pLeft=T1; 
	switch(T2->balFactor) { 
	case LH: T->balFactor=RH; T1->balFactor=EH; break; 
	case EH: T->balFactor=EH; T1->balFactor=EH; break; 
	case RH: T->balFactor=EH; T1->balFactor=LH; break; 
	} 
	T2->balFactor=EH; 
	T=T2; 
} 
QUAY RIGHT-LEFT 
void rotateRl(AVLTree &T) 
{ 
	AVLTree T1=T->pRight, T2=T1->pLeft; 
	T->pRight=T2->pLeft; 
	T2->pLeft=T; 
	T1->pLeft=T2->pRight; 
	T2->pRight=T1; 
	switch(T2->balFactor) { 
	case RH: T->balFactor=LH; T1->balFactor=EH; break; 
	case EH: T->balFactor=EH; T1->balFactor=EH; break; 
	case LH: T->balFactor=EH; T1->balFactor=RH; break; 
	} 
	T2->balFactor=EH; 
	T=T2; 
} 
HÀM CÂN BẰNG KHI CÂY LỆCH TRÁI 
void balanceLeft(AVLTree &T) 
{ 
	AVLTree T1=T->pLeft; 
	switch(T1->balFactor) { 
	case LH: rotateLL(T); break; 
	case EH: rotateLL(T); break; 
	case RH: rotateLR(T); break; 
	} 
} 
HÀM CÂN BẰNG KHI CÂY LỆCH PHẢI 
void balanceRight(AVLTree &T) 
{ 
	AVLTree T1=T->pRight; 
	switch(T1->balFactor) { 
	case LH: rotateRL(T); break; 
	case EH: rotateRR(T); break; 
	case RH: rotateRR(T); break; 
	} 
} 
Chèn 1 phần tử vào cây AVL 
Tìm và chèn tương tự như trên cây nhị phân tìm kiếm 
Sau khi chèn phải cân bằng lại 
Thao tác insertNode trả về : 
	+ -1 : khi không đủ bộ nhớ, 
 + 0: gặp nút đã có 
 + 1: chèn thành công (chiều cao không tăng) 
 + 2: nếu chèn thành công và chiều cao tăng 
Chèn 1 phần tử vào cây AVL 
int insertNode(AVLTree &T, int x) 
{ 
	int res; 
	if(T) { if(T->key==x) return 0; 
	if(T->key>x){ 
	res= insertNode(T->pLeft, x); 
	if(res<2) return res; 
	switch(T->balFactor) { 
	case RH: T->balFactor=EH; return 1; 
	case EH: T->balFactor=LH; return 2; 
	case LH: balanceLeft(T); return 1; 
	} 
	} else 
	{ res= insertNode(T->pRight, x); 
	if(res<2) return res; 
	switch(T->balFactor) { 
	case LH: T->balFactor=EH; return 1; 
	case EH: T->balFactor=RH; return 2; 
	case RH: balanceRight(T); return 1; 
	} 
	} 
	} //kết thúc T khác rỗng 
	T=new(AVLNode); 
	if(T==NULL) return -1; //thiếu bộ nhớ 
	T->key=x; T-balFactor=EH; 
	T->Pleft=T->pRight=NULL; 
	return 2; //chiều cao tăng 
} 
XÓA 1 phần tử KHỎI cây AVL 
T ìm và xóa tương tự như trên cây nhị phân tìm kiếm 
Sau khi xóa phải cân bằng lại 
Thao tác delNode trả về 1, 0 khi xóa thành công hoặc không có x trong cây (chiều cao không giảm) 
Thao tác delNode trả về 2 nếu xóa thành công và chiều cao giảm 
Tham khảo chương trình (hàm delNode) trong sách CTDL> của Trần Hạnh Nhi và Dương Anh Đức 
Độ phức tạp 
Thao tác cân bằng tại một nút có độ phức tạp là O(1) 
Thao tác thêm và xóa có độ phức tạp là O(h) 
Nếu cây có n nút, độ phức tạp thêm và xóa là O(log 2 n) 
Biểu diễn cây đa phân 
Cơ chế biểu diễn cây nhị phân có thể mở rộng cho cây đa phân 
Nếu mỗi nút có tối đa k con thì có thể dùng k+1 biến là p (chỉ đến cha) và child1, child2, ..., childk (chỉ đến k con) 
Phương pháp này không hiệu quả (tốn nhiều bộ nhớ) và không sử dụng được nếu số con tối đa của một nút quá lớn 
Biểu diễn cây đa phân 
Sử dụng 3 biến p, left-child, right-sibling để lưu trữ các pointer chỉ đến cha, con trái trái nhất và anh, em bên phải của mỗi nút trong T 
root[T] là pointer chỉ đến gốc của T 
left-child[x] chỉ đến con trái nhất của x 
right-sibling[x] chỉ đến anh em trực tiếp bên phải của x 
Nếu x không có con left-child[x] = NIL 
Nếu x là con phải nhất thì right-sibling[x] = NIL 
Các biểu diễn khác của cây 
Có thể biểu diễn cây có gốc như một đồ thị có hướng 
Có thể biểu diễn cây có gốc mà không cần pointer chỉ đến cha của nó 
Ngoài ra có thể dùng một mảng một chiều để biểu diễn cây có gốc