Category: Computer Science

// Insertion sort, heap sort, and quick sort algorithms
// From "Algortihms" by Thomas H. Cormen, et. al.
// Selection sort, Singleton's sort, and Tree Sort 3
// From "Sorting and Sort Systems" by Harold Lorin

#pragma once

#include <cinttypes>
#include <vector>
using namespace std;

// See "Introduction to Algorithms"
// Thomas H. Cormen Among Others
// Chapter 13 Binary Search Trees
// Translated from Pascal found in
// "Applied Data Structures Using
// Pascal" by Guy J. Hale and
// Richard J. Easton Chapter 6
// Introduction to Trees

typedef struct treeNode
{
	uint32_t key;
	treeNode* lt, * rt;
} TREENODE, * PTREENODE;

class BinarySearchTree
{
public:
	static void InitTree(
		PTREENODE root, uint32_t key);
	static void CreateTree(
		PTREENODE& root, vector<uint32_t>& data,
		unsigned int seed, size_t bound);
	static void InOrderTreeWalk(PTREENODE x);
	static PTREENODE TreeSearch(PTREENODE x, uint32_t k,
		uint32_t& depth);
	static PTREENODE IterativeTreeSearch(
		PTREENODE x, uint32_t k);
	static PTREENODE TreeMinimum(PTREENODE x);
	static PTREENODE TreeMaximum(PTREENODE x);
	static PTREENODE TreeSuccessor(PTREENODE x);
	static void InsertTree(
		PTREENODE &root, uint32_t key);
};

#include "pch.h"
#include "BinarySearchTree.h"
#include "SieveOfEratosthenes.h"
#include <iostream>
#include <vector>
using namespace std;

void BinarySearchTree::InitTree(
	PTREENODE root, uint32_t key)
{
	root->key = key;
	root->lt = root->rt = NULL;
}

void BinarySearchTree::CreateTree(
	PTREENODE& root, vector<uint32_t>& keys,
	unsigned int seed, size_t bound)
{
	SieveOfEratosthenes::Initialization(bound);

	for (uint32_t i = 0; i < bound; i++)
	{
		uint32_t prime = SieveOfEratosthenes::GetNextPrime(bound);

		if (prime != -1)
			keys.push_back(prime);
	}

	srand(seed);

	unsigned int number;
	uint32_t key = -1;

	number = rand() % keys.size();
	key = keys[number];
	InitTree(root, key);
	keys.erase(keys.begin() + number, keys.begin() + number + 1);
	size_t count = 0, start = keys.size();

	for (size_t count = 1; count < start; count++)
	{
		bool found = false;

		do
		{
			number = rand() % start;

			if (number < keys.size())
			{
				key = keys[number];
				found = true;
			}
		} while (!found);
		
		keys.erase(keys.begin() + number, keys.begin() + number + 1);
		BinarySearchTree::InsertTree(root, key);
	}

	delete[] SieveOfEratosthenes::sieve;
}

void BinarySearchTree::InOrderTreeWalk(PTREENODE x)
{
	if (x != NULL)
	{
		InOrderTreeWalk(x->lt);
		cout << x->key << endl;
		InOrderTreeWalk(x->rt);
	}
}

PTREENODE BinarySearchTree::TreeSearch(
	PTREENODE x, uint32_t k, uint32_t &depth)
{
	depth++;

	if (x == NULL || x->key == k)
		return x;
	if (k < x->key)
		return TreeSearch(x->lt, k, depth);

	return TreeSearch(x->rt, k, depth);
}

PTREENODE BinarySearchTree::IterativeTreeSearch(
	PTREENODE x, uint32_t k)
{
	while (x != NULL && x->key != k)
	{
		if (k < x->key)
			x = x->lt;
		else
			x = x->rt;
	}

	return x;
}

PTREENODE BinarySearchTree::TreeMinimum(PTREENODE x)
{
	while (x->lt != NULL)
		x = x->lt;
	return x;
}

PTREENODE BinarySearchTree::TreeMaximum(PTREENODE x)
{
	while (x->rt != NULL)
		x = x->rt;
	return x;
}

PTREENODE BinarySearchTree::TreeSuccessor(PTREENODE x)
{
	if (x->rt != NULL)
		return TreeSuccessor(x->rt);
	PTREENODE y = x;
	while (y != NULL && x == y->rt)
		x = y;
	return x;
}

void BinarySearchTree::InsertTree(
	PTREENODE& root, uint32_t key)
{
	bool inserted = false;
	PTREENODE node = new TREENODE();
	PTREENODE oneNode = root;

	while (!inserted)
	{
		if (key <= oneNode->key)
		{
			if (oneNode->lt != NULL)
				oneNode = oneNode->lt;
			else
			{
				oneNode->lt = node;
				inserted = true;
			}
		}

		else
		{
			if (oneNode->rt != NULL)
				oneNode = oneNode->rt;
			else
			{
				oneNode->rt = node;
				inserted = true;
			}
		}
	}

	node->key = key;
	node->lt = node->rt = NULL;
}

// PrimeNumberBST.cpp : This file contains the 'main' function.
// Program execution begins and ends there.
// Create a prime number search tree
// James Pate Wiliams, Jr. (c) 2023

#include "pch.h"
#include "BinarySearchTree.h"
#include "SieveOfEratosthenes.h"
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	while (true)
	{
		uint32_t bound = 50;
		size_t start = 0;
		unsigned int seed = 1;
		PTREENODE root = new TREENODE();

		cout << "Key Bound = ";
		cin >> bound;

		if (bound == 0)
			break;

		cout << "PRNG seed = ";
		cin >> seed;
		cout << endl;

		vector<uint32_t> data;
		uint32_t depth = 0, key;
		BinarySearchTree::CreateTree(
			root, data, seed, bound);
		BinarySearchTree::InOrderTreeWalk(root);
		cout << endl;
		cout << "Search key = ";
		cin >> key;

		PTREENODE x = BinarySearchTree::TreeSearch(
			root, key, depth);

		cout << "Search depth = ";
		cout << depth << endl;
		cout << "Found key = ";

		if (x != NULL)
			cout << x->key << endl;
		else
			cout << "Key not found" << endl;
	
		cout << endl;
	}

	return 0;
}

#pragma once
#include <cinttypes>
#include <vector>
using namespace std;

// See "Introduction to Algorithms"
// Thomas H. Cormen Among Others
// Chapter 13 Binary Search Trees
// Translated from Pascal found in
// "Applied Data Structures Using
// Pascal" by Guy J. Hale and
// Richard J. Easton Chapter 6
// Introduction to Trees

typedef struct treeNode
{
	uint32_t key;
	treeNode* lt, * rt;
} TREENODE, * PTREENODE;

class BinaryTree
{
public:
	static void InitTree(PTREENODE root, uint32_t key);
	static void InsertInTree(PTREENODE& root, uint32_t key);
	static void CreateTree(PTREENODE& root, vector<uint32_t> &data,
		unsigned int seed, size_t number);
	static void TravInOrder(PTREENODE node);
	static void TravPreOrder(PTREENODE node);
	static void TravPostOrder(PTREENODE node);
};

#include "BinaryTree.h"
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;

void BinaryTree::InitTree(
	PTREENODE root, uint32_t key)
{
	root->key = key;
	root->lt = root->rt = NULL;
}

void BinaryTree::InsertInTree(
	PTREENODE& root, uint32_t key)
{
	bool inserted = false;
	PTREENODE node = new TREENODE();
	PTREENODE oneNode = root;
	
	while (!inserted)
	{
		if (key <= oneNode->key)
		{
			if (oneNode->lt != NULL)
				oneNode = oneNode->lt;
			else
			{
				oneNode->lt = node;
				inserted = true;
			}
		}

		else
		{
			if (oneNode->rt != NULL)
				oneNode = oneNode->rt;
			else
			{
				oneNode->rt = node;
				inserted = true;
			}
		}
	}

	node->key = key;
	node->lt = node->rt = NULL;
}

void BinaryTree::CreateTree(PTREENODE& root, vector<uint32_t>& data,
	unsigned int seed, size_t number)
{
	srand(seed);
	uint32_t key = rand() % 1000;

	data.push_back(key);
	root = new TREENODE();
	InitTree(root, key);

	for (size_t i = 1; i < number; i++)
	{
		bool found = false;
		uint32_t next = rand() % 1000;
		
		while (!found)
		{
			for (size_t j = 0; !found && j < data.size(); j++)
				found = data[j] == next;

			next = rand() % 1000;
		}

		data.push_back(next);
	}

	for (size_t i = 1; i < data.size(); i++)
	{
		BinaryTree::InsertInTree(root, data[i]);
	}
}

void BinaryTree::TravInOrder(PTREENODE node)
{
	if (node != NULL)
	{
		TravInOrder(node->lt);
		cout << node->key << endl;
		TravInOrder(node->rt);
	}
}

void BinaryTree::TravPreOrder(PTREENODE node)
{
	if (node != NULL)
	{
		cout << node->key << endl;
		TravPreOrder(node->lt);
		TravPreOrder(node->rt);
	}
}

void BinaryTree::TravPostOrder(PTREENODE node)
{
	if (node != NULL)
	{
		TravPostOrder(node->lt);
		TravPostOrder(node->rt);
		cout << node->key << endl;
	}
}

// DataStructuresFromPascal.cpp : This file contains the 'main'
// function. Program execution begins and ends there.
// James Pate Williams, Jr. (c) 2023

#include "BinaryTree.h"
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	PTREENODE root = NULL;
	vector<uint32_t> data;
	unsigned int seed = 1;
	size_t number;

	cout << "# keys = ";
	cin >> number;
	cout << "PRNG seed = ";
	cin >> seed;
	cout << endl;
	BinaryTree::CreateTree(root, data, seed, number);
	BinaryTree::TravInOrder(root);
	cout << endl;
	BinaryTree::TravPreOrder(root);
}

#pragma once

// Binary searches from the following website
// https://www.geeksforgeeks.org/binary-search/

typedef long long ll;

class Search
{
public:
	int IterativeBinarySearch(
		ll A[], ll x, int low, int high);
	int RecursiveBinarySearch(
		ll A[], ll x, int low, int high);
	int IterativeLinearSearch(
		ll A[], ll x, int low, int high);
};

#include "Search.h"

int Search::IterativeBinarySearch(
	ll A[], ll x, int low, int high)
{
	do
	{
		int middle = low + (high - low) / 2;

		if (x == A[middle])
			return middle;

		else if (x > A[middle])
			low = middle + 1;

		else if (x < A[middle])
			high = middle - 1;

	} while (high >= low);

	return -1;
}

int Search::RecursiveBinarySearch(
	ll A[], ll x, int low, int high)
{
	if (high >= low)
	{
		int middle = low + (high - low) / 2;

		if (x == A[middle])
			return middle;

		else if (x > A[middle])
			return RecursiveBinarySearch(
				A, x, middle + 1, high);

		else if (x < A[middle])
			return RecursiveBinarySearch(
				A, x, low, middle - 1);
	}
	
	return -1;
}

int Search::IterativeLinearSearch(
	ll A[], ll x, int low, int high)
{
	for (int i = low; i <= high; i++)
		if (x == A[i])
			return i;

	return -1;
}

// Searching.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include "Search.h"
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using chrono::duration_cast;
using chrono::nanoseconds;

ll A[1000001];

ll RandomLongLong()
{
	ll lo = rand();
	ll hi = rand();

	return (lo << 31) | hi;
}

void GenerateArray(ll A[], int n, int seed)
{
	for (int i = 1; i <= n; i++)
		A[i] = RandomLongLong();
}

void GenerateArrayMod(ll A[], int n, int mod, int seed)
{
	Search search;

	for (int i = 1; i <= n; i++)
	{
		while (true)
		{
			ll Ai = RandomLongLong() % mod;

			if (search.IterativeLinearSearch(
				A, Ai, 1, i) == -1)
			{
				A[i] = Ai;
				break;
			}
		}
	}
}

int Partition(ll* A, int p, int r)
{
	int q = p;
	ll t;

	for (int u = p; u <= r - 1; u++)
	{
		if (A[u] <= A[r])
		{
			t = A[q];
			A[q] = A[u];
			A[u] = t;
			q++;
		}
	}

	t = A[q];
	A[q] = A[r];
	A[r] = t;

	return q;
}

void RunQuickSort(ll* A, int p, int r)
{
	if (p < r)
	{
		int q = Partition(A, p, r);

		RunQuickSort(A, p, q - 1);
		RunQuickSort(A, q + 1, r);
	}
}

void RunSearches(
	Search search,
	ll A[],
	int n, int seed)
{
	int index[4];
	ll x = RandomLongLong() % n;

	GenerateArrayMod(A, n, 2LL * n, seed);
	RunQuickSort(A, 1, n);
	
	cout << "key = " << x << endl;

	if (n <= 25)
	{		for (int i = 1; i <= n; i++)
			cout << A[i] << " ";

		cout << endl;
	}

	cout << "Runtimes in nanoseconds" << endl;
	cout << "n" << "\t" << "Iter" << "\t";
	cout << "Recur" << "\t" << "Linear" << endl;
	cout << setw(5) << n << "\t";

	auto start1 = chrono::steady_clock::now();
	index[0] = search.IterativeBinarySearch(A, x, 1, n);
	auto final1 = chrono::steady_clock::now();

	cout << setw(5) << duration_cast<nanoseconds>(final1 - start1).count();
	cout << "\t";

	auto start2 = chrono::steady_clock::now();
	index[1] = search.RecursiveBinarySearch(A, x, 1, n);
	auto final2 = chrono::steady_clock::now();

	cout << setw(5) << duration_cast<nanoseconds>(final2 - start2).count();
	cout << "\t";

	auto start3 = chrono::steady_clock::now();
	index[2] = search.IterativeLinearSearch(A, x, 1, n);
	auto final3 = chrono::steady_clock::now();

	cout << setw(5) << duration_cast<nanoseconds>(final3 - start3).count();
	cout << endl;
	cout << "Search indicies" << endl;

	for (int i = 0; i < 3; i++)
		cout << "index[" << i << "] = " << index[i] << endl;
}

int main()
{
	cout << "Comparison of Iterative Binary Search," << endl;
	cout << "Recursive Binary Search, and Linear Search" << endl;

	while (true)
	{
		int n, seed;
		Search search;

		cout << "n = ";
		cin >> n;
		
		if (n == 0)
			break;

		cout << "seed = ";
		cin >> seed;
		srand(seed);

		RunSearches(search, A, n, seed);
	}
}