Binary Search Tree | Chinese Rule of Eight

http://code.runnable.com/VUTjJDME6nRv_HOe/delete-node-from-bst-for-c%2B%2B

demo download xCode 7.3 (c++)

Adding to Tree Concept

Traverse until you hit a leaf. Then, Re-point at the leaf

//1) we NEED to RE-POINT all left and rights

//2) due to 1) we need to carry the tree into the parameter

void MyBST::addNode(Node * node, long long newData) {

if(newData > node->data) {

//right

if(node->right) //if the right tree exist, we have to recurse into it

this->addNode(node->right, newData);

else //if the right tree does not exist, we create a node and point our right to it

node->right = new Node(newData);

}

Finding from Tree Concept

Traverse if data does not match. If at leaf, return NULL.

1) we need the node back, hence, we return our traversals.
2) When we find our target node, we return a new Node with that value. That return will return traverse back.
3) If nothing is found then we return NULL.

//node to traverse into, data to match

Node * MyBST::findNode(Node * node, long long newData) {

//traverses

if(newData > node->data) {

//go right

if(node->right) {

//traverse down

return this->findNode(node->right, newData);

}

else {

return NULL;

}

//stop case

else if (newData == node->data) {

cout << "FOUND IT" << endl;

return new Node(newData);

}

return NULL;

}

Running Time

Average Time

Access: O(log(n))
Search: O(log(n))
Insertion: O(log(n))
Deletion: O(log(n))

Worst Time (due to unbalanced tree that deteriorates to a linear tree

Access: O(n)
Search: O(n)
Insertion: O(n)
Deletion: O(n)

The Node – building block of the Binary Search Tree

First we must create the building block of the tree. It is an object with a data container, a left pointer, and right pointer. Each pointer denotes a leaf.

You can initialize this object by value, and set both leafs to NULL.
Or you can pass in data to set everything.

struct Node {

int value;

Node *left;

Node *right;

Node(int val) {

this->value = val;

this->left = NULL;

this->right = NULL;

}

Node(int val, Node * left, Node * right) {

this->value = val;

this->left = left;

this->right = right;

}

};

Creating a BST tree

First we create the BST class. The key thing here is to add a private member for the root Node. This is the starting point of all tree manipulations.
Then we add the void addNode(Node * root, int newVal) for adding data algorithm.

class BST {

private:

Node * root; //head

void addNode(Node * root, int newVal);

public:

BST();

~BST();

void add(int value);

};

Adding Nodes O(log n)

We start at the root node, and check the value of it with the incoming new value.

If the new value is larger than the root, then:

1) If the right node exist, we move down the right side of the tree via recursion.
2) If the right node is NULL, we create a new Node, and point it to the right node.

If the new value is smaller or equal than the root, then:

1) If the left node exist, we move down the left side of the tree via recursion.
2) If the left node is NULL, we create a new Node, and point it to the left node.

void BST::addNode(Node * root, int newVal) {

GLOG;

std::cout << "\n" << __PRETTY_FUNCTION__ << " - value is: " << newVal << std::endl;

if(newVal > root->value) {

std::cout << "\n" << __PRETTY_FUNCTION__ << " -- newValue is larger than current !! -- ";

if(root->right) // new value is larger than current node's value

addNode(root->right, newVal); // we go down left

else {

std::cout << "\n" << __PRETTY_FUNCTION__ << " - Reached end. Creating new Node: (" << newVal << ")" << std::endl;

root->right = new Node(newVal);

}

} else {

std::cout << "\n" << __PRETTY_FUNCTION__ << " -- newValue is larger than current !! -- ";

if(root->left)

addNode(root->left, newVal);

else {

std::cout << "\n" << __PRETTY_FUNCTION__ << " - Reached end. Creating new Node: (" << newVal << ")" << std::endl;

root->left = new Node(newVal);

}

http://stackoverflow.com/questions/9456937/when-to-use-preorder-postorder-and-inorder-binary-search-tree-traversal-strate

Depth First Search – Pre order (left side)

print
recursion left
recursion right

If you know you need to explore the roots before inspecting any leaves, you pick pre-order because you will encounter all the roots before all of the leaves.

void BST::traverse(Node * root) {

std::cout << "\n" << __PRETTY_FUNCTION__ << " - value is: " << root->value << std::endl;

if(root->left)

traverse(root->left);

if(root->right)

traverse(root->right);

}

Depth First Search – Post order (right side)

recursion left
recursion right
print

If you know you need to explore all the leaves before any nodes, you select post-order because you don’t waste any time inspecting roots in search for leaves.

void BST::traverse(Node * root) {

if(root->left)

traverse(root->left);

if(root->right)

traverse(root->right);

std::cout << "\n" << __PRETTY_FUNCTION__ << " - value is: " << root->value << std::endl;

}

Depth First Search – In order (bottom side)

recursion left
print
recursion right

If you know that the tree has an inherent sequence in the nodes, and you want to flatten the tree back into its original sequence, than an in-order traversal should be used. The tree would be flattened in the same way it was created. A pre-order or post-order traversal might not unwind the tree back into the sequence which was used to create it.

void BST::traverse(Node * root) {

if(root->left)

traverse(root->left);

std::cout << "\n" << __PRETTY_FUNCTION__ << " - value is: " << root->value << std::endl;

if(root->right)

traverse(root->right);

}

Search for a value O(log n)

Search a value in the binary tree is the fastest. The time is O(log n).

If the node is not NULL, we recursively go down the tree according to if the “to get” value is larger or smaller. Then when we hit a node value that matches, we just return the current node.

Node * BST::search(long long value) {

if(root) {

return this->Traverse(root, value);

} else {

return NULL;

}

Node * BST::Traverse(Node * root, long long valueToGet) {

if(root==NULL) {

//std::cout << "Traverse: NULL reached...returning NULL" << std::endl;

return NULL;

}

std::cout << "\n ----STEP----" << std::endl;

std::cout << "\n --value to get is: " << valueToGet << std::endl;

std::cout << "\n current node's value is: " << root->value;

std::cout << "\n-------------------------\n" << std::endl;

if (valueToGet < root->value) {

return Traverse(root->left, valueToGet);

} else if (valueToGet > root->value) {

return Traverse(root->right, valueToGet);

} else {

if(root->value == valueToGet) {

//std::cout << "Traverse - value FOUND!" << valueToGet << std::endl;

return root;

}

return NULL;

}

Deletion O(log n)

Deletion is O(log n + k).

void BST::remove(int value) {

GLOG;

if(root) {

this->Delete(root, value);

} else {

}

Node * BST::Delete( Node * root, long long data) {

if(root == NULL) return root;

//basic traversal

else if(data < root->value)

root->left = Delete(root->left,data);

else if(data > root->value)

root->right = Delete(root->right, data);

else { //ran to a endpoint or found a node that matches

//if no leafs, node without children

if(root->left == NULL && root->right == NULL){

delete root; //delete the root

root = NULL;

} else if (root->left == NULL) {

// RIGHT child exists and LEFT is NULL, connect pointer to current's right leaf

Node * temp = root;

root = root->right;

delete temp;

} else if (root->right == NULL) {

//LEFT child exists and RIGHT is NULL, connect pointer to current's left left

Node *temp = root;

root = root->left;

delete temp;

} else {

//if BOTH leafs exist, replace the current node's value as the minimum of the right tree

Node * rightMin = FindMin(root->right); //find minimum of right tree

root->value = rightMin->value; //have current's value take on right tree's minimum

root->right = Delete(root->right, rightMin->value); //then search and destroy that value

}

return root;

}

Delete All Nodes

The idea behind deleting all the nodes is a thorough recursion through the left and right.

We delete in 2 situations:

1) delete the node if it has no children
2) delete the node after left and right recursion.

given that if a root is NULL, we just return.
If a node has one child (and the other is NULL), then the NULL leaf just returns.
We recurse down the child.

BST.cpp

BST::~BST() {

DeleteAllNodes(root);

}

void BST::DeleteAllNodes(Node * root) {

//nothing to delete if node is NULL, just return

if(root==NULL) {

return;

} else {

//when we reach a node with NO children, we delete it

if((root->left==NULL)&&(root->right==NULL)) {

cout << "deleting " << root->value << endl;

root->value = NULL;

root->left = NULL;

root->right = NULL;

delete root;

return;

}

//when we reach a node with 1 or more child, recurse down

DeleteAllNodes(root->left);

DeleteAllNodes(root->right);

//when both children trees are processed, delete current

cout << "deleting " << root->value << endl;

root->value = NULL;

root->left = NULL;

root->right = NULL;

delete root;

return;

}

Testing it all

#include <iostream>

#include <thread>

#include "BST.hpp"

#include <random>

using namespace std;

//Using a BST, 100 million sorted entries takes 30 steps, and 0.00065600s on a 2013 iMac

#define TOTAL_NUM 1000000

//http://stackoverflow.com/questions/31015456/is-there-a-way-i-can-get-a-random-number-from-0-1-billion

//http://stackoverflow.com/questions/876901/calculating-execution-time-in-c

//http://www.bogotobogo.com/cplusplus/multithreaded4_cplusplus11.php

void searchFor(long long num, BST * tree) {

clock_t tStart = clock();

Node * n = tree->search(num);

printf("Time taken to search the tree: %.8fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

if(n) {

std::cout << "node with data: " << n->value << " found";

} else {

std::cout << "\n this tree does not data: " << 888;

}

void createUniques(BST * tree) {

cout << "----- createOneBillionUniques ---------" << endl;

random_device rd;

mt19937 gen(rd());

uniform_int_distribution<> dis(1, TOTAL_NUM); //1 billion

//1 billion !!!

clock_t tStartBuild = clock();

for (int n=0; n<10; ++n) {

//cout << "\t index " << n << ", ";

tree->add(dis(gen));

}

printf("Time taken to build the TREE: %.8fs\n", (double)(clock() - tStartBuild)/CLOCKS_PER_SEC);

cout << "\n NODES ADDED \n" << endl;

searchFor(8888, tree);

delete tree;

}

int main(int argc, const char * argv[]) {

cout << " -------- BST demonstration ------ \n";

BST * myTree = new BST();

thread t1(createUniques, myTree);

t1.join();

return 0;

}