Prime Number Binary Search Tree Implemented by James Pate Williams, Jr.

#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;
}