Input: A sequence of $n$ numbers
(1)
\begin{align} a_1, a_2,\cdots, a_n \end{align}
Output: A permutation (reordering) $a^\prime_1, a^\prime_2,\cdots, a^\prime_n$ of the input sequence such that
(2)
\begin{align} a^\prime_1 \le a^\prime_2 \le \cdots \le a^\prime_n \end{align}
The numbers that we wish to sort are also known as the keys.
Insertion Sorting Algorithm
The following pseudocode presents the algorithm for Insertion Sort algorithm:
INSERTION − SORT(n, A)
1) for j ← 2 to n
2) key ← A[j]
3) :->Insert A[j] into the sorted sequence A[1..j − 1]
4) i ← j − 1
5) while i > 0 and A[i] > key
6) A[i + 1] ← A[i]
7) i ← i − 1
8) A[i + 1] ← key
In the following, an C++ implementation of the Insertion Sort algorithm is shown.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
void selectionSort(int n, int s[]);
int main(int argc, char** argv) {
int n = 10;
int s[n];
s[0]=0;
s[1]=10;
s[2]=8;
s[3]=9;
s[4]=4;
s[5]=1;
s[6]=3;
s[7]=2;
s[8]=6;
s[9]=11;
cout << "Before sorting:" << endl;
for (int i=0; i < n; i++) {
cout << i<< " " << s[i] << endl;
}
selectionSort(n,s);
exit(0);
return 0;
}
void selectionSort(int n, int s[])
{
int i, key;
for (int j = 1; j < n; j++)
{
key = s[j];
i = j-1;
while ( i >= 0 && s[i] > key)
{
s[i+1] = s[i];
i--;
cout << "Running the loop" << endl;
}
s[i+1] = key;
}
cout << "After sorting:" << endl;
for (int i=0; i < n; i++) {
cout << i<< " " << s[i] << endl;
}
}
The following code, in C/C++, can be used to sort using the Insertion-Sort algorithm a randomly given array of $n$ elements and to measure the elapsed CPU time (in seconds).
#include <sys/time.h> //or #include <time.h> depending on the compiler
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int timeval_subtract(struct timeval *result, struct timeval *t2, struct timeval *t1)
{
long int diff = (t2->tv_usec + 1000000 * t2->tv_sec) - (t1->tv_usec + 1000000 * t1->tv_sec);
result->tv_sec = diff / 1000000;
result->tv_usec = diff % 1000000;
return (diff<0);
}
void timeval_print(struct timeval *tv)
{
char buffer[30];
time_t curtime;
printf("%ld.%06ld", tv->tv_sec, tv->tv_usec);
curtime = tv->tv_sec;
strftime(buffer, 30, "%m-%d-%Y %T", localtime(&curtime));
printf(" = %s.%06ld\n", buffer, tv->tv_usec);
}
void InsertionSort(unsigned *a, int n)
{
int k;
for (k = 1; k < n; ++k) {
int key = a[k];
int i = k - 1;
while ((i >= 0) && (key < a[i])) {
a[i + 1] = a[i];
--i;
}
a[i + 1] = key;
}
}
int main(int argc, char *argv[])
{
int* arrayList;
int i;
struct timeval tvBegin, tvEnd, tvDiff;
int size = atoi(argv[1]);
arrayList = malloc(sizeof(int)*size);
srand(time(NULL));
for(i=0; i<size; i++) {
arrayList[i] = rand() % size;
}
puts("Before sorting");
for(i = 0; i < size; i++)
printf("%5d\n", arrayList[i]);
gettimeofday(&tvBegin, NULL);
timeval_print(&tvBegin);
InsertionSort(arrayList, size);
gettimeofday(&tvEnd, NULL);
timeval_print(&tvEnd);
printf("Array list after sorting \n");
for (i=0; i < size; ++i) {
printf("%5d %10d\n", i, arrayList[i]);
}
timeval_subtract(&tvDiff, &tvEnd, &tvBegin);
printf("%ld.%06ld\n", tvDiff.tv_sec, tvDiff.tv_usec);
return 0;
}
Merge Sorting Algorithm
Pseudocode for the merge sorting algorithm is given in the following:
MERGE − SORT(A, p,r)
1 if p < r
2 then q ←floor((p + r)/2)
3 MERGE − SORT(A, p, q)
4 MERGE − SORT(A, q + 1,r)
5 MERGE(A, p, q,r)
Initial call: MERGE − SORT(A, 1, n).
In the following, a C++ code for implementation of Merge Sorting algorithm is presented.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int h,i,j,b[50],k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++) a[k]=b[k];
}
int main()
{
int num,i;
cout<<"********************************************************************************"<<endl;
cout<<" MERGE SORT PROGRAM " <<endl;
cout<<"******************************************************************* *************"<<endl;
cout << endl << endl;
cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort [THEN PRESS ENTER]:"<<endl;
cin>>num;
cout<<endl;
cout<<"Now, Please Enter the ( "<< num <<" ) numbers (ELEMENTS) [THEN PRESS ENTER]:"<<endl;
for(i=1;i<=num;i++)
{
cin>>a[i] ;
}
merge_sort(1,num);
cout<<endl;
cout<<"So, the sorted list (using MERGE SORT) will be :"<<endl;
cout<<endl<<endl;
for(i=1;i<=num;i++)
cout<<a[i]<<" ";
cout<<endl<<endl<<endl<<endl;
return(0);
}
The following code can be used to estimate the elapsed CPU time of the Merge Sorting algorithm.
#include <sys/time.h> //Or, #include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int* a;
int* temp;
int timeval_subtract(struct timeval *result, struct timeval *t2, struct timeval *t1)
{
long int diff = (t2->tv_usec + 1000000 * t2->tv_sec) - (t1->tv_usec + 1000000 * t1->tv_sec);
result->tv_sec = diff / 1000000;
result->tv_usec = diff % 1000000;
return (diff<0);
}
void timeval_print(struct timeval *tv)
{
char buffer[30];
time_t curtime;
printf("%ld.%06ld", tv->tv_sec, tv->tv_usec);
curtime = tv->tv_sec;
strftime(buffer, 30, "%m-%d-%Y %T", localtime(&curtime));
printf(" = %s.%06ld\n", buffer, tv->tv_usec);
}
void merge(int, int, int);
void merge_sort(int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int h,i,j,k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
temp[i]=a[h];
h++;
}
else
{
temp[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
temp[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
temp[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++) a[k]=temp[k];
}
int main(int argc, char* argv[])
{
int i;
struct timeval tvBegin, tvEnd, tvDiff;
int size = atoi(argv[1]);
a = malloc(sizeof(int)*size);
temp = malloc(sizeof(int)*size);
srand(time(NULL));
for(i=0; i<size; i++) {
a[i] = rand() % size;
}
puts("Before sorting");
for(i = 0; i < size; i++)
printf("%5d\n", a[i]);
gettimeofday(&tvBegin, NULL);
timeval_print(&tvBegin);
merge_sort(1,size);
gettimeofday(&tvEnd, NULL);
timeval_print(&tvEnd);
puts("After sorting");
for(i=0;i < size; i++)
printf("%5d\n", a[i]);
timeval_subtract(&tvDiff, &tvEnd, &tvBegin);
printf("%ld.%06ld\n", tvDiff.tv_sec, tvDiff.tv_usec);
return(0);
}
Figure below shows the elapsed CPU time as a function of the length of sequence $n$:
(3)
\begin{align} T(n) = \Theta(n\log n) \end{align}
Indicator Random Variables
Consider the Flipping a Coin Experiment - Expected number of Heads out of $n$ trials is $n/2$.
//
//
//
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include "Random.hpp"
#include "defs.hpp"
#include "Maths.hpp"
using namespace std;
using namespace rangen;
using namespace maths;
int const n=100;
double const p=0.5;
int main()
{
cout << "Flipping a Coin Experiment - Expected number of Heads" << endl;
cout << "Modified by Hiqmet Kamberaj on 4/7/23." << endl;
cout << "Copyright (c) 2023 Hiqmet Kamberaj. All rights reserved." << endl;
int n_h = 0;
int n_h_expected = int(n/2);
initrand();
for (int i = 0; i < n; i++) {
if (drand(0.0,1.0) < p)
n_h++;
}
cout << "................................................................................" << endl;
cout << "Number of Heads " << n_h << " out of " << n << " trials" << endl;
cout << "Expected number of heads " << n_h_expected << endl;
cout << "Deviation from Expected number of heads " << abs(n_h_expected - n_h) << endl;
return(0);
}
Randomized Hiring Algorithms
The algorithm is summarized as the following:
- Assumes that the candidates are numbered 1 to $n$ and that after interviewing each candidate;
- We can also determine (based on some criteria) if the candidate is better than the current office assistant;
- Uses a dummy candidate 0 that is worse than all others, so that the first candidate is always hired.
The pseudocode is given in the following:
HIRE-ASSISTANT(n)
1 best ← 0 B candidate 0 is a least-qualified dummy candidate
2 for i ← 1 to n
3 do interview candidate i
4 if candidate i is better than candidate best
5 then best ← i
6 hire candidate i
A pseudocode for randomized hiring algorithm is given below:
RANDOMIZED − HIRE − ASSISTANT(n)
randomly permute the list of candidates
HIRE − ASSISTANT(n)
In the following, an C++ code is given, which implements different algorithms for randomly permuting the list of candidates.
//
//
//
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include "Random.hpp"
#include "defs.hpp"
#include "Maths.hpp"
using namespace std;
using namespace rangen;
using namespace maths;
int const n=500;
int temp;
double prob(int i);
void selectionSort(int n, int s[]);
int myIrand(int min, int max);
#define SWAP(a,b) {temp=(a);(a)=(b);(b)=temp;}
int main(int argc, const char * argv[]) {
cout << "Hiring Experiment - Expected number of Hirings" << endl;
cout << "Modified by Hiqmet Kamberaj on 4/7/23." << endl;
cout << "Copyright (c) 2023 Hiqmet Kamberaj. All rights reserved." << endl;
int n_h, best;
int n_h_expected = int( log((double)n) );
int rank[n];
initrand();
for (int i = 0; i < n; i++) rank[i] = myIrand(1,n);
n_h = 0;
best = 0;
for (int i = 0; i < n; i++){
if ( rank[i] > best ) {
best = rank[i];
n_h++;
}
}
cout << endl;
cout << ".................... Method 1 (Random ranking) ..........................." << endl;
cout << "Number of hirings " << n_h << " out of " << n << " trials" << endl;
cout << "Expected number of hirings " << n_h_expected << endl;
cout << "Deviation from Expected number of hirings " << abs(n_h_expected - n_h) << endl;
initrand();
n_h = 0;
for (int i = 0; i < n; i++){
if ( drand(0.0,1.0) <= prob(i+1) ) {
n_h++;
}
}
cout << endl;
cout << "................ Method 2 (Indicator random variables) ..................." << endl;
cout << "Number of hirings " << n_h << " out of " << n << " trials" << endl;
cout << "Expected number of hirings " << n_h_expected << endl;
cout << "Deviation from Expected number of hirings " << abs(n_h_expected - n_h) << endl;
initrand();
int n3 = n*n*n;
for (int i = 0; i < n; i++) rank[i] = myIrand(1, n3);
selectionSort( n, rank );
n_h = 0;
best = 0;
for (int i = 0; i < n; i++){
if ( rank[i] > best ) {
best = rank[i];
n_h++;
}
}
cout << endl;
cout << "................... Method 3 (Permute by sorting) ........................" << endl;
cout << "Number of hirings " << n_h << " out of " << n << " trials" << endl;
cout << "Expected number of hirings " << 1 << endl;
cout << "Deviation from Expected number of hirings " << abs(1 - n_h) << endl;
initrand();
for (int i = 0; i < n; i++)
rank[i] = i+1;
for (int i = 0; i < n; i++)
SWAP(rank[i], rank[myIrand(i,n-1)]);
n_h = 0;
best = 0;
for (int i = 0; i < n; i++){
if ( rank[i] > best ) {
best = rank[i];
n_h++;
}
}
cout << endl;
cout << "................... Method 4 (Radomize in place) ........................" << endl;
cout << "Number of hirings " << n_h << " out of " << n << " trials" << endl;
cout << "Expected number of hirings " << n_h_expected << endl;
cout << "Deviation from Expected number of hirings " << abs(n_h_expected - n_h) << endl;
return(0);
}
int myIrand(int min, int max) {
return ceil( drand( (double) min, (double)max ) );
}
double prob(int i) {
return (1.0/(double)i);
}
void selectionSort(int n, int s[])
{
int i, key;
for (int j = 1; j < n; j++){
key = s[j];
i = j-1;
while ( i >= 0 && s[i] <= key){
s[i+1] = s[i];
i--;
}
s[i+1] = key;
}
}
Select the $i$-th smallest of $n$ elements (the element with rank $i$).
Special cases:
- $i = 1$: minimum;
- $i = n$: maximum;
- $i =\lfloor(n + 1)/2\rfloor$ lower median; or $i =\lceil(n + 1)/2\rceil$: upper median
Input: A set $A$ of $n$ (distinct) numbers and a number $i$, with
(4)
\begin{align} 1 \le i \le n \end{align}
Output: The element $x\in A$ that is larger than exactly $i-1$ other elements of $A$.
In the following, the code for finding min and max of an array is shown.
//
//
//
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include "Random.hpp"
#include "defs.hpp"
#include "Maths.hpp"
using namespace std;
using namespace rangen;
using namespace maths;
int const n=11;
double a[n];
int main(int argc, const char * argv[]) {
double min, max;
cout << "Finding min and max of an array" << endl;
cout << "Modified by Hiqmet Kamberaj on 4/18/23." << endl;
cout << "Copyright (c) 2023 Hiqmet Kamberaj. All rights reserved." << endl;
initrand();
for (int i = 0; i < n; i++) {
a[i] = drand(0.0,1.0);
cout << i << " " << a[i] << endl;
}
cout << "Minimum= " << minVector(n, a) << endl;
cout << "Maximum= " << maxVector(n, a) << endl;
minmaxVector(n, a, &min, &max);
cout << "(min, max) = " << "(" << min << "," << max << ")" << endl;
return(0);
}
Randomized Select Algorithm
A pseudocode for randomized select is given below:
RAND − SELECT(A, p, q, i) :-> ith smallest of A[p..q]
if p = q then return A[p]
r ← Randomized − Partition(A, p, q)
k ← r − p + 1 .k = rank(A[r])
if i = k then return A[r]
if i < k
then return RAND − SELECT(A, p,r − 1, i)
else return RAND − SELECT(A,r + 1, q, i − k)
where
RANDOMIZED-PARTITION(A, p,r)
1) i ←RANDOM(p,r)
2) exchange A[r] ↔ A[i]
3) return PARTITION(A, p,r)
and
PARTITION(A, p,r)
1) x ← A[r]
2) i ← p − 1
3) for j ← p to r − 1 do
4) if A[j] ≤ x then
5) i ← i + 1
6) exchange A[i] ↔ A[j]
7) exchange A[i + 1] ↔ A[r]
8) return i + 1
In the following, an implementation code is given in C++.
//
//
//
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include "Random.hpp"
#include "defs.hpp"
#include "Maths.hpp"
using namespace std;
using namespace rangen;
using namespace maths;
int const n=11;
double a[n];
int main(int argc, const char * argv[]) {
int const i = 1;
cout << "Finding the i-th smallest element of an array" << endl;
cout << "Modified by Hiqmet Kamberaj on 4/18/23." << endl;
cout << "Copyright (c) 2023 Hiqmet Kamberaj. All rights reserved." << endl;
initrand();
for (int i = 0; i < n; i++) {
a[i] = drand(0.0,1.0);
cout << i << " " << a[i] << endl;
}
cout << "i-th smallest element = (" << i << "," << rand_select(a, 0, n-1, i)<<")" << endl;
return(0);
}
In the following figure, we show the linear timing of randomized select algorithm:
(5)
\begin{align} T(n) = \Theta(n) \end{align}
In the following, we show the quicksort algorithm in C++:
//
//
//
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include "Random.hpp"
#include "defs.hpp"
#include "Maths.hpp"
using namespace std;
using namespace rangen;
using namespace maths;
int const n=5;
double a[n];
int main(int argc, const char * argv[]) {
cout << "Quicksort algorithm" << endl;
cout << "Modified by Hiqmet Kamberaj on 4/25/23." << endl;
cout << "Copyright (c) 2023 Hiqmet Kamberaj. All rights reserved." << endl;
initrand();
for (int i = 0; i < n; i++) {
a[i] = drand(0.0,1.0);
}
cout << "Before sorting(:" << endl;
printVector(n, a);
quicksort(a, 0, n-1);
cout << "After sorting:)" << endl;
printVector(n, a);
return(0);
}
where
int partition(double a[], int p, int r){
double x = a[r];
int i = p-1;
for (int j = p; j <= r-1; j++) {
if (a[j] <= x) {
i++;
SWAP(a[i], a[j]);
}
}
i++;
SWAP(a[i], a[r]);
return i;
}
void quicksort(double a[], int p, int r) {
if (p < r) {
int q = partition(a, p, r);
quicksort(a, p, q-1);
quicksort(a, q+1, r);
}
}
In the case of the randomized quicksort algorithm, we have
int rand_partition(double a[], int p, int r){
int i = ceil( drand((double)p, (double)r) );
SWAP( a[r], a[i] );
return partition(a, p, r);
}
void rand_quicksort(double a[], int p, int r) {
if (p < r) {
int q = rand_partition(a, p, r);
rand_quicksort(a, p, q-1);
rand_quicksort(a, q+1, r);
}
}
Figure below shows the timing of the quicksort algorithm:
(6)
\begin{align} T(n)=O(n\log n) \end{align}
Creating and Printing out in a BST
The following C++ code represents the algorithms for inserting a list of numbers in an empty BST and printing them out.
//
//
//
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
struct Node;
typedef Node *Node_ptr;
struct Node
{
int item;
Node_ptr ptr_to_parent_node;
Node_ptr ptr_to_left_node;
Node_ptr ptr_to_right_node;
};
Node_ptr tree_insert(Node_ptr z, Node_ptr &root);
void assign_list(Node_ptr &a_list);
void assign_new_node(Node_ptr &a_node);
void print_list_preorder(Node_ptr a_node);
void print_list_postorder(Node_ptr a_node);
void print_list_inorder(Node_ptr a_node);
int main(int argc, char** argv) {
Node_ptr my_list = NULL;
assign_list(my_list);
cout << "\nTHE LIST INORDER IS:" << endl;
print_list_inorder(my_list);
cout << endl;
cout << "\nTHE LIST PREORDER IS:" << endl;
print_list_preorder(my_list);
cout << endl;
cout << "\nTHE LIST POSTORDER IS:" << endl;
print_list_postorder(my_list);
cout << endl;
return 0;
}
void assign_list(Node_ptr &a_list)
{
Node_ptr root, current_node, last_node;
int item;
assign_new_node(a_list);
cout << "Enter first (or root of BST) number (or '-1' to end list): ";
cin >> item;
a_list->item = item;
a_list->ptr_to_parent_node = NULL;
a_list->ptr_to_left_node = NULL;
a_list->ptr_to_right_node = NULL;
if (a_list->item == -1)
{
delete a_list;
a_list = NULL;
}
current_node = a_list;
root = a_list;
while (current_node != NULL)
{
assign_new_node(last_node);
cout << "Enter next number (or '-1' to end list): ";
cin >> item;
last_node->item = item;
last_node->ptr_to_parent_node = current_node;
if (last_node->item == -1)
{
delete last_node;
last_node = NULL;
current_node = last_node;
}
else{
current_node = tree_insert(last_node, root);
}
}
}
Node_ptr tree_insert(Node_ptr z, Node_ptr &root)
{
Node_ptr x, y, parent;
y = NULL;
x = root;
while (x != NULL)
{
y = x;
if (z->item < x->item)
x = x->ptr_to_left_node;
else
x = x->ptr_to_right_node;
}
parent = y;
if (parent == NULL) {
root = z;
}
else {
if (z->item < y->item)
y->ptr_to_left_node=z;
else
y->ptr_to_right_node=z;
}
return y;
}
void assign_new_node(Node_ptr &a_node)
{
a_node = new Node;
if (a_node == NULL)
{
cout << "sorry - no more memory\n";
exit(1);
}
}
void print_list_preorder(Node_ptr a_node)
{
if (a_node != NULL)
{
cout << a_node->item << " ";
print_list_preorder(a_node->ptr_to_left_node);
print_list_preorder(a_node->ptr_to_right_node);
}
}
void print_list_postorder(Node_ptr a_node)
{
if (a_node != NULL)
{
print_list_postorder(a_node->ptr_to_left_node);
print_list_postorder(a_node->ptr_to_right_node);
cout << a_node->item << " ";
}
}
void print_list_inorder(Node_ptr a_node)
{
if (a_node != NULL)
{
print_list_inorder(a_node->ptr_to_left_node);
cout << a_node->item << " ";
print_list_inorder(a_node->ptr_to_right_node);
}
}
The INORDER algorithm is described in the following pseudocode:
Inorder-Tree-Walk (x)
1.if x != NIL
2. then Inorder-Tree-Walk(left[x])
3. print key[x]
4. Inorder-Tree-Walk(right[x])
The PREORDER algorithm in a BST is given below:
PREORDER-TREE-WALK (x)
1. If x != NIL then
2. print key[x]
3. PREORDER-TREE-WALK (left[x])
4. PREORDER-TREE-WALK (right[x])
and for the POSTORDER the following pseudocode describes the algorithm:
POSTORDER-TREE-WALK (x)
1. If x != NIL then
2. POSTORDER-TREE-WALK (left[x])
3. POSTORDER-TREE-WALK (right[x])
4. print key[x]
The algorithm for insertion in an BST or empty BST is given in the following pseudocode:
Tree-Insert (T, z)
1. y ← NIL
2. x ← root[T]
3. while x != NIL
4. do y ← x
5. if key[z] < key[x]
6. then x ← left[x]
7. else x ← right[x]
8. p[z] ← y
9. if y = NIL
10. then root[T] ← z . Tree T was empty
11. else if key[z] < key[y]
12. then left[y] ← z
13. else right[y] ← z
In the following, we show the code for deleting a key from a BST:
//
//
//
//
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
struct Node;
typedef Node *Node_ptr;
struct Node
{
int item;
Node_ptr ptr_to_parent_node;
Node_ptr ptr_to_left_node;
Node_ptr ptr_to_right_node;
};
Node_ptr tree_insert(Node_ptr z, Node_ptr &root, Node_ptr &parent);
void assign_list(Node_ptr &a_list, Node_ptr &root);
void assign_new_node(Node_ptr &a_node);
Node_ptr tree_search(Node_ptr x, int k);
Node_ptr tree_minimum(Node_ptr x);
Node_ptr tree_maximum(Node_ptr x);
Node_ptr tree_successor(Node_ptr x);
Node_ptr tree_predecessor(Node_ptr x);
Node_ptr tree_delete(Node_ptr &root, Node_ptr &z);
void print_list_inorder_before(Node_ptr a_node);
void print_list_inorder_after(Node_ptr a_node, Node_ptr y, Node_ptr z);
int main(int argc, char** argv) {
Node_ptr bst = NULL, root_bst=NULL;
Node_ptr z, y;
int k;
assign_list(bst, root_bst);
cout << "\nDelete the node with key:" << endl;
cin >> k;
z = tree_search(bst, k);
cout << "\nTHE LIST INORDER BEFORE IS:" << endl;
print_list_inorder_before(bst);
cout << endl;
y = tree_delete(root_bst, z);
cout << "\nTHE LIST INORDER AFTER IS:" << endl;
print_list_inorder_after(bst, y, z);
cout << endl;
return 0;
}
void assign_list(Node_ptr &a_list, Node_ptr &root)
{
Node_ptr current_node, last_node;
int item;
assign_new_node(a_list);
cout << "Enter first (or root of BST) number (or '-1' to end list): ";
cin >> item;
a_list->item = item;
a_list->ptr_to_parent_node = NULL;
a_list->ptr_to_left_node = NULL;
a_list->ptr_to_right_node = NULL;
if (a_list->item == -1)
{
delete a_list;
a_list = NULL;
}
current_node = a_list;
root = a_list;
while (current_node != NULL)
{
assign_new_node(last_node);
cout << "Enter next number (or '-1' to end list): ";
cin >> item;
last_node->item = item;
last_node->ptr_to_parent_node = current_node;
if (last_node->item == -1)
{
delete last_node;
last_node = NULL;
current_node = last_node;
}
else{
current_node = tree_insert(last_node, root, last_node->ptr_to_parent_node);
}
}
}
Node_ptr tree_insert(Node_ptr z, Node_ptr &root, Node_ptr &parent)
{
Node_ptr x, y;
y = NULL;
x = root;
while (x != NULL)
{
y = x;
if (z->item < x->item)
x = x->ptr_to_left_node;
else
x = x->ptr_to_right_node;
}
parent = y;
if (parent == NULL) {
root = z;
}
else {
if (z->item < y->item) {
y->ptr_to_left_node=z;
}
else {
y->ptr_to_right_node=z;
}
}
parent = y;
return y;
}
void assign_new_node(Node_ptr &a_node)
{
a_node = new Node;
if (a_node == NULL)
{
cout << "sorry - no more memory\n";
exit(1);
}
}
Node_ptr tree_delete(Node_ptr &root, Node_ptr &z)
{
Node_ptr x=NULL, y=NULL;
cout << "Key to delete: " << z->item << endl;
if (z->ptr_to_left_node == NULL || z->ptr_to_right_node == NULL) {
y = z;
cout << "Case 1 or Case 2" << endl;
cout << "Key to be deleted: " << y->item << endl;
}
else {
y = tree_successor(z);
cout << "Case 3" << endl;
cout << "Key of its successor: " << y->item << endl;
}
if (y->ptr_to_left_node != NULL) {
x = y->ptr_to_left_node;
}
else if (y->ptr_to_right_node != NULL) {
x = y->ptr_to_right_node;
}
if (x != NULL)
x->ptr_to_parent_node = y->ptr_to_parent_node;
if (y->ptr_to_parent_node == NULL)
root = x;
else if (y == y->ptr_to_parent_node->ptr_to_left_node){
y->ptr_to_parent_node->ptr_to_left_node = x;
if (z->ptr_to_left_node == NULL || z->ptr_to_right_node == NULL){
if (x != NULL)
y->item = x->item;
else
y = NULL;
}
}
else {
y->ptr_to_parent_node->ptr_to_right_node=x;
if (z->ptr_to_left_node == NULL || z->ptr_to_right_node == NULL) {
if (x != NULL)
y->item = x->item;
else
y = NULL;
}
}
if (y!= NULL)
cout << "Final Key Placed on Node z: " << y->item << endl;
else
cout << "Final Key Placed on Node z is NULL node" << endl;
return y;
}
Node_ptr tree_search(Node_ptr x, int k)
{
if (x == NULL || k == x->item)
return x;
if (k < x->item)
return tree_search(x->ptr_to_left_node, k);
else
return tree_search(x->ptr_to_right_node, k);
}
Node_ptr tree_minimum(Node_ptr x)
{
while (x->ptr_to_left_node != NULL)
x = x->ptr_to_left_node;
return x;
}
Node_ptr tree_maximum(Node_ptr x)
{
while (x->ptr_to_right_node != NULL)
x = x->ptr_to_right_node;
return x;
}
Node_ptr tree_successor(Node_ptr x)
{
if (x->ptr_to_right_node != NULL)
return tree_minimum(x->ptr_to_right_node);
Node_ptr y = x->ptr_to_parent_node;
while ( y != NULL && x== y->ptr_to_right_node) {
x = y;
y = y->ptr_to_parent_node;
}
return y;
}
Node_ptr tree_predecessor(Node_ptr x)
{
if (x->ptr_to_left_node != NULL)
return tree_maximum(x->ptr_to_left_node);
Node_ptr y = x->ptr_to_parent_node;
while ( y != NULL && x== y->ptr_to_left_node) {
x = y;
y = y->ptr_to_parent_node;
}
return y;
}
void print_list_inorder_before(Node_ptr a_node)
{
if (a_node != NULL)
{
print_list_inorder_before(a_node->ptr_to_left_node);
cout << a_node->item << " ";
print_list_inorder_before(a_node->ptr_to_right_node);
}
}
void print_list_inorder_after(Node_ptr a_node, Node_ptr y, Node_ptr z)
{
if (a_node != NULL)
{
print_list_inorder_after(a_node->ptr_to_left_node,y,z);
if (z == a_node)
cout << y->item << " ";
else
cout << a_node->item << " ";
print_list_inorder_after(a_node->ptr_to_right_node,y,z);
}
}
Figure below show the linear timing for printing out the BST keys in sorting order.
Figure below show the logarithm timing for searching an key in the BST.