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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
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; } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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 { } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
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); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#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; } |
