Search Algorithms in C++ || Binary Search Tree || Part 3

This is part 3 for Binary Search Tree, previous posts are Part 1 and Part 2. In this post, I'll attach the complete code also explain how Remove function for BST can be implemented.

There are a few situations possible while removing a node from the BST. There node may have no children, both children, etc. Let's have a quick view of them.

Key is element to be deleted.

• BST is empty -- then do nothing.
• Key is not found -- do nothing.
• Key is found at a node which is:

                 (a) A leaf node -- delete that node (let's call it current node), Update its Parent's appropriate child to Null (e.g. if it was Left child that got deleted, set lChild pointer in Parent to null.), point Previous (Previous is the Parent node of the Current node) pointer to null. (if the current was leaf as well as root, then set root pointer to null)

                (b) Not a leaf node and has:

                       (i) One child N -- Previous adapts N, Remove Current

                       (ii) Two children -- find the Predecessor¹ P of the current node, Swap P and current node, if P is leaf then apply A else apply B(a)

Figure A

Figure B

 ¹To find a Predecessor, go to left child and then keep going right till the leaf element is reached. Predecessor is the element which is smaller to the Current node but larger than all it's left side children.

In this figure A, you can see even if replace predecessor with current node i.e. 12 with 9, the order of the tree remains intact. See figure B. 

Now let's look at the code.

void remove(const T & key)

{

if (s == 0)

{

cout << "\n Empty! \n";

return;

}

else

{

if (search(key) == false)

{

cout << "\n Key not found! \n";

return;

}

//SEARCHING

Node* curr = root;

Node* prev = nullptr;   //parent

while (curr != nullptr && curr->data != key)

{

prev = curr;

if (curr->data > key)

curr = curr->lchild;   //key is smaller

else

curr = curr->rchild;   //key is greater

}    

if (curr->lchild == nullptr && curr->rchild == nullptr) //if leaf

{

delete curr;

if (curr == root)

root = nullptr;

//is it left or right child?

else if (prev->data > key)   

prev->lchild = nullptr;

else if (prev->data < key)

prev->rchild = nullptr;

}

else     //not leaf

{

//single child

if ((curr->lchild != nullptr && curr->rchild == nullptr) || (curr->lchild == nullptr && curr->rchild != nullptr))

{

if (prev->lchild = curr)    //if curr was left child of its parent

{

if (curr->lchild != nullptr) //if curr has left child

{

prev->lchild = curr->lchild;    //prev adopts left child

}

else if (curr->rchild != nullptr)  //if curr has right child

{

prev->lchild = curr->rchild;   //prev adopts right child

}

}

else if (prev->rchild = curr)    //if curr was right child of its parent

{

if (curr->lchild != nullptr) //if curr has left child

{

prev->rchild = curr->lchild;    //prev adopts left child

}

else if (curr->rchild != nullptr)  //if curr has right child

{

prev->rchild = curr->rchild;   //prev adopts right child

}

}

delete curr;

}

//if curr has 2 children

else if (curr->lchild != nullptr && curr->rchild != nullptr)

{

//find the predecessor

Node* curr2 = curr->lchild;  //go to left of the curr

Node* prev2 = curr;

Node* prev3 = nullptr;

while (curr2 != nullptr)

{

prev3 = prev2;

prev2 = curr2;

curr2 = curr2->rchild;

}

swap(curr->data, prev2->data);   //swapped

//if prev2 is a leaf

if (prev2->lchild == nullptr && prev2->rchild == nullptr) 

{

if (prev2 == root)

root = nullptr;

else if (prev3->lchild == prev2)

prev3->lchild = nullptr;

else if (prev3->rchild == prev2)

prev3->rchild = nullptr;

delete prev2;

}

//if prev2 has one child

else if ((prev2->lchild != nullptr && prev2->rchild == nullptr) || (prev2->lchild == nullptr && prev2->rchild != nullptr))

{

if (prev3->lchild = prev2)    //if prev2 was left child of its parent

{

if (prev2->lchild != nullptr) //if curr has left child

{

prev3->lchild = prev2->lchild;    //prev adopts left child

}

else if (prev2->rchild != nullptr)  //if curr has right child

{

prev3->lchild = prev2->rchild;   //prev adopts right child

}

}

else if (prev3->rchild = prev2)    //if prev2 was right child of its parent

{

if (prev2->lchild != nullptr) //if curr has left child

{

prev3->rchild = prev2->lchild;    //prev adopts left child

}

else if (prev2->rchild != nullptr)  //if prev2 has right child

{

prev3->rchild = prev2->rchild;   //prev adopts right child

}

}

delete curr;

}

}

}

s--;   //reducing size

}

}

This is all so far about BST. 

To download code, Click Here!

In my code, I have other utility functions too as per my requirement which I have not discussed here. Keep them or remove them, your choice! :P

Thanks for reading. If any question, Comment below! :)

        

Read More

Search Algorithms in C++ || Binary Search Tree || Part 2

This is the second post in continuation of the last post on Binary Search Trees in C++.

Just like we did for vectors, linked strings; we will have a struct for Node to represent nodes of the tree. The node will contain a  data element, a pointer to the left child and a pointer to the right child.

template <class T>
struct node{
             T data;
             node * lChild, rChild;
}

And then a class for BST (Binary Search Tree). In the private members, we will have a node* root element that will serve as the beginning of tree traversal. We will have some basic functions like insert, search and remove in the class. I have made an iterator for the traversal in my class. Given below is the code:

template <class T>
class bst {
private:
struct Node {
T data;
Node* lchild;
Node* rchild;

};   //I've made the struct inside the class so that user cannot access it

Node* root;   //private members
int s;

Node* createNode(const T & obj )  //a utility function
{
Node* temp = new Node;
temp->data = obj;
temp->lchild = temp->rchild = nullptr;
return temp;

}

int height(Node* n )  //to get tree height at a specific node

{

if (n == nullptr)

{

return 0;

}

else

{

int ln = height(n->lchild);     //used recursion to get tree height using

                                                                    originating branches from the child

int rn = height(n->rchild);

return (max(rn, ln) + 1);

}

}

bst()  //default constructor

{

s = 0;

root = nullptr;

}

Strategy used in Insert:  We have two nodes to help in our traversal, Previous and Current. In the parameter we take 'key', which is the data to be inserted, we compare that data with the current node and go to its left if the data in the current node is greater than the key (as the left child is smaller than its parent) and go to its right if the data in the current node is smaller than the key (as the right child is greater than its parent).

  >> Note: The data here is template T type which can be an int, string or any custom datatype. The comparison is done using < and > operators which may be type specific. E.g. different for integer comparison and different for string comparsion. 

Also, in every traversal we update Previous pointer with the Current pointer to move to the next and update Current with left or right child's pointer using comparison. The while loop traversal keeps going till we reach the leaf position where we can insert our new node. After the while loop ends, the Previous pointer is pointing to the node of which we will make a new child, either left or right, after comparison of the data.

If the previous pointer is simply empty, it means no node has been created so far and the tree is empty, so we create a new node at the Root. 

void insert(const T & key)

{

                

Node* curr = root;  //current element in the traversal, in the beginning it is root

Node* prev = nullptr;    //previous element, i.e. parent of the current node

while (curr != nullptr)    //if the tree is not empty, start traversal

{

prev = curr;

if (curr->data > key)   //if key < current then go to left

{

curr = curr->lchild;  

}

else if (curr->data < key)    //if key > current then go to right

{

curr = curr->rchild;

}

else

return;    //no repetition allowed

}

if (prev == nullptr)

{

root = createNode(key);    //if empty

s++;

}

else        //tree size >= 1

{

if (prev->data < key)     //key is bigger

{

prev->rchild = createNode(key);

s++;

}

else if (prev->data > key)    //key is smaller

{

prev->lchild = createNode(key);

s++;

}

}

}

bool search(const T & key)  //returns the true if the key found in the tree, else false
{
Node* curr = root;
while (curr != nullptr && curr->data != key )
{
if (curr->data > key)
curr = curr->lchild;   //key is smaller
else
curr = curr->rchild;   //key is greater
}

if (curr != nullptr)
return true;

return false;

}

int size()
{
return s;
}

int height()
{
return height(root);
}

Here is the code for the Iterator of this class, it will be in the public section of the BST class

//************* ITERATOR **************//

class iterator {
private:
vector <Node*> nodes;
int index;

public:
iterator(int i, vector <Node*> & v)
{
nodes = v;    //automatically does deep copy in vector class
index = i;
}

iterator(const iterator & obj)
{
nodes = obj.nodes;
index = obj.index;
}

bool operator != (const iterator & obj)
{
if (index != obj.index)
return true;

return false;
}

void  operator ++ ()
{
index++;

}

void operator ++ (int ind)
{
index = index + ind;
}

T operator * ()
{
return nodes[index]->data;
}
};


/****************** End of Iterator Class *********************/

We will also require some utility functions in the BST class to help initialise the iterator.

==> To see what are iterators and how they work, Click Here!

void getNodes_inOrder(Node* n, vector  <Node*> & v )
{
if (n != nullptr)
{
getNodes_inOrder(n->lchild, v);
v.push_back(n);
getNodes_inOrder(n->rchild, v);
}
}

iterator begin()
{
vector <Node*>  v;
getNodes_inOrder(root, v);
iterator itr(0, v);     //starting index is 0
return itr;
}

iterator end()
{
vector <Node*>  v;
getNodes_inOrder(root, v);
iterator itr(v.size(), v);     //ending index is vector's size
return itr;
}

The Remove function of this class is a bit tricky and long in code length. So I will explain that in the next post. Complete code will be posted in the next post.

Thank you for reading and comment below if you have any questions! :)

Read More

Search Algorithms || Binary Search Tree || Part 1

What are Search Algorithms?

Search Algorithms provide us with fast search mechanism. Not only search, but insertion and deletion also becomes faster. These sort of Algorithms are normally explored under the subject Data Structures. There are different algorithms like binary search, binary search tree, minHeap, etc. 

In this post and some upcoming posts, I'll be explaining Binary Search Tree. So let's begin.

Binary Search Tree

In binary search tree, the data is divided into halves and there is a root element. There are nodes in the tree. 

• Each node has zero, one or two children. 
• Each node has only one parent. But may have grand parents, great grant parents and so on :P
• Nodes that have zero children are called leaves.
• Each tree has a height, which is number of jumps/edges from the root to the most distant leaf.
• Similarly, height of a node is the number of jumps/edges from the node to most distant leaf.

Height of the root is the height of the tree.

In the image given above, you can observe a binary tree. The height of this tree is 2. Root has two children, right and left children. The right child of the root has only one child i.e. a left child. While the left child of the root has two children which is the maximum number of children a node can have. The blue nodes are the leaves of these tree. 

A tree may not necessarily have all the leaves at the same level e.g.

in the image on the right. In this image, there are still 3 leaves i.e. 2 blue nodes and the right child of the root.

The data in a binary tree is sorted, for instance, let's take a binary tree that stores integers in the nodes. On the left of the root, there will be integers smaller than the root and on the right there will be integers larger than the root. In other words, the left child of a node is smaller than itself and the right one is greater than itself.

In this image, the root contains integer 12. All the integers to the left of the root are smaller than 12. Similarly, the numbers to the right are larger than 12. In the second row, consider node 8. Which has left child containing number 5 (smaller than 8) and right child containing 9 (larger than 8).

Categories on the basis of arrangement of the nodes

Perfectly Balanced Tree : A tree which has equal number of nodes on the both sides of the root.

Skewed BST : A tree which doesn't have equal number of nodes on both sides of the root. A tree may be left or right skewed.

The height of a tree is
                                              h = lg(n+1) - 1

where,
h : height of the tree
lg : log base 2
n : number of nodes


In the next post, I'll explain a BST with a code example. 👍
Thank you for reading and if any questions, comment below! 😊😇

Read More