Đề cương tổng hợp một số cấu trúc giữ liệu và giải thuật cơ bản

lOMoARcPSD|36442750 Mục lục 9.5
Lấy ra các phần tử trong stack ........................... 9 1
Tổ hợp ........................................................................ 3 10
Queue – ds móc nối đôi ......................................... 9 2
Tháp Hà Nội ............................................................... 3 10.1
Tạo mới một queue ......................................... 10 3
Quay lui hoán vị ......................................................... 3 10.2
Nếu queue rỗng trả về true ............................. 10 4
Hiển thị ngoặc đúng ................................................... 3 10.3
Thêm một phần tử vào queue ......................... 10 5
Xếp hậu ...................................................................... 4 10.4
Lấy ra một phần tử của queue ......................... 10 6
Danh sách móc nối đơn ............................................. 4 10.5
Lấy hết các phần tử trong queue ..................... 10 6.1
Xóa phần tử cuối ................................................ 5 11
Cây ....................................................................... 10 6.2
Xóa phần tử đầu ................................................ 5 11.1
Tạo mới một nút .............................................. 10 6.3
Chèn vào giữa .................................................... 5 11.2
Duyệt cây theo thứ tự trước ........................... 11 6.4
Chèn vào cuối ..................................................... 5 11.3
Duyệt cây theo thứ tự sau ............................... 11 6.5
Chèn vào đầu ..................................................... 5 11.4
Duyệt cây theo thứ tự giữa ............................. 11 6.6
Hiển thị danh sách ............................................. 6 11.5
Đếm số nút cây ................................................ 11 6.7
Tạo mới một nút ................................................ 6 11.6
Chiều sâu cây ................................................... 11 6.8
Đảo chiều danh sách .......................................... 6 11.7
Cây nhị phân đầy đủ ........................................ 12 6.9
Trộn 2 ds sx tăng dần thành 1 ds giảm dần ....... 6 11.7.1
Tạo cây nhị phân đầy đủ .......................... 12 6.10
Trộn 2 ds sx giảm dần thành 1 ds giảm dần ....... 7 11.7.2
Kiểm tra cây nhị phân đầy đủ .................. 12 7
Danh sách dùng mảng ................................................ 7 11.8
Cây nhị phân hoàn chỉnh ................................. 12 7.1
Tạo mới một nút ................................................ 7 11.8.1
Tạo cây nhị phân hoàn chỉnh ................... 12 7.2
Thêm nút mới .................................................... 8 11.8.2
Số nút của cây hoàn chỉnh ....................... 12 7.3
Xóa nút ............................................................... 8 11.9
Cây nhị phân cân bằng ..................................... 13 7.4
Locate ................................................................. 8 12
Kiểm tra cây nhị phân đầy đủ .............................. 13 7.5
Hiển thị ds .......................................................... 8 13
Phản xạ gương cây ............................................... 13 8
Stack – ds móc nối đơn .............................................. 8 14
Số lá chẵn của cây ................................................ 13 8.1
Tạo mới một stack ............................................. 8 15
Số nút có info lớn hơn k ....................................... 13 8.2
Ds rỗng trả về true ............................................. 9 16
Kiểm tra đẳng cấu hai cây .................................... 13 8.3
Push ................................................................... 9 17
Sắp xếp ................................................................. 13 8.4
Pop ..................................................................... 9 17.1
Hiển thị ds ........................................................ 13 8.5
Lấy ra các phần tử trong stack ........................... 9 17.2
Swap ................................................................ 13 9
Stack – mảng .............................................................. 9 17.3
SelectionSort .................................................... 14 9.1
Tạo mới một stack ............................................. 9 17.4
InsertionSort .................................................... 14 9.2
Nếu stack rỗng trả về true ................................. 9 17.5
BubleSort ......................................................... 14 9.3
Push ................................................................... 9 17.6
MergSort .......................................................... 14 9.4
Pop ..................................................................... 9 17.7
QuickSort ......................................................... 15 1
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 17.8
HeapSort .......................................................... 15 17.8.1
Max-heap ................................................. 15 17.8.2
Min-heap .................................................. 16 17.8.3
Khôi phục tính chất đống ......................... 16 17.8.4
Xây dựng đống ......................................... 16 17.8.5
Sắp xếp đống ............................................ 16 18
Tìm kiếm nhị phân ............................................... 16 18.1
Tìm kiếm nhị phân ........................................... 16 18.2
Cây nhị phân tìm kiếm (BST) ............................ 16 18.2.1
Thuật toán tìm kiếm (Search) .................. 17 18.2.2
Thuật toán bổ sung (Insertion) ................ 17 18.2.3
Thuật toán loại bỏ (delete) ...................... 17 18.3
Cây AVL ............................................................ 17 18.3.1
Cây con trái cao hơn cây con phải do cây
con trái của con trái ................................................. 18 18.3.2
Cây con phải cao hơn cây con trái do cây
con phải của con phải .............................................. 18 18.3.3
Cây con trái co hơn cây con phải do cây
con phải của con trái ................................................ 18 18.3.4
Cây con phải cao hơn cây con trái do cây
con trái của con phải ................................................ 19 2
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 1 Tổ hợp int j; int C(int n, int k){
for(j=1;j if ((k==0)||(k==n)) if(m[i]==a[j]) return 1; return 0; else return 1; return C(n-1,k-1)+C(n-1,k); } } void hienhoanvi(int k){ C(9, 5) = 126 int i; 2 Tháp Hà Nội for(i=1;i<=n;i++) { int solanchuyen = 0; if(UCV(i,k)==1) {
void thapHN(int n, char a, char b, char c){ a[k] = m[i]; if (n==1) if(k==n) Ghinhan();
printf("%d:Chuyen 1 dia tu %c sang %c\n",++solanchuyen,a,c); else hienhoanvi(k+1); else { } thapHN(n-1,a,c,b); } thapHN(1,a,b,c); } thapHN(n-1,b,a,c);
4 Hiển thị ngoặc đúng int n, count; } char a[20]; } int Ghinhan() { 3 Quay lui hoán vị int n, count; int i; int a[20];
count++; printf("%i. ",count); int m[5];
for (i=1; i<=n;i++) printf("%c ",a[i]); void Ghinhan() { printf("\n"); int i; }
count++; printf("%i. ",count); int UCV(char c, int k){
for (i=1; i<=n;i++) printf("%i ",a[i]); int t=0; printf("\n"); int i; }
for(i=1;iint UCV(int i, int k){ if(a[i]=='(') t++; 3
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 else t--; int i; if(t<0) return 0;
count++; printf("%i. ",count); }
for (i=1; i<=n;i++) printf("%i ",a[i]); if(c=='(') t++; printf("\n"); else t--; } if(kint abs(int x){ if(t<0) return 0; if(x<0) return -x; else return 1; return x; } } else if(k==n) { int UCV(int i, int k){ if(t!=0) return 0; int j; else return 1; for(j=1;j }
if((a[j]==i)||(abs(a[j]-i)==abs(j-k))) } return 0; void hienthingoacdung(int k){ } if(UCV('(',k)==1) { return 1; a[k] = '('; } if(k==n) Ghinhan(); void xephau(int k){ else hienthingoacdung(k+1); int i; } for(i=1;i<=8;i++) { if(UCV(')',k)==1) { if(UCV(i,k)==1) { a[k] = ')'; a[k] = i; if(k==n) Ghinhan(); if(k==n) Ghinhan(); else hienthingoacdung(k+1); else xephau(k+1); } } } } 5 Xếp hậu } int n, count;
6 Danh sách móc nối đơn int a[20]; typedef int elementtype; int Ghinhan() { typedef struct _newNodeType { 4
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 elementtype Inf;
NodeType *newNode = (NodeType *) malloc(sizeof(NodeType)); struct _newNodeType *Next; if(newNode == NULL) { } NodeType;
printf("Khong the cap phat bo nho\n");
6.1 Xóa phần tử cuối
NodeType *delete_Last(NodeType *First){ return; if(First==NULL) return NULL; } NodeType *t2 = First; newNode->Inf = datum; NodeType *t1 = NULL;
newNode->Next = pred->Next; if(t2->Next==NULL) { pred->Next = newNode; free(t2); return; return NULL; } } 6.4 Chèn vào cuối
void insertToLast(NodeType *head, elementtype datum) { while(t2->Next!=NULL) {
NodeType *newNode = (NodeType *) t1 = t2; malloc(sizeof(NodeType)); t2 = t2->Next; if(newNode == NULL) { }
printf("Khong the cap phat bo nho\n"); t1->Next = NULL; return NULL; free(t2); } return First; newNode->Inf = datum; } newNode->Next = NULL;
6.2 Xóa phần tử đầu while(head->Next != NULL)
NodeType *delete_Head(NodeType *First){ head = head->Next; if(First==NULL) return NULL; head->Next = newNode; NodeType *p = First; return; First = First->Next; } free(p); 6.5 Chèn vào đầu return First;
NodeType *insertToHead(NodeType *head, elementtype datum) { }
NodeType *newNode = (NodeType *) 6.3 Chèn vào giữa malloc(sizeof(NodeType));
void insertToMiddle(NodeType *pred, elementtype datum) { if(newNode == NULL) { 5
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
printf("Khong the cap phat bo nho\n"); NodeType *dsmoi = NULL; return NULL; NodeType *p = header; } while(p!=NULL) { newNode->Inf = datum;
dsmoi = Insert_ToHead(dsmoi,p->Inf); newNode->Next = head; p = p->Next; return newNode; } } return dsmoi;
6.6 Hiển thị danh sách }
void printList(NodeType *head) {
6.9 Trộn 2 ds sx tăng dần thành 1 ds giảm while(head != NULL) { dần
ListNode *sortInsert(ListNode *head1, ListNode *head2) {
printf("%d\t", head->Inf);
if(head1 == NULL || head2 == NULL) head = head->Next; return NULL; }
ListNode *head = NULL, *compare = NULL; printf("\n"); return; do { } compare = head; 6.7 Tạo mới một nút
NodeType *createNewNode(elementtype datum) {
if(head1->Inf > head2->Inf) {
NodeType *newNode = (NodeType *) head = head2; malloc(sizeof(NodeType)); head2 = head2->next; if(newNode == NULL) { head->next = compare;
printf("Khong the cap phat bo nho\n"); } else { return NULL; head = head1; } head1 = head1->next; newNode->Inf = datum; head->next = compare; newNode->Next = NULL; } return newNode;
} while(head1 != NULL && head2 != NULL); } while(head1 != NULL) {
6.8 Đảo chiều danh sách compare = head;
NodeType *daoChieuDS_pp1(NodeType *header){ head = head1;
if(header==NULL) return NULL; 6
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 head1 = head1->next; head2 = head2->next; head->next = compare;
insertNode = insertNode->next; }
insertNode->next = compare; while(head2 != NULL) { } else { compare = head; insertNode = compare; head = head2; compare = compare->next; head2 = head2->next; } head->next = compare;
}while(head2 != NULL && compare != NULL); } if(head2 != NULL) return head; insertNode->next = head2; } 6.10 return head1;
Trộn 2 ds sx giảm dần thành 1 ds giảm dần }
ListNode *sortInsert2(ListNode *head1, ListNode *head2) { 7 Danh sách dùng mảng # define maxlength 1000
if(head1 == NULL || head2 == NULL)
typedef int elementtype; /* elements are integers */ return NULL; typedef struct list_tag {
ListNode *compare = NULL, *insertNode = NULL;
elementtype elements [maxlength]; // khai báo mảng
if(head2->Inf > head1->Inf) { 1000 phần tử int last; compare = head1; } list_type; head1 = head2;
7.1 Tạo mới một nút head2 = head2->next; list_type *create() { head1->next = compare;
list_type* lp = (list_type*)malloc(sizeof(list_type)); } lp->last = -1; insertNode = head1; return lp; compare = head1->next; } int end (list_type *lp){ do { return (lp->last +1);
if(head2->Inf > compare->Inf) { } insertNode->next = head2; 7
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 7.2 Thêm nút mới
lp -> elements [q] = lp -> elements [q+1];
void insert (elementtype x , int p , list_type * lp){ } int v; // running position }
if (lp -> last >= maxlength - 1) { 7.4 Locate
printf("\n%s ","list is full");
int locate (elementtype x , list_type * lp){ return; int q; }
for (q = 0; q <= lp ->last; q++)
if ((p < 0) || (p > lp -> last + 1)) {
if (lp -> elements [q] == x)
printf("\n%s ","position does not exist"); return (q); return;
return (lp -> last + 1); /* if not found */ } } else { 7.5 Hiển thị ds
void hienthi(list_type *lp){ int q; int i;
for (q = lp -> last; q >= p; q--) if(lp==NULL) return;
lp -> elements [q+1] = lp -> elements [q];
printf("Cac ptu co trong danh sach: \n");
lp -> last = lp -> last +1 ; for(i=0;ilast+1;i++) lp -> elements[p] = x;
printf("%d ",lp->elements[i]); } printf("\n"); } } 7.3 Xóa nút
void deleteL(int p , list_type * lp){
8 Stack – ds móc nối đơn typedef int Item;
int q; /* running position */ typedef struct _StackNode {
if ((p > lp-> last) || (p < 0)) { Item item;
printf("\n%s ","position does not exist"); struct _StackNode *next; return; } StackNode; } typedef struct _Stack { else /* shift elements */ { StackNode *top; lp -> last --; } Stack; int q; 8.1
for (q = p; q <= lp ->last; q++)
Tạo mới một stack Stack *StackInit(){ 8
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Stack *s = (Stack*)malloc(sizeof(Stack)); static Item *s; if(s==NULL) return NULL; static int N; s->top = NULL;
9.1 Tạo mới một stack void STACKinit(int maxN){ return s;
s = (Item *) malloc(maxN*sizeof(Item)); } N = 0;
8.2 Ds rỗng trả về true int StackEmpty(Stack *s){ } return (s->top==NULL);
9.2 Nếu stack rỗng trả về true int STACKempty() { } return N==0; 8.3 Push
void StackPush(Stack *s, Item x){ } StackNode *newnode = 9.3 Push
(StackNode*)malloc(sizeof(StackNode)); void STACKpush(Item item) { if(newnode==NULL) return; s[N++] = item; newnode->item = x; }
newnode->next = s->top; 9.4 Pop Item STACKpop() { s->top = newnode; return s[--N]; } } 8.4 Pop Item StackPop(Stack *s){
9.5 Lấy ra các phần tử trong stack while(!STACKempty())
if(s->top == NULL) return NULL; printf("%d\n",STACKpop()); Item X = s->top->item; StackNode *t = s->top;
10 Queue – ds móc nối đôi typedef int Item;
s->top = s->top->next; typedef struct _QueueNode { free(t); Item item; return X; struct _QueueNode *next; } } QueueNode;
8.5 Lấy ra các phần tử trong stack typedef struct _Queue { while(!StackEmpty(st)) QueueNode *front; printf("%d\t",StackPop(st)); QueueNode *back; 9 Stack – mảng typedef int Item; } Queue; 9
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
10.1 Tạo mới một queue Item X; Queue *QueueInit() {
if(q->front==q->back) {
Queue *q = (Queue*)malloc(sizeof(Queue)); temp = q->front; if(q==NULL) return NULL; X = temp->item; q->front = NULL; free(temp); q->back = NULL; q->front = NULL; return q; q->back = NULL; } return X;
10.2 Nếu queue rỗng trả về true } int QueueEmpty(Queue *q) { else { return (q->front==NULL); temp = q->front; } X = temp->item;
10.3 Thêm một phần tử vào queue
void enqueue(Queue *q, Item x){
q->front = q->front->next; QueueNode *newnode = free(temp);
(QueueNode*)malloc(sizeof(QueueNode)); return X; if(newnode==NULL) return; } newnode->item = x; } newnode->next = NULL;
10.5 Lấy hết các phần tử trong queue
if((q->front==NULL)&&(q->back==NULL)) { while(!QueueEmpty(q)) { q->front = newnode; printf("%d\n",dequeue(q)); q->back = newnode; 11 Cây } typedef struct _Tnode{ else {
char word; // Dữ liệu cất giữ ở nút
q->back->next = newnode;
struct _Tnode *leftmost_child; q->back = newnode; struct _Tnode *right_sibling; } } treeNode; }
11.1 Tạo mới một nút
treeNode *maketreenode(char w){
10.4 Lấy ra một phần tử của queue Item dequeue(Queue *q){ treeNode *temp =
(treeNode*)malloc(sizeof(treeNode));
if(QueueEmpty(q)) return NULL; if(temp==NULL) return NULL; QueueNode *temp; 10
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
temp->leftmost_child = NULL; inOrder(p);
temp->right_sibling = NULL; printf("%c ",r->word); temp->word = w;
if(p!=NULL) p = p->right_sibling; return temp; while(p!=NULL) { } inOrder(p);
11.2 Duyệt cây theo thứ tự trước p = p->right_sibling; void preOrder(treeNode *r){ } if(r==NULL) } return;
11.5 Đếm số nút cây printf("%c ",r->word);
int CountNodes(treeNode *tree) {
treeNode *p = r->leftmost_child; if(tree==NULL) return 0; while(p!=NULL) { int sonut = 1; preOrder(p);
treeNode *p = tree->leftmost_child; p = p->right_sibling; while(p!=NULL) { } sonut += CountNodes(p); } p = p->right_sibling;
11.3 Duyệt cây theo thứ tự sau } void postOrder(treeNode *r){ return sonut; if(r==NULL) } return; 11.6 Chiều sâu cây
treeNode *p = r->leftmost_child; int depth(treeNode *tree){ while(p!=NULL) { if(tree==NULL) return 0; postOrder(p);
treeNode *p = tree->leftmost_child; p = p->right_sibling; int k,dosaumax = 0; } while(p!=NULL) { printf("%c ",r->word); k = depth(p); } if(k>dosaumax)
11.4 Duyệt cây theo thứ tự giữa dosaumax = k; void inOrder(treeNode *r) { p = p->right_sibling; if(r==NULL) return; }
treeNode *p = r->leftmost_child; 11
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 return dosaumax + 1;
int j = kiemtramotcaynhiphandaydu(tree->right); }
int hi = depth(tree->left);
11.7 Cây nhị phân đầy đủ
int hj = depth(tree->right);
Cây nhị phân đầy đủ là cây nhị phân:
if((i==1)&&(j==1)&&(hi==hj))
 Mỗi nút lá đều có cùng độ sâu  return 1;
Các nút trong có đúng hai con else return 0; }
11.8 Cây nhị phân hoàn chỉnh
Cây nhị phân hoàn chỉnh là cây nhị phân độ sâu n thỏa mãn: 
Là cây nhị phân đầy đủ nếu không tính đến các nút ở độ sâu n
11.7.1 Tạo cây nhị phân đầy đủ
 Tất cả các nút ở độ sâu n lệch sang trái nhất có
treeNode *taocaynhiphandaydu(int n, char X) thể được { if(n==0) return NULL;
treeNode *r = maketreenode(X);
treeNode *left = taocaynhiphandaydu(n-1,X);
treeNode *right = taocaynhiphandaydu(n-1,X); r->left = left;
11.8.1 Tạo cây nhị phân hoàn chỉnh r->right = right;
treeNode *taocaynhiphanhoanchinh(int n, char X) { return r; int k = somuccuacayhc(n); }
treeNode *r = taocaynhiphandaydu(k);
11.7.2 Kiểm tra cây nhị phân đầy đủ }
int kiemtramotcaynhiphandaydu(treeNode *tree)
11.8.2 Số nút của cây hoàn chỉnh { int somuccuacayhc(int n) { if(tree==NULL) return 0; int k=0;
if((tree->left==NULL)&&(tree->right==NULL)) while(power(2,k)-1<=n) return 1; k++;
int i = kiemtramotcaynhiphandaydu(tree->left); return k-1; 12
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 } return nodePrt;
11.9 Cây nhị phân cân bằng }
Cây nhị phân cân bằng là cây có chiều cao cây con trái và
14 Số lá chẵn của cây
chiều cao cây con phải của mọi nút chênh lệch nhau
Int EvenLeaf(treeNode *RootTree) { không quá 1 đơn vị If(RootTree == null) Return 0;
If(RootTree-left==null && RootTree->right ==null) { If(RootTree->key % 2) Return 0; Return 1; }
12 Kiểm tra cây nhị phân đầy đủ
Return EvenLeaf(RootTree->left) + EvenLeaf(RootTree-
int kiemtramotcaynhiphandaydu(treeNode *tree){ >right); if(tree==NULL) return 0; }
if((tree->left==NULL)&&(tree->right==NULL))
15 Số nút có info lớn hơn k return 1; Giống bài duyệt cây
int i = kiemtramotcaynhiphandaydu(tree->left);
16 Kiểm tra đẳng cấu hai cây
int j = kiemtramotcaynhiphandaydu(tree->right); 17 Sắp xếp
int hi = depth(tree->left);
int hj = depth(tree->right); 17.1 Hiển thị ds
void Print(int p[], int len) {
if((i==1)&&(j==1)&&(hi==hj)) int i; return 1; for(i = 0; i < len;) else return 0; } printf("%d\t", p[i++]);
13 Phản xạ gương cây printf("\n");
treeNode *mirror(treeNode *nodePrt) { } if (nodePrt == NULL) 17.2 Swap return NULL; void Swap(int *a, int *b) {
treeNode *tmp = mirror(nodePrt->left); int tmp = *a;
nodePrt->left = mirror(nodePrt->right); *a = *b; nodePrt->right = tmp; 13
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 *b = tmp; 17.5 BubleSort
void BubbleSort(int a[], int len) { } int i, j, tmp; 17.3 SelectionSort
void SelectionSort(int p[], int len) {
for(i = 0; i < len - 1; ++i) int i, j, jmin; for(j = i; j < len; ++j)
for(i = 0; i < len - 1; ++i) { if(a[i] > a[j]) { jmin = i; tmp = a[i]; for(j=i+1; j < len; ++ j) a[i] = a[j]; if(p[j] < p[jmin]) a[j] = tmp; jmin = j; } if(jmin != i) }
Swap(&p[jmin], &p[i]); 17.6 MergSort } } 17.4 InsertionSort
void InsertionSort(int a[], int len) { int i, j, tmp;
for(i = 0; i < len-1; ++i) { tmp = a[i]; j = i - 1;
while(j > 0 && tmp < a[j]) {
void MergeSort(int a[], int first, int last) { a[j+1] = a[j]; if(first < last) { --j; int mid = (first + last)/2; } MergeSort(a, first, mid); a[j+1] = tmp; MergeSort(a, mid+1, last); } Merge(a, first, mid, last); return; } else } return; 14
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 }
QuickSort(a, first, pivot - 1);
void Merge(int a[], int first, int mid, int last) { else
int tmpA[MAX_SIZE]; // mang phu
QuickSort(a, pivot + 1, last);
int first1 = first; int last1 = mid; }
int first2 = mid + 1; int last2 = last; return; int index = first1; }
for(; (first1 <= last1) && (first2 <= last2); ++index) {
int Partition(int a[], int first, int last) {
if(a[first1] < a[first2]) {
int i = first, j = last + 1, p = a[first]; tmpA[index] = a[first1]; while(i < j) { ++first1; ++i; } else {
while((i <= last) && (a[i] < p)) tmpA[index] = a[first2]; ++i; ++first2; --j; }
while((j >= first) && (a[j] > p)) } --j;
for(; first1 <= last1; ++first1, ++index) Swap(&a[i], &a[j]);
tmpA[index] = a[first1]; // sao not day con 1 }
for(; first2 <= last2; ++first2, ++index) Swap(&a[i], &a[j]);
tmpA[index] = a[first2]; // sao not day con 2
Swap(&a[j], &a[first]);
for(index = first; index <= last; ++index) return j;
a[index] = tmpA[index]; // sao tra mang ket qua } return; 17.8 HeapSort
Đống là cây nhị phân gần hoàn chỉnh có 2 tính chất: }
 Tính cấu trúc: tất cả các mức đều là đầy trừ mức 17.7 QuickSort
cuối cùng. Mức cuối được điền đầy từ trái sang
void QuickSort(int a[], int first, int last) { phải if(first < last) {
 Tính chất đống: với mỗi nút ta luôn có con ≥ hoặc ≤ cha.
int pivot = Partition(a, first, last); 17.8.1 Max-heap if(first < pivot)
Với mọi nút I ta luôn có A[parent(i)] ≥ A[ i] 15
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
17.8.4 Xây dựng đống
17.8.5 Sắp xếp đống 17.8.2 Min-heap
Với mọi nút I ta luôn có A[parent(i)] ≤ A[ i]
18 Tìm kiếm nhị phân
17.8.3 Khôi phục tính chất đống
18.1 Tìm kiếm nhị phân
Điều kiện để tìm kiếm nhị phân là:
 Ds phải được sắp xếp theo thứ tự không giảm
 Phải cho phép trực truy (tức là không áp dụng được với ds móc nối)
18.2 Cây nhị phân tìm kiếm (BST)
Cây nhị phân tìm kiếm là cây nhị phân:
 Left trỏ đến con trái
 Right trỏ đến con phải  Parent trỏ đến cha  Info
 Tính chất BST: mọi nút thuộc cây con trái có giá trị
nhỏ hơn cha. Mọi nút thuộc cây con phải có giá trị lớn hơn cha. 16
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
 Nếu nút cần xóa chỉ có con trái
 Nếu nút cần xóa chỉ có con phải
Duyệt cây theo thứ tự giữa sẽ được dãy sắp xếp
18.2.1 Thuật toán tìm kiếm (Search)
 Nếu khóa cần tìm nhỏ hơn khóa của nút hiện tại
thì tiếp tục tìm kiếm ở cây con trái.
 Nếu khóa cần tìm lớn hơn khóa của nút hiện tại
thì tiếp tục tim kiếm ở cây con phải.
 Nếu tìm thấy thì trả lại con trở đên nút chứa khóa
cần tìm, ngược lại trả về Null.
 Nếu nút cần xóa có hai con:
18.2.2 Thuật toán bổ sung (Insertion)
 Tạo nút mới chứa phần tử chèn
 Di chuyển trên cây để tìm cha của nút mới: so
sách khóa của phần tử cần chèn với khóa của nút
đang xét, nếu khóa của phần tử cần chèn lớn hơn
(nhỏ hơn) khóa của nút đang xét thì rẽ theo con
phải ( con trái) của nút đang xét. Nếu gặp Null thì
dừng, nút đang xét là cha cần tìm.
 Gắn nút mới vào cha vừa tìm được.
18.2.3 Thuật toán loại bỏ (delete)
 Nếu nút cần xóa là lá 18.3 Cây AVL
Là cây nhị phân tìm kiếm thỏa mãn tính chất AVL: chiều
cao của cây con trái và cây con phải của một gốc chỉ sai
khác nhau không quá 1 và cả cây con trái và cây con phải đều là cây AVL.
Có 4 trường hợp khôi phục tính cân bằng của cây: 17
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
18.3.1 Cây con trái cao hơn cây con phải do cây con Thực hiện cân bằng: trái của con trái Thực hiện cân bằng:
18.3.3 Cây con trái co hơn cây con phải do cây con phải của con trái
18.3.2 Cây con phải cao hơn cây con trái do cây con Thực hiện cân bằng:
phải của con phải 18
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
18.3.4 Cây con phải cao hơn cây con trái do cây con trái của con phải Thực hiện cân bằng: 19
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)