250 Bài tập kỹ thuật lập trình C - Dương Thiên Tứ

 printf( "Nhap khoa can tim: " ); 
 scanf( "%d", &x ); 
 if ( ( d = Find( t, x ) ) != NULL ) 
 printf( "[%d,%s]\n", d->key, d->value ); 
 else 
 printf( "Khong tim thay khoa\n" ); 
 return 0; 
} 
Cây AVL được Adelson - Velskii và Landis giới thiệu năm 1962. Cây AVL là một 
cây BST cân bằng 1 cấp (1-balanced BST), điều kiện cân bằng của cây là: 
x,1|))x(T(height))x(T(height| RL  
Trong đó: height(): trả về chiều cao của cây, TL(x): cây con bên trái node x, TR(x): 
cây con bên phải node x 
Nghĩa là chênh lệch chiều cao giữa cây con bên trái và cây con bên phải của một 
node x bất kỳ trong cây không được vượt quá 1. 
Cấu trúc dữ liệu của một node trong cây AVL cần thêm một “tác nhân cân bằng” 
(balancing factor) flag để kiểm tra cân bằng của cây: 
- ))x(T(height))x(T(height RL  : flag = LEFT (minh họa bằng dấu /) 
- ))x(T(height))x(T(height RL  : flag = EVEN (minh họa bằng dấu -) 
- ))x(T(height))x(T(height RL  : flag = RIGHT (minh họa bằng dấu \) 
Khi chèn một node mới vào cây AVL, ta có thể làm cây AVL mất cân bằng. Có 4 
trường hợp làm cây AVL mất cân bằng: 
- RR - cây con bên phải (R) có nhánh phải (R) dài 
- RL - cây con bên phải (R) có nhánh trái (L) dài 
- LL - cây con bên trái (L) có nhánh trái (L) dài 
- LR - cây con bên trái (L) có nhánh phải (R) dài 
Biến taller dùng trong hàm Insert() báo rằng cây đang “lệch” sau mỗi lần chèn 
node. Trong lần chèn node kế tiếp, khi nhận thấy lần chèn node trước đã làm cây 
“lệch”, cần xác định là lần chèn node hiện tại có làm cây mất cân bằng không (hoặc 
làm cây cân bằng trở lại). 
Sự mất cân bằng này liên quan đến 3 node: kể từ node gốc đi theo “hướng” nhánh 
gây mất cân bằng. Để cân bằng lại cây, người ta tái bố trí lại (trinode restructuring) 
sao cho 3 node này và các cây con liên quan vẫn giữ đúng thứ tự duyệt LNR (inoder, 
xem bài 222, trang 325). 
Các hình dưới trình bày cách tái bố trí lại cây, các con trỏ trong hình giúp dễ theo 
dõi các hàm quay cây: 
- Trường hợp RR: 
Thao tác tái bố trí gọi là “quay trái cây” (xem hàm RotateLeft()) có gốc là a. Chú ý 
thứ tự duyệt LNR (T1) a (T2) b (T3) c (T4) không thay đổi sau khi cân bằng cây. 
(c) Dương Thiên Tứ www.trainingwithexperts.com 
 340 
- Trường hợp RL: 
Thao tác tái bố trí thực hiện quay kép: “quay phải cây” con gốc b để đưa về trường 
hợp RR, sau đó “quay trái cây” gốc a để giải quyết trường hợp RR. Chú ý thứ tự duyệt 
LNR (T1) a (T2) c (T3) b (T4) không thay đổi sau khi cân bằng cây. 
- Trường hợp LL: đối xứng với trường hợp RR, tái bố trí bằng cách tương tự, gọi là 
“quay phải cây” (xem hàm RotateRight()). 
- Trường hợp LR: đối xứng với trường hợp RL, tái bố trí bằng cách tương tự, “quay 
trái cây” chuyển về LL, sau đó “quay phải cây” để cân bằng. 
Các trường hợp RR và RL giải quyết bằng hàm Rebalance_RIGHT(). 
Các trường hợp LL và LR giải quyết bằng hàm Rebalance_LEFT(). 
Bài 230: (trang 65) 
void Delete( NODEPTR* t, int d, int* shorter ) { 
 if ( d == ( *t )->pData->key ) { 
 if ( ( *t )->left && ( *t )->right ) { /* có hai cây con */ 
 NODEPTR p; 
 void* temp; 
 /* tìm node thay thế trước */ 
 for ( p = ( *t )->left; p->right; p = p->right ) { } 
 /* hoán chuyển dữ liệu node cần xóa với node thay thế trước */ 
 temp = ( *t )->pData; 
 ( *t )->pData = p->pData; 
 p->pData = temp; 
 /* gọi đệ quy xóa node thay thế (hiện mang khóa d) trong cây trái */ 
 Delete( &( *t )->left, d, shorter ); 
 /* cân bằng cây sau khi xóa node */ 
 if ( shorter ) 
 switch ( ( *t )->flag ) { 
 case RIGHT: /* xóa node nhánh phải: cây mất cân bằng */ 
 Rebalance_RIGHT( t ); 
 break; 
 case EVEN: /* xóa node nhánh phải: node gốc lệch phải */ 
t 
T2 
\ 
T3 
T1 
T4 
- 
T3 T4 
- 
T1 T2 
\
\ temp 
a 
c 
b 
b 
a c 
T4 
/ 
T2 
T1 
T3 
- 
T3 T4 
T1 T2 
\
\ 
a 
c 
b 
c 
a b 
T2 
\ 
T3 
T1 
T4 
\
\ 
a 
b 
c 
t 
temp 
temp2 
(c) Dương Thiên Tứ www.trainingwithexperts.com 
 341 
 ( *t )->flag = RIGHT; 
 *shorter = FALSE; 
 break; 
 case LEFT: /* xóa node nhánh phải: cây cân bằng trở lại */ 
 ( *t )->flag = EVEN; 
 *shorter = TRUE; 
 } 
 } else { /* trường hợp chỉ có một cây con, xóa node tại đây */ 
 NODEPTR dnode = *t; 
 *t = ( !( *t )->left ) ? ( *t )->right : ( *t )->left; 
 free( dnode->pData ); 
 free( dnode ); 
 *shorter = TRUE; 
 } 
 } else if ( d pData->key ) { /* xóa bên nhánh trái */ 
 Delete( &( *t )->left, d, shorter ); 
 /* cân bằng cây sau khi xóa node */ 
 if ( shorter ) 
 switch ( ( *t )->flag ) { 
 case RIGHT: 
 Rebalance_RIGHT( t ); 
 break; 
 case EVEN: 
 ( *t )->flag = RIGHT; 
 *shorter = FALSE; 
 break; 
 case LEFT: 
 ( *t )->flag = EVEN; 
 *shorter = TRUE; 
 } 
 } else { /* xóa bên nhánh phải */ 
 Delete( &( *t )->right, d, shorter ); 
 /* cân bằng cây sau khi xóa node */ 
 if ( shorter ) 
 switch ( ( *t )->flag ) { 
 case LEFT: 
 Rebalance_LEFT( t ); 
 break; 
 case EVEN: 
 ( *t )->flag = LEFT; 
 *shorter = FALSE; 
 break; 
 case RIGHT: 
 ( *t )->flag = EVEN; 
 *shorter = TRUE; 
 } 
 } 
} 
Áp dụng cách xóa node trong cây BST trình bày cuối bài tập 221 (trang 320). Kết 
quả node cần xóa được chuyển thành node thay thế chỉ có một cây con. 
Giống như biến taller trong hàm Insert(), biến shorter truyền trong hàm Delete() 
báo rằng cây đang “lệch” sau mỗi lần xóa node, dùng xác định việc xóa node có làm 
cây mất cân bằng không để tiến hành cân bằng lại cây sau khi xóa node.
(c) Dương Thiên Tứ www.trainingwithexperts.com 
 342 
TÀI LIỆU THAM KHẢO 
(Sắp xếp theo năm xuất bản) 
[1] Programming Language - C. ANSI X3.159-1989 aka ISO 9899-1990 - 
American National Standard for Information Systems. 
[2] Kernighan, Brian W. & Ritchie, Dennis M. - The C Programming Language 
- Second Edition - Prentice Hall, 1988. ISBN 0-131-10370-9 
[3] Kochan, Stephen G. & Wood, Patrick H. - Topics in C Programming - Third 
Edition - John Wiley & Sons, 1991. ISBN 0-471-53404-8 
[4] Schildt, Herbert - A Book on C: Programming in C - Fourth Edition - 
McGraw Hill/Osborne Media, 1995. ISBN 0-078-82101-0 (tiếng Anh). 
[5] Johnsonbaugh, R. & Kalin M. - Applications Programming in ANSI C - 
Third Edition - MacMillan, 1996. ISBN 0-023-61141-3 
[6] Summit, Steve & Lafferty, Deborah - C Programming FAQs: Frequently 
Asked Questions - Addison Wesley, 1996. ISBN 0-201-84519-9 
[7] Kelley, Al & Pohl, Ira - C: The Complete Reference - Third Edition - Addison 
Wesley, 1997. ISBN 0-078-82101-0 
[8] Cassgne, Bernage - Introduction au Language C (norme ISO/ANSI) - 
Université Joseph Fourier & CNRS, 1998 (tiếng Pháp). 
[9] P.S. Deshpande & O.G. Kakde - C & Data Structures - Charles River Media, 
2004. ISBN 1-584-50338-6 
[10] Ivor Horton - Beginning C - Fifth Edition - Apress, 2013. ISBN 978-1-4302-
4881-1 
[11] Jeri R. Hanly, Elliot B. Koffman - Problem Solving and Program Design in 
C - Seventh Edition - Pearson Education, Inc., 2013. ISBN 0-13-293649-6 
[12] Deitel, H.M. & Deitel, P.J. - C How to Program - Seventh Edition - Prentice 
Hall, 2013. ISBN 0-13-299044-X 
[13] Stephen Prata - C Primer Plus - Sixth Edition – Pearson Education, Inc., 2014. 
ISBN 0-321-92842-3 
[14] Tony Crawford, Peter Prinz - C: In a Nutshell - Second Edition - O'Reilly, 
2016. ISBN 978-1-491-90475-6 
(c) Dương Thiên Tứ www.trainingwithexperts.com 
 343 
Mục lục 
Lời nói đầu ................................................................................................................ 1 
Hướng dẫn sử dụng sách .......................................................................................... 2 
Phần bài tập 
 Khái niệm cơ bản - Toán tử - Cấu trúc lựa chọn - Cấu trúc lặp ............................ 3 
 Mảng .................................................................................................................... 17 
 Mảng nhiều chiều ................................................................................................ 25 
 Chuỗi ................................................................................................................... 35 
 Đệ quy ................................................................................................................. 41 
 Structure - Union - Bit Field ................................................................................ 46 
 Tập tin .................................................................................................................. 49 
 Các vấn đề khác ................................................................................................... 56 
 Cấu trúc dữ liệu ................................................................................................... 58 
Phần bài giải 
 Khái niệm cơ bản - Toán tử - Cấu trúc lựa chọn - Cấu trúc lặp .......................... 66 
 Mảng .................................................................................................................. 113 
 Mảng nhiều chiều .............................................................................................. 146 
 Chuỗi ................................................................................................................. 181 
 Đệ quy ............................................................................................................... 217 
 Structure - Union - Bit Field .............................................................................. 240 
 Tập tin ................................................................................................................ 252 
 Các vấn đề khác ................................................................................................. 279 
 Cấu trúc dữ liệu ................................................................................................. 296 
Tài liệu tham khảo ................................................................................................ 342