Bài tập Kỹ thuật lập trình

p->data, q->data ); } Xem lại giải thuật sắp xếp Selection Sort trên mảng: #define Swap( a, b ) { int t = a; a = b; b = t; } /* ... */ void selectsort( int a[], int n ) { int i, j; for ( i = 0; i < n - 1; ++i ) for ( j = i + 1; j < n; ++j ) if ( a[i] > a[j] ) Swap( a[i], a[j] ); } Thực hiện n - 1 đợt sắp xếp (vòng lặp ngoài, chỉ số i), mỗi đợt sắp xếp cho vị trí a[i]. Mảng được sắp xếp từ đầu đến cuối. Ðể sắp xếp đúng vị trí a[i], ta so sánh a[i] với các phần tử sau nó (từ j = i + 1 trở đi), chọn ra phần tử nhỏ nhất đặt vào vị trí a[i], bằng cách duyệt các phần tử sau a[i] (vòng lặp trong, chỉ số j), phần tử đang duyệt a[j] nào nhỏ hơn phần tử a[i] đang xét thì hoán đổi với a[i]. Danh sách liên kết có những thao tác tương tự như trên mảng: Mảng a Danh sách liên kết l Ý nghĩa với danh sách liên kết i = 0 p = l Chỉ đến đầu danh sách i next != NULL Chưa đến cuối danh sách i++ p = p->next Đến phần tử kế tiếp j = i + 1 q = p->next Phần tử này ngay sau phần tử kia a[i] > a[j] p->data > q->data So sánh hai trị Từ những nhận xét trên ta dễ dàng viết được giải thuật Selection Sort trên danh sách liên kết đơn chứa các trị nguyên. Bài 217: (trang 62) NODEPTR SwapTwoNode( NODEPTR p ) { NODEPTR t = p->next->next->next; p->next->next->next = p->next; (c) Dương Thiên Tứ www.trainingwithexperts.com 316 p->next = p->next->next; p->next->next->next = t; return p->next->next; } void Solution( NODEPTR* l, int x ) { NODEPTR p, g; /* chèn đầu ghost node, không cần lưu trị trong ghost node */ g = ( NODEPTR )malloc( sizeof( struct NODE ) ); g->next = *l; *l = g; for ( p = g; p->next && p->next->next; ) p = ( p->next->data == x ) ? SwapTwoNode( p ) : p->next; /* xóa đầu ghost node */ *l = ( *l )->next; free( g ); } /* gọi trong hàm main() */ printf( "Nhap k: " ); scanf( "%d", &k ); Solution( &l, k ); Đảo hai node kế tiếp nhau trong một danh sách liên kết được thực hiện như sau: Cần chú ý nguyên tắc: - Khi thay đổi một thông tin liên kết phải bảo đảm thông tin đó được lưu lại. Ví dụ: trước khi thay đổi p->next->next->next ta lưu thông tin này vào t. - Nếu không lưu thông tin liên kết lại trước khi thay đổi chúng thì phải bảo đảm là còn cách khác để nhận được thông tin này. Ví dụ: node a do p->next chỉ đến, ta thay p->next bằng p->next->next được vì sau đó vẫn xác định được node a do con trỏ p->next->next chỉ đến. - Một thông tin liên kết không còn ý nghĩa nữa thì có thể thay đổi mà không cần lưu lại. Ví dụ: ở bước cuối, thông tin liên kết đến node b đã được p->next lưu nên có thể thay đổi thông tin liên kết từ node a trỏ đi. Khi đảo hai node trong danh sách liên kết có các ngoại lệ sau: - Node a là node cuối, khi đó p->next->next = NULL, ta kiểm tra và không thực hiện b a p b a b a b a t = p->next->next->next t t p p->next->next->next = p->next p t p->next = p->next->next p->next->next->next = t p t (c) Dương Thiên Tứ www.trainingwithexperts.com 317 hoán chuyển nữa. - Node a là node đầu, ta chèn thêm node giả (ghost node) vào để đưa về trường hợp chung. Có thể nhận thấy quá trình tìm node để đảo không xét node giả này. - Danh sách rỗng (không kể node giả), khi đó p->next = NULL, ta kiểm tra và không thực hiện hoán chuyển nữa. Để đảo nhiều node chứa trị k yêu cầu ta cần chú ý khi đảo hai node, node chứa trị k chuyển về phía sau; nếu vòng lặp tiến đến node kế tiếp bằng p = p->next ta sẽ gặp lại node vừa đảo. Vì thế hàm SwapTwoNode() dùng đảo hai node được thiết kế trả về p->next->next để vượt qua node vừa đảo. Bài 218: (trang 62) void Swap( NODEPTR* a, NODEPTR* b ) { NODEPTR t = *a; *a = *b; *b = t; } void Solution( NODEPTR* l ) { NODEPTR p, p1, q, q1; for ( p1 = p = *l; p->next; p1 = p, p = p->next ) for ( q1 = q = p->next; q; q1 = q, q = q->next ) if ( p->data > q->data ) { Swap( &p->next, &q->next ); ( p == *l ) ? Swap( l, &q1->next ) : Swap( &p1->next, &q1->next ); Swap( &p, &q ); } } Vấn đề được giải quyết giống bài 216 (trang 315). Tuy nhiên, ta cần hoán chuyển hai node, không phải hoán chuyển trị chứa trong chúng. Trong danh sách liên kết, thông tin vị trí một node còn lưu trữ trong node truớc nó. Vì vậy một số thao tác trên một node cần đến con trỏ quản lý node trước node đó. Để có được con trỏ này người ta thường dùng kỹ thuật “hai con trỏ nối đuôi nhau”. for ( p1 = p = l; p->next; p1 = p, p = p->next ) { } p chạy từ đầu danh sách l đến cuối danh sách. Trước khi p di chuyển, dùng p1 để lưu lại vị trí cũ của p, vậy p1 luôn là con trỏ quản lý node đứng trước p. Chú ý nếu p chưa di chuyển, p1 và p chỉ chung một node. Khi hoán chuyển hai node, trước tiên hoán chuyển thông tin liên kết đến node sau trong nó, sau đó hoán chuyển thông tin liên kết đến nó chứa trong node ngay trước. Các bước cần thực hiện khi hoán chuyển hai node p (có node trước là p1) và q (có node trước là q1) trình bày trong hình trang sau: - Hoán chuyển thông tin liên kết chỉ đến node sau, chứa trong node đang xét. Swap( p->next, q->next ); - Hoán chuyển thông tin liên kết chỉ đến node đang xét, chứa trong node ngay trước node đang xét. Chú ý trường hợp node đang xét là node đầu. if ( p == l ) Swap( l, q1->next ); else Swap( p1->next, q1->next ); - Sau khi hoán chuyển vai trò của p và q đổi chỗ nhau nên cần hoán chuyển chúng trở lại: Swap( p, q ); (c) Dương Thiên Tứ www.trainingwithexperts.com 318 Hình dưới mô tả một vài trường hợp đặc biệt: hai node kế tiếp nhau (trái), một trong hai node là node đầu (phải). Bạn có thể kiểm chứng tính chính xác của cách hoán chuyển node trên. Bài 219: (trang 62) #define Swap( a, b ) { int t = a; a = b; b = t; } /* ... */ void Solution( NODEPTR l ) { NODEPTR p, q; for ( p = NULL; p != l->next; p = q ) for ( q = l; q->next != p; q = q->next ) if ( q->data > q->next->data ) Swap( q->data, q->next->data ); } Xem lại giải thuật sắp xếp Bubble Sort trên mảng: 1 l 3 2 p1 p q1 q 5 4 1 l 3 2 p1 p q1 q 5 4 1 l 3 2 p1 p q1 q 5 4 1 l 3 4 q p 5 2 1 l 4 3 2 p1 p q q1 1 l 4 3 2 p1 p q q1 1 l 4 3 2 p1 p q q1 1 l 4 2 3 q p 1 l 4 3 2 q q1 l 2 l 4 3 1 q p 1 l 4 3 2 q q1 p p1 p p1 l 1 4 3 2 q l p p1 (c) Dương Thiên Tứ www.trainingwithexperts.com 319 #define Swap( a, b ) { int t = a; a = b; b = t; } /* ... */ void bubblesort( int a[], int n ) { int i, j; for ( i = n - 1; i > 0; --i ) for ( j = 0; j < i; ++j ) if ( a[j] > a[j + 1] ) Swap( a[j], a[j+1] ); } Thực hiện n - 1 đợt sắp xếp (vòng lặp ngoài, chỉ số i), mỗi đợt sắp xếp cho vị trí a[i]. Mảng được sắp xếp từ cuối đến đầu. Trong mỗi đợt sắp xếp, ta so sánh các phần tử gần nhau, hoán đổi chúng cho đúng chiều sắp xếp. Chuỗi “so sánh - hoán đổi” liên tục này sẽ dần dần đẩy phần tử a[i] “nổi” dần lên đúng vị trí sắp xếp. Mảng được sắp xếp từ đầu đến cuối. Ta nhận thấy vòng lặp bên ngoài (i) đi ngược từ cuối mảng lên đầu. Thao tác này khó thực hiện được khi dùng danh sách liên kết đơn, chỉ có thể thực hiện trên danh sách liên kết đôi. Tuy nhiên, do một số đặc điểm của hai vòng lặp trên, ta vẫn có thể điều khiển được một con trỏ đi ngược từ cuối danh sách liên kết đơn lên đầu danh sách bằng một thủ thuật nhỏ sau: for ( p = NULL; p != l->next; p = q ) for ( q = l; q->next != p; q = q->next ) if ( q->data > q->next->data ) Swap( q->data, q->next->data ); Vòng lặp trong (j) dừng khi q->next chỉ đến con trỏ “chặn dưới” p (lần đầu gán p bằng NULL). Như vậy q chỉ đến node trước p; sau mỗi vòng lặp ngoài (i), ta đơn giản gán cho p trị chứa trong q, kết quả là con trỏ “chặn dưới” p di chuyển ngược lên đầu một node. Bài 220: (trang 62) void Solution( NODEPTR* l ) { NODEPTR t, t1, t2; NODEPTR p; if ( *l ) { /* list p có 1 phần tử "đã sắp xếp", là phần tử đầu list l */ p = *l; *l = ( *l )->next; p->next = NULL; while ( *l ) { /* xóa đầu l từng node, lưu node xóa vào t */ t = *l; *l = ( *l )->next; t->next = NULL; /* chèn t vào danh sách "đã sắp xếp" p */ t1 = NULL; t2 = p; while ( t2 && t2->data data ) { t1 = t2, t2 = t2->next; } if ( !t1 ) { t->next = p; p = t; } else { t->next = t1->next; t1->next = t; } } (c) Dương Thiên Tứ www.trainingwithexperts.com 320 /* cập nhật lại l với p "đã sắp xếp" */ *l = p; } } Giải pháp dựa trên giải thuật sắp xếp Insertion Sort trên mảng: void insertsort( int a[], int n ) { int v, i, j; for ( i = 1; i < n; ++i ) { v = a[i]; /* lưu a[i] vào v để dồn mảng */ j = i; /* dồn mảng từ a[i] ngược lên đến vị trí chèn */ while ( a[j - 1] > v ) { a[j] = a[j - 1]; j--; } a[j] = v; /* j là vị trí chèn, đưa v vào */ } } Thuật toán chia mảng thành hai phần; - Phần “đã sắp xếp”, nằm đầu mảng, được khởi tạo có một phần tử a[0]. - Phần còn lại là phần chưa sắp xếp. Từng phần tử trong phần này sẽ được chèn đúng vị trí vào phần “đã sắp xếp”. Ta thực hiện tương tự trên danh sách liên kết: - Tạo một danh sách “đã sắp xếp” do p quản lý, được khởi tạo có một phần tử là phần tử đầu danh sách l cần sắp xếp. - Xóa đầu dần danh sách l, từng node xóa chuyển cho t quản lý. Chèn t vào danh sách có thứ tự p sao cho vẫn bảo đảm thứ tự đó, xem bài 203 (trang 301). Bài 221: (trang 63) Gọi t là con trỏ chỉ đến node cần xóa. Ta sẽ xóa node này không phải thông qua t mà thông qua một con trỏ khác cũng chỉ đến node cần xóa, con trỏ d với d = t. Có ba trường hợp: - Node cần xóa không có cây con bên phải (t->right = NULL) - Node cần xóa không có cây con bên trái (t->left = NULL) - Node cần xóa có đủ các cây con bên trái và bên phải, tức node cần xóa là node trong. a) Node cần xóa không có cây con bên phải Vì node cần xóa đã được giữ bởi con trỏ d, ta đơn giản chỉ “vượt” qua node cần xóa xuống cây con bên trái: if ( t->right == NULL ) t = t->left; 18 12 t->left 6 7 4 10 15 8 d = t (c) Dương Thiên Tứ www.trainingwithexperts.com 321 Node cần xóa bây giờ đã tách khỏi cây và được quản lý bởi con trỏ d, có thể xóa dễ dàng: free( d ); b) Node cần xóa không có cây con bên trái Tương tự trường hợp trên, chỉ “vượt” qua node cần xóa xuống cây con bên phải: if ( t->left == NULL ) t = t->right; free( d ); c) Node cần xóa là node trong Khi xóa node t, node thay thế node t phải bảo đảm tính chất của cây BST, nghĩa là: phải có trị lớn hơn tất cả các trị trong các node của cây con bên trái node t, đồng thời phải có trị nhỏ hơn tất cả các trị trong các node của cây con bên phải node t. Vậy node thay thế node t phải là node cực phải của cây con bên trái node t (tức node lớn nhất trong cây con bên trái, gọi là node “thay thế trước”) hoặc node cực trái của cây con bên phải node t (tức node nhỏ nhất của cây con bên phải, gọi là node “thay thế sau”). Ta quy ước chọn node thay thế là node cực phải của cây con bên trái node t (node “thay thế trước”). Có hai cách xóa một node trong: - Cách thứ nhất, xóa bằng cách sao chép node. Tìm node “thay thế trước” là node phải nhất của cây con bên trái node t. Ta bắt đầu từ node gốc của cây con bên trái (node t->left, nghĩa là d = t->left), sau đó luôn đi về bên phải (d = d->right) cho đến khi không còn đi tiếp được, nghĩa là khi con trỏ d->right == NULL. Trong khi con trỏ d di chuyển, ta dùng con trỏ p nối đuôi con trỏ d, tức p luôn chỉ node cha của node đang xét (node đang xét do d chỉ). for ( p = t, d = t->left; d->right; p = d, d = d->right ) { } Kết thúc vòng lặp trên d sẽ chỉ node “thay thế trước” và p là cha của d. Sao chép chồng dữ liệu chứa trong node “thay thế trước” vào node cần xóa: 4 8 t->right 24 20 27 10 6 18 d = t 10 8 20 15 12 18 25 16 23 27 p d (c) Dương Thiên Tứ www.trainingwithexperts.com 322 t->data = d->data; Bây giờ có cây 2 node chứa dữ liệu giống nhau, ta sẽ xóa node “thay thế trước” vì node này hoặc là node lá, hoặc chỉ có một cây con bên trái nên dễ dàng xóa hơn. Node cha của node “thay thế trước” là p, lưu được do dùng kỹ thuật hai con trỏ nối đuôi ở bước trước. Cho p chỉ đến node gốc của cây bên trái node “thay thế trước”: p->right = d->left; Node “thay thế trước” bây giờ đã tách khỏi cây và quản lý bởi con trỏ d, ta xóa d: free( d ); Khi tìm node “thay thế trước”, có một trường hợp đặc biệt là node “thay thế trước” nằm ngay sau node cần xóa. Kết quả vòng lặp tìm node “thay thế trước” như sau: Trong trường hợp này p = t và d chính là p->left. Sau khi sao chép chồng dữ liệu chứa trong node “thay thế trước” vào node cần xóa: t->data = d->data; ta tách node “thay thế trước” ra khỏi cây bằng cách: p->left = d->left; 10 8 18 15 12 18 25 16 23 27 p d 10 8 18 15 12 18 25 16 23 27 p p->right cũng là d d->left 10 8 18 15 12 25 23 27 p = t 10 14 d (c) Dương Thiên Tứ www.trainingwithexperts.com 323 Node “thay thế trước” bây giờ đã tách khỏi cây và quản lý bởi con trỏ d, ta xóa d: free( d ); Tổng kết cách 1: void RemoveNodeByCopy( NODEPTR* t ) { NODEPTR p, d = *t; if ( !( *t )->left ) *t = ( *t )->right; else if ( !( *t )->right ) *t = ( *t )->left; else { for ( p = *t, d = ( *t )->left; d->right; p = d, d = d->right ) { } ( *t )->data = d->data; if ( p == *t ) p->left = d->left; else p->right = d->left; } free( d ); } - Cách thứ hai, xóa node bằng ghép cây (merge). Cách thứ hai để xóa node trong, gọn hơn cách trên, nhưng có một vài khác biệt khi tiến hành xóa node. Tìm node “thay thế trước” là node phải nhất của cây con bên trái node t, không cần dùng kỹ thuật hai con trỏ nối đuôi nhau. Ta bắt đầu từ node gốc của cây con bên trái (node t->left, nghĩa là p = t->left), sau đó luôn đi về bên phải (p = p->right) cho đến khi không còn đi tiếp được, nghĩa là khi con trỏ p->right == NULL. for ( p = t->left; p->right; p = p->right ) { } Kết thúc vòng lặp trên p sẽ chỉ node “thay thế trước”. Cây con bên phải node cần xóa sẽ được ghép vào bên phải node “thay thế trước” thành cây con bên phải node “thay thế trước”, chú ý t->right là con trỏ quản lý cây con bên phải của node t. p->right = t->right; p->left cũng là d d->left 10 8 15 15 12 25 23 27 p = t 10 14 10 8 20 15 12 18 25 16 23 27 (c) Dương Thiên Tứ www.trainingwithexperts.com 324 Như vậy, xem như node cần xóa không còn cây con bên phải (t->right vẫn tồn tại nhưng không còn ý nghĩa). Bạn có thể xóa dễ dàng bằng cách “vượt” qua node cần xóa xuống cây con bên trái: t = t->left; Node cần xóa bây giờ đã tách khỏi cây và quản lý bởi con trỏ d, có thể xóa dễ dàng: free( d ); Cách này tuy đơn giản hơn nhưng dễ làm cho cây mất cân bằng, gây ảnh hưởng đến hiệu suất tìm kiếm. Tổng kết cách 2: void RemoveNodeByMerge( NODEPTR* t ) { NODEPTR p, d = *t; if ( !( *t )->left ) *t = ( *t )->right; else if ( !( *t )->right ) *t = ( *t )->left; else { for ( p = ( *t )->left; p->right; p = p->right ) { } p->right = ( *t )->right; *t = ( *t )->left; } free( d ); } d) Xóa một node chứa trị chỉ định Trên cơ sở thao tác xóa một node ở trên, ta tiến hành xóa một node với trị chỉ định trong cây BST bằng cách đệ quy: 10 8 20 15 12 18 25 16 23 27 10 8 20 15 12 18 25 16 23 27 d = t t->left (c) Dương Thiên Tứ www.trainingwithexperts.com 325 - Nếu node đang xét chứa trị trùng với trị chỉ định thì xóa ngay node đó và dừng đệ quy. - Nếu node đang xét chứa trị nhỏ hơn trị chỉ định thì tiến hành xóa đệ quy node chứa trị chỉ định trong cây bên trái node đang xét. - Ngược lại, tiến hành xóa đệ quy node chứa trị chỉ định trong cây bên phải node đang xét. void Remove( NODEPTR* t, int x ) { if ( x == ( *t )->data ) { RemoveNode( t ); return; } ( x data ) ? Remove( &( *t )->left, x ) : Remove( &( *t )->right, x ); } /* dùng trong hàm main() */ Remove( &t, k ); Ta nhận thấy thao tác xóa một node (RemoveNode()) cách 1 tuy có ưu điểm hơn nhưng phải giải quyết trường hợp ngoại lệ và phải xác định node cha của node thay thế bằng kỹ thuật dùng hai con trỏ nối đuôi nhau. Nếu viết hàm RemoveNode() cách 1 ngay trong hàm đệ quy Remove(), cách 1 sẽ được thực hiện đơn giản như cách 2, xem chú thích trong bài: void Remove( NODEPTR* t, int x ) { if ( x == ( *t )->data ) { NODEPTR p, d = *t; if ( ( *t )->left && ( *t )->right ) { /* node có 2 con */ /* tìm node thay thế như cách 2, không cần tìm node cha của node thay thế */ for ( p = ( *t )->left; p->right; p = p->right ) { } /* hoán chuyển trị của node xóa và node thay thế */ int temp = ( *t )->data; ( *t )->data = p->data; p->data = temp; /* trị cần xóa đã "xuống" cây con bên trái */ /* gọi đệ quy với cây con bên trái để xóa nó */ Remove( &( *t )->left, x ); } else { *t = ( !( *t )->left ) ? ( *t )->right : ( *t )->left; free( d ); } return; } ( x data ) ? Remove( &( *t )->left, x ) : Remove( &( *t )->right, x ); } Mục tiêu của cách xóa node này là chuyển node cần xóa có hai cây con trái phải thành node xóa chỉ có một cây con trái hoặc phải. Việc xóa node giảm thiểu khả năng mất cân bằng của cây. Bài 222: (trang 63) void LNR( NODEPTR t ) { if ( t ) { LNR( t->left ); printf( "%d ", t->data ); (c) Dương Thiên Tứ www.trainingwithexperts.com 326 LNR( t->right ); } } void NLR( NODEPTR t ) { if ( t ) { printf( "%d ", t->data ); NLR( t->left ); NLR( t->right ); } } void LRN( NODEPTR t ) { if ( t ) { LRN( t->left ); LRN( t->right ); printf( "%d ", t->data ); } } Phương pháp mô tả sau là một trong những cách duyệt cây BST một cách thủ công, giúp kiểm tra nhanh các kết quả duyệt theo chiều sâu: - Đi theo một “đường bao” xung quanh các node cây nhị phân từ trái sang phải (nếu trong thứ tự duyệt L trước R). Khi di chuyển ta duyệt qua các node của cây 3 lần, tương ứng với ba cách duyệt cây. - Thứ tự xuất các node được xác định như sau (chú ý các mũi tên ): LNR: (inorder) xuất trị của node khi đi qua ngay “dưới” node. NLR: (preorder) xuất trị của node khi đi qua ngay “trước” (bên trái) node. LRN: (postorder) xuất trị của node khi đi qua ngay “sau” (bên phải) node. Các cách duyệt ngược lại (backward): RNL, NRL và RLN cũng tiến hành tương tự. LNR: 2 3 4 5 8 9 14 16 18 NLR: 9 3 2 5 4 8 16 14 18 LRN: 2 4 8 5 3 14 18 16 9 Ý nghĩa mỗi cách duyệt theo chiều sâu được trình bày trong bài 224 (trang 329). 9 3 16 2 5 14 18 4 8 End Start End Start 9 3 16 2 5 14 18 4 8 9 3 16 2 5 14 18 4 8 End Start (c) Dương Thiên Tứ www.trainingwithexperts.com 327 Bài 223: (trang 63) #include #include struct NODE { int data; struct NODE *left, *right; }; typedef struct NODE* NODEPTR; /* cấu trúc dữ liệu cho queue */ struct QNODE { NODEPTR data; /* dữ liệu của queue là một node của BST */ struct QNODE *next; }; typedef struct QNODE* QNODEPTR; typedef struct { QNODEPTR qdata; /* danh sách liên kết chứa các node của queue */ QNODEPTR front, rear; /* con trỏ quản lý đầu và cuối queue */ } QUEUE; /* chèn dữ liệu vào queue - chèn cuối nhờ con trỏ rear */ void InQueue( QUEUE* q, NODEPTR p ) { QNODEPTR h = ( QNODEPTR )malloc( sizeof( struct QNODE ) ); h->data = p; h->next = NULL; if ( ( *q ).rear ) ( *q ).rear->next = h; ( *q ).rear = h; if ( !( *q ).front ) ( *q ).front = h; } /* trả về dữ liệu xuất từ queue - xóa đầu */ NODEPTR OutQueue( QUEUE* q ) { NODEPTR t = ( *q ).front->data; QNODEPTR d = ( *q ).front; ( *q ).front = ( *q ).front->next; if ( !( *q ).front ) ( *q ).rear = NULL; free( d ); return t; } void Insert( NODEPTR* t, int x ) { if ( !*t ) { *t = ( NODEPTR )malloc( sizeof( struct NODE ) ); ( *t )->data = x; ( *t )->left = ( *t )->right = NULL; } else ( x data ) ? Insert( &( *t )->left, x ) : Insert( &( *t )->right, x ); } void InTree( NODEPTR* t ) { int x; (c) Dương Thiên Tứ www.trainingwithexperts.com 328 printf( "Nhap 0 de dung: " ); do { scanf( "%d", &x ); if ( x ) Insert( t, x ); } while ( x ); } void BFS( NODEPTR t ) { QUEUE q; q.front = q.rear = NULL; if ( t ) InQueue( &q, t ); while ( q.front ) { NODEPTR d = OutQueue( &q ); printf( "%d ", d->data ); if ( d->left ) InQueue( &q, d->left ); if ( d->right ) InQueue( &q, d->right ); } } int main() { NODEPTR t = NULL; InTree( &t ); printf( "BFS: " ); BFS( t ); putchar( '\n' ); return 0; } Duyệt theo chiều rộng cây BST là lần lượt duyệt từng mức (level-by-level) của cây, tại mỗi mức duyệt các node từ trái sang phải: BFS: 9 3 16 2 5 14 18 4 8 Khi duyệt một node ta đồng thời biết được thông tin liên kết đến hai node con, thông tin này được lưu trữ vào một cấu trúc dữ liệu bổ trợ (helper data structure) nào đó để xử lý sau. Như vậy cấu trúc dữ liệu bổ trợ đó phải đáp ứng: - Xử lý tuần tự. - Ta đặt node cha vào cấu trúc dữ liệu đó trước các node con. Sau đó node cha được xử lý trước các node con. Cấu trúc dữ liệu bổ trợ thích hợp là queue (hàng đợi), hoạt động theo nguyên tắc FIFO tuần tự, được xây dựng bằng danh sách liên kết đơn, với các thao tác: - InQueue(): chèn cuối một node vào queue, dữ liệu trong node của queue chính là một node của cây BST. - OutQueue(): xóa đầu một node của queue, trước khi xóa dữ liệu được lưu lại để trả về. Trong queue, thao tác nhập/xuất diễn ra ở hai đầu khác nhau của queue. 9 3 16 2 5 14 18 4 8 9 cấp 0 3 16 cấp 1 2 5 14 18 cấp 2 4 8 cấp 3 (c) Dương Thiên Tứ www.trainingwithexperts.com 329 Để thực hiện nhanh thao tác chèn cuối, ta xây dựng thêm cấu trúc QUEUE dùng quản lý queue, trong đó đưa thêm con trỏ rear nhằm hỗ trợ cho thao tác chèn cuối. Nếu dùng cấu trúc dữ liệu bổ trợ là stack, ta có kết quả như cách duyệt NRL. Một cách duyệt BFS khác, không dùng cấu trúc dữ liệu bổ trợ mà dùng đệ quy: #define Max( a, b ) ( ( a ) > ( b ) ? ( a ) : ( b ) ) /* ... */ void PrintLevel( NODEPTR t, int cLevel, int tLevel ) { if ( t ) if ( cLevel == tLevel ) printf( "%d ", t->data ); else { PrintLevel( t->left, cLevel + 1, tLevel ); PrintLevel( t->right, cLevel + 1, tLevel ); } } int MaxLevel( NODEPTR t ) { if ( !t ) return 0; return 1 + Max( MaxLevel( t->left ), MaxLevel( t->right ) ); } void BFS( NODEPTR t ) { int i; int maxLevel = MaxLevel( t ); for ( i = 0; i < maxLevel; ++i ) PrintLevel( t, 0, i ); } Ta dùng hai hàm đệ quy: - Hàm PrintLevel( t, cLevel, tLevel ), duyệt đệ quy cây t và in các node ở mức tLevel. cLevel là mức hiện hành, dùng xác định xem có đang duyệt mức tLevel hay không. Vì vậy khi bắt đầu duyệt, truyền tham số cLevel bằng 0 (mức 0). - Hàm MaxLevel( t ) trả về mức sâu nhất (chiều cao) của cây t, cộng 1. Bạn cũng có thể tìm chiều cao của cây trong khi chèn node để tạo cây, không nhất thiết dùng đến hàm này. Sau đó, hàm BFS() chỉ đơn giản chạy vòng lặp duyệt từ mức 0 đến mức sâu nhất. Tại mỗi mức, gọi hàm PrintLevel() để in các phần tử thuộc mức đó. Tuy nhiên, do cả hai hàm đệ quy trên đều hoạt động không hiệu quả nên phương pháp này không tối ưu. Ý nghĩa cách duyệt theo chiều rộng được trình bày trong bài 225 (trang 332). Bài 224: (trang 63) #include #include struct NODE { int data; struct NODE *left, *right; }; typedef struct NODE* NODEPTR; void Insert( NODEPTR* t, int x ) { if ( !*t ) { (c) Dương Thiên Tứ www.trainingwithexperts.com 330 *t = ( NODEPTR )malloc( sizeof( struct NODE ) ); ( *t )->data = x; ( *t )->left = ( *t )->right = NULL; } else ( x data ) ? Insert( &( ( *t )->left ), x ) : Insert( &( ( *t )->right ), x ); } void InTree( NODEPTR* t ) { int x; printf( "Nhap 0 de dung: " ); do { scanf( "%d", &x ); if ( x ) Insert( t, x ); } while ( x ); } void OutTree( NODEPTR t ) { if ( t ) { printf( "%d ", t->data ); OutTree( t->left ); OutTree( t->right ); } } void CopyTree( NODEPTR t, NODEPTR* t1 ) { if ( t ) { Insert( t1, t->data ); CopyTree( t->left, t1 ); CopyTree( t->right, t1 ); } } void SortTree( NODEPTR t ) { if ( t ) { SortTree( t->left ); printf( "%d ", t->data ); SortTree( t->right ); } } void RemoveTree( NODEPTR* t ) { if ( *t ) { RemoveTree( &( ( *t )->left ) ); RemoveTree( &( ( *t )->right ) ); printf( "%d ", ( *t )->data ); free( *t ); } } int main() { NODEPTR t, t1; t = t1 = NULL; InTree( &t ); printf( "\nCay goc : " ); OutTree( t ); (c) Dương Thiên Tứ www.trainingwithexperts.com 331 CopyTree( t, &t1 ); printf( "\nCay copy : " ); OutTree( t1 ); printf( "\nXuat tang: " ); SortTree( t ); printf( "\nXoa cay goc... " ); RemoveTree( &t ); if ( t ) printf( "\nCay goc rong\n" ); return 0; } Duyệt cây BST là lần lượt đi qua tất cả các node của cây và thực hiện một thao tác nào đó trên mỗi node. Tùy thao tác cần thực hiện, ta chọn cách duyệt cây thích hợp cho thao tác đó: - InOrder: vì trị các node chứa trong nhánh phải của cây BST lớn hơn trị các node chứa trong nhánh trái và node gốc chứa trị trung gian, ta dùng cách duyệt LNR để xuất trị chứa trong các node cây BST theo chiều tăng dần (L < N < R). Tương tự, cách duyệt RNL dùng xuất trị chứa trong các node cây BST theo chiều giảm dần (L > N > R). Cách duyệt này thật sự không ý nghĩa với cây tổng quát. - PreOrder: khi muốn tạo một cây BST mới sao chép từ cây gốc, ta duyệt từng node trên cây gốc và chèn trị đọc được vào cây sao chép. Để cây sao chép có cùng cấu trúc với cây gốc, phải bảo đảm thứ tự chèn node vào cây sao chép giống như ở cây gốc, tạo node gốc trước rồi mới tạo các node con. Cách duyệt NLR hoặc NRL đáp ứng được yêu cầu này. Do đặc điểm trên, cách duyệt này còn dùng khi muốn so sánh cấu trúc của hai cây BST: void CompareTree( NODEPTR t, NODEPTR t1, int* b ) { if ( t && t1 ) { if ( t->data != t1->data ) { *b = 0; return; } CompareTree( t->left, t1->left, b ); CompareTree( t->right, t1->right, b ); } } /* dùng trong hàm main() */ int b = 1; CompareTree( t, t2, &b ); if ( b ) printf( "\nCung cau truc cay\n" ); else printf( "\nKhac cau truc cay\n" ); Có thể dùng cách xuất sau để dễ dàng quan sát cấu trúc cây hơn: void OutTree( NODEPTR t, char label, int d ) { if ( t ) { OutTree( t->right, 'L', d + 1 ); printf( "%*c[%c%d]\n", 2 * d, ' ', label, t->data ); OutTree( t->left, 'R', d + 1 ); } } /* dùng trong hàm main() */ printf( "Cay goc:\n" ); OutTree( t, '*', 1 ); Kết quả xuất: (c) Dương Thiên Tứ www.trainingwithexperts.com 332 Nhap 0 de dung: 9 3 7 16 14 2 5 4 8 18 0  Cay goc: [L18] [L16] [R14] [*9] [L8] [L7] [R5] [R4] [R3] [R2] Cách duyệt PreOrder còn dùng khi muốn tìm một node trong cây BST. Các phương pháp duyệt đều duyệt qua các tất cả các node trong cây, nhưng phương pháp PreOrder xử lý node ngay từ lần đầu tiên gặp node. - PostOrder: Khi muốn xóa tất cả các node trong một nhánh cây hoặc cả cây BST, ta tiến hành xóa các node con (trái và phải) rồi mới xóa node cha của chúng. Vì vậy ta dùng cách duyệt LRN hoặc RLN cho thao tác này. Bài 225: (trang 63) void Solution( int n, NODEPTR t, int curlevel, int* sum ) { if ( t ) { if ( curlevel == n ) { printf( "%d ", t->data ); *sum += t->data; } else if ( curlevel < n ) { Solution( n, t->left, curlevel + 1, sum ); Solution( n, t->right, curlevel + 1, sum ); } } } /* dùng trong hàm main() */ s = 0; Solution( n, t, 0, &s ); printf( "\nTong = %d\n", s ); Ta duyệt đệ quy cây từ node gốc đến mức n yêu cầu, mức đang duyệt được xác định bởi curlevel được truyền như tham số. curlevel được khởi tạo mức 0 khi gọi hàm, khi đệ quy xuống nhánh trái hay phải curlevel tăng 1 đơn vị. Nếu curlevel bằng mức n yêu cầu thì xuất nội dung node lưu trữ. Để tính tổng các node thuộc mức n, ta truyền bằng con trỏ thêm một biến sum, những thay đổi của biến sum sẽ được lưu qua các lần gọi đệ quy. Cách trên dễ hiểu nhưng sum được truyền bằng con trỏ nên dễ nhầm lẫn. Một phương án khác: int Solution( int n, NODEPTR t, int curlevel ) { if ( t ) { if ( curlevel == n ) { printf( "%d ", t->data ); return t->data; } else if ( curlevel < n ) { return Solution( n, t->left, curlevel + 1 ) + Solution( n, t->right, curlevel + 1 ); (c) Dương Thiên Tứ www.trainingwithexperts.com 333 } } return 0; } Bài 226: (trang 63) int Solution( int x, NODEPTR t, int level ) { if ( !t ) return -1; if ( t->data == x ) return level; return ( x data ) ? Solution( x, t->left, level + 1 ) : Solution( x, t->right, level + 1 ); } /* dùng trong hàm main() */ n = Solution( x, t, 0 ); if ( n == -1 ) printf( "Khong tim thay\n" ); else printf( "Muc %d\n", n ); Ta tìm x trong cây t bằng cách duyệt cây, có hai trường hợp dừng: - Duyệt đến node lá (t = NULL) mà vẫn không tìm thấy, trả về -1 (mức không thể có trong cây). Chú ý, nếu chèn node chứa trị x vào, t = NULL chính là nơi chèn node. - Tìm thấy node (x = t->data) ta trả về mức level. Mức level khởi tạo bằng 0 (mức xuất phát) khi gọi hàm và sẽ tăng 1 đơn vị khi duyệt xuống cây con trái hoặc phải. Khi không gặp hai trường hợp trên, duyệt đệ quy xuống nhánh con trái hoặc phải tùy theo trị của x, chú ý tăng mức level. Bài 227: (trang 64) NODEPTR isMember( NODEPTR t, int x ) { if ( t ) { if ( x == t->data ) return t; return ( x data ) ? isMember( t->left, x ) : isMember( t->right, x ); } return NULL; } /* x, y phải chắc chắn thuộc cây, x < y */ NODEPTR isParent( NODEPTR t, int x, int y ) { if ( x == t->data || y == t->data || x data && y > t->data ) return t; return ( x data ) ? isParent( t->left, x, y ) : isParent( t->right, x, y ); } /* dùng trong hàm main() */ do { printf( "Nhap a, b: " ); scanf( "%d%d", &a, &b ); if ( a != b && isMember( t, a ) && isMember( t, b ) ) break; printf( "Nhap khong hop le...\n" ); } while ( 1 ); if ( a > b ) { int temp = a; a = b; b = temp; } printf( "Node cha: %d\n", isParent( t, a, b )->data ); (c) Dương Thiên Tứ www.trainingwithexperts.com 334 Ta sắp xếp trước a < b: giúp dễ dàng xác định được vị trí node còn lại khi xác định được một node a hoặc b. - Nếu 2 node chứa a và b nằm trên 2 cây con trái phải của node gốc, node gốc là node cha của chúng (TH1). - Nếu 2 node chứa a và b cùng nằm trong cây con bên trái hoặc bên phải của node gốc thì có hai trường hợp con: + Node cha là một trong hai node chứa a hoặc b (TH2). + Hai node nằm trên 2 nhánh của một cây con thuộc nhánh trái hoặc phải của node gốc, node cha là node gốc của cây con này (quy về TH1). Từ node gốc p, ta đệ quy xuống hai nhánh trái và phải cho đến khi xảy ra một trong các điều kiện dừng đệ quy TH1 hoặc TH2. Khi đó, trị trả về của hàm isParent() chính là node cha cần tìm. Để bảo đảm hàm isParent() có điểm dừng, trị a và b phải có trong cây. Ta dùng hàm isMember() để xác định điều kiện này: duyệt cây theo NLR (tốt nhất cho tìm node). Nếu tìm được node, trả về node cần tìm; nếu không, trả về NULL. Bài 228: (trang 64) void PathLeft( NODEPTR t, int x ) { if ( t ) { if ( x == t->data ) return; ( x data ) ? PathLeft( t->left, x ) : PathLeft( t->right, x ); printf( "%d ", t->data ); } } void PathRight( NODEPTR t, int x ) { if ( t ) { if ( x == t->data ) return; printf( "%d ", t->data ); ( x data ) ? PathRight( t->left, x ) : PathRight( t->right, x ); } } /* dùng trong hàm main() */ int main() { NODEPTR t, p; int a, b; t = NULL; InTree( &t ); do { printf( "Nhap a, b: " ); scanf( "%d%d", &a, &b ); if ( a != b && isMember( t, a ) && isMember( t, b ) ) break; printf( "Nhap khong hop le...\n" ); } while ( 1 ); if ( a > b ) { int temp = a; a = b; b = temp; } (c) Dương Thiên Tứ www.trainingwithexperts.com 335 p = isParent( t, a, b ); if ( p->data == a ) { PathRight( p, b ); printf( "%d", b ); } else if ( p->data == b ) { printf( "%d ", a ); PathLeft( p , a ); } else { printf( "%d ", a ); PathLeft( p , a ); PathRight( p->right, b ); printf( "%d", b ); } putchar( '\n' ); return 0; } Hàm xuất đường đi từ node gốc đến một node trong cây thực chất là duyệt cây để tìm node, tốt nhất là duyệt theo NLR; nhưng thêm thao tác xuất từng node đã duyệt trên đường đi tới node cần tìm. - Hàm PathRight( t, x ): xuất đường đi từ node gốc p đến node chứa trị x có trong cây con bên phải, node gốc chứa trị nhỏ hơn x. - Hàm PathLeft( t, x ): xuất đường đi từ node chứa trị x có trong cây con bên trái đến node gốc p chứa trị lớn hơn x. Vì ta duyệt đệ quy từ node gốc xuống nên để xuất đường đi theo thứ tự ngược lại, ta dùng đệ quy đầu. Đường đi không bao gồm node chứa x. Khi xét hai node chứa a và b, a < b và phải có mặt trong cây BST, ta gặp các trường hợp sau đây: - Node gốc đang xét p là node chứa a: vì a < b node chứa b nằm trong cây con bên phải node gốc p; gọi hàm PathRight( p, b ) để xuất đường đi từ node gốc p chứa a đến node chứa b. - Node gốc đang xét p là node chứa b: vì a < b node chứa a nằm trong cây con bên trái node gốc p; gọi hàm PathLeft( p, a ) để xuất đường đi từ node chứa a đến node gốc p chứa b. - Node gốc p không chứa a hoặc b: vì a < b, node a nằm trong cây con bên trái và node b nằm trong cây con bên phải cây này; gọi hàm PathLeft( p, a ) để xuất đường đi từ node a đến node gốc p, gọi tiếp hàm PathRight( p->right, b ) để xuất tiếp đường đi từ node phải của node gốc p đến node b. Xuất đường đi từ node phải của p do node gốc p đã xuất khi gọi hàm PathLeft( p, a ). Khi giải quyết các trường hợp trên, ta cần xác định node cha gần nhất của hai node chứa trị a và b; ta dùng hàm isParent() cho yêu cầu này, xem bài 227 (trang 333). Bài 229: (trang 64) #include #include #include #define FALSE 0 #define TRUE 1 enum eBALANCE { LEFT, EVEN, RIGHT }; struct DATA { (c) Dương Thiên Tứ www.trainingwithexperts.com 336 int key; char value[10]; }; struct NODE { enum eBALANCE flag; struct DATA* pData; struct NODE *left, *right; }; typedef struct NODE* NODEPTR; void RotateRight( NODEPTR* t ) { NODEPTR temp = ( *t )->left; ( *t )->left = temp->right; temp->right = *t; *t = temp; } void RotateLeft( NODEPTR* t ) { NODEPTR temp = ( *t )->right; ( *t )->right = temp->left; temp->left = *t; *t = temp; } void Rebalance_RIGHT( NODEPTR* t ) { NODEPTR temp2, temp = ( *t )->right; switch ( temp->flag ) { case RIGHT: /* RR - cây con bên phải (R) có nhánh phải (R) dài */ ( *t )->flag = EVEN; temp->flag = EVEN; RotateLeft( t ); break; case LEFT: /* RL - cây con bên phải (R) có nhánh trái (L) dài */ temp2 = temp->left; switch ( temp2->flag ) { case EVEN: ( *t )->flag = EVEN; temp->flag = EVEN; break; case LEFT: ( *t )->flag = EVEN; temp->flag = RIGHT; break; case RIGHT: ( *t )->flag = LEFT; temp->flag = EVEN; } temp2->flag = EVEN; RotateRight( &temp ); ( *t )->right = temp; RotateLeft( t ); } } void Rebalance_LEFT( NODEPTR* t ) { (c) Dương Thiên Tứ www.trainingwithexperts.com 337 NODEPTR temp2, temp = ( *t )->left; switch ( temp->flag ) { /* LL - cây con bên trái (R) có nhánh trái (R) dài */ case LEFT: ( *t )->flag = EVEN; temp->flag = EVEN; RotateRight( t ); break; /* LR - cây con bên trái (R) có nhánh phải (R) dài */ case RIGHT: temp2 = temp->right; switch ( temp2->flag ) { case EVEN: ( *t )->flag = EVEN; temp->flag = EVEN; break; case RIGHT: ( *t )->flag = EVEN; temp->flag = LEFT; break; case LEFT: ( *t )->flag = RIGHT; temp->flag = EVEN; } temp2->flag = EVEN; RotateLeft( &temp ); ( *t )->left = temp; RotateRight( t ); } } void Insert( NODEPTR* t, struct DATA* d, int* taller ) { /* chèn một node mới */ if ( *t == NULL ) { *t = ( NODEPTR )malloc( sizeof( struct NODE ) ); ( *t )->pData = d; ( *t )->flag = EVEN; ( *t )->left = ( *t )->right = NULL; *taller = TRUE; return; } /* trùng khóa */ if ( d->key == ( *t )->pData->key ) { *taller = 0; return; } /* chèn trái */ if ( d->key pData->key ) { Insert( &( *t )->left, d, taller ); if ( taller ) /* có khả năng làm mất cân bằng */ switch ( ( *t )->flag ) { case LEFT: /* node gốc thành //, cần cân bằng trái */ Rebalance_LEFT( t ); *taller = FALSE; break; case EVEN: /* node gốc lệch trái nhưng chưa mất cân bằng */ // \ \ // \ / // \ - - - - - / - - - \ temp temp temp t t t (c) Dương Thiên Tứ www.trainingwithexperts.com 338 ( *t )->flag = LEFT; *taller = TRUE; break; case RIGHT: /* thêm node chỉ làm cây cân bằng */ ( *t )->flag = EVEN; *taller = FALSE; break; } return; } /* chèn phải */ Insert( &( *t )->right, d, taller ); if ( *taller ) { /* có khả năng làm mất cân bằng */ switch ( ( *t )->flag ) { case LEFT: /* thêm node chỉ làm cây cân bằng */ ( *t )->flag = EVEN; *taller = FALSE; break; case EVEN: /* node gốc lệch phài nhưng chưa mất cân bằng */ ( *t )->flag = RIGHT; *taller = TRUE; break; case RIGHT: /* node gốc thành \\, cần cân bằng phải */ Rebalance_RIGHT( t ); *taller = FALSE; break; } } return; } void OutTree( NODEPTR t, int depth ) { int i; char b[3] = { '\\', '|', '/' }; if ( t == NULL ) return; OutTree( t->right, depth + 1 ); for ( i = 0; i < depth; ++i ) printf( " " ); printf( "(%d,%c)\n", t->pData->key, b[t->flag] ); OutTree( t->left, depth + 1 ); } struct DATA* Find( NODEPTR t, int key ) { for( ; t; ) { if ( t->pData->key == key ) return t->pData; t = ( t->pData->key > key ) ? t->left : t->right; } return NULL; } int main() { int i, taller, x; struct DATA* d; NODEPTR t = NULL; struct DATA data[6] = { { 11, "Cho" }, { 4, "Meo" }, { 12, "Heo" }, { 3, "Cop" }, { 9, "De" }, { 6, "Ran" } }; (c) Dương Thiên Tứ www.trainingwithexperts.com 339 for ( i = 0; i < 6; ++i ) { d = ( struct DATA* )malloc( sizeof( struct DATA ) ); d->key = data[i].key; strcpy( d->value, data[i].value ); Insert( &t, d, &taller ); OutTree( t, 0 ); printf( "----------\n" ); } 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