Tuesday 16 June 2020
Friday 13 July 2018
01:59:00
algorithms, bst, C++, Class, code, Concepts, heap, heapify, maxheap, minheap, minheapify, search algorithms, searchalgo
No comments
What is a Binary Heap?
A heap is always (logically) a complete binary tree. It has these basic properties:- All levels are full except possibly the last level
- If the last level is not full, it is left justified
- It has the either of these two Heap properties in case of
- Min Heap: Each Parent key <= Both Children Keys (Root is minimum)
- Max Heap: Each Parent key >= Both Childen Keys (Root is maximum)
Min Heap
As stated above, min heap will have minimum of all the keys at the top due its heap property.
For instance, look at the tree in Fig(1.1): the root node which contains 2 is the smallest. Similarly, all the elements on level 2 are smaller then those on level 3 and so on. Observe that there is no order between the left and right children of a key i.e. it doesn't matter if left child > right child or vice versa. They are just compared to their parent key (min heap property).
 |
| Fig: 1.1 |
Now, to move onto the code of the Min Heap:
There are three basic functions:
int lchild(int i) //returns the index
{
return (2 * i);
}
int rchild(int i)
{
return ((2 * i) + 1);
}
int parent(int i)
{
return (i / 2);
}
I have implemented Min Heap using Templates. Also, I have used the default Vector class to stored keys.
template <class T>
class minHeap {
private:
vector <T> h; //using default vector class
....
}
To insert an element,
void insert(const T & temp)
{
h.push_back(temp); //default insert method for the vector class
int i = size();
while (i > 1 && h[parent(i)].fc > h[i].fc) //Not root && parent & child comparison
{
swap(h[parent(i)], h[i]);
i = parent(i);
}
}
void deMin()
{
if (size() > 0)
{
swap(h[1], h[size()]);
h.pop_back(); //deleting the last element
minheapify(1);
}
}
After deletion, we shall have to MinHeapify the whole tree so that the order is mainted.
void minheapify(int i ) //percolate down
{
int lc = lchild(i); //left child index
int rc = rchild(i); //right child index
int imin = i; //min index
if (lc < size() && h[lc].fc < h[imin].fc)
imin = lc;
if (rc < size() && h[rc].fc < h[imin].fc)
imin = rc;
if (i != imin) //parents/current isn't imin itself
{
swap(h[i], h[imin]);
minheapify(imin); //recursive call
}
}
You can create helper functions of your own to getNode(), find() and so on. I have provided the basic functions :P
Thank you for reading! I hope it helped! :)
If any questions, comment below!
01:00:00
book sugesstions, books, C++, c++ book, Class, Concepts, headfirst, java, java book, Simple Programs, suggestions, Tips & Tricks
No comments
Hello Everyone!
This is just a short post to hand out some suggestions about books. If you are studying a programmatic language, you may find a lot of books in the market which cover all the details of the language and from basic to complex all of the concepts.
However, I personally recommend HeadFirst books which are great if you are a beginner at language and complex books with lots of boring theories and background history are tiresome for you. You will find books on C++, C#, Java, JavaScript, Html, SQL and many other languages.
There are also books on Design Patterns and Algorithms. The content and concept is explained in easy to understand and interesting way for you to have a great learning time. There are exercises and practices in the book too. The books cover all the basic and common concepts about the languages but if you want more details and advanced knowledge, you can refer to those complex books after acquiring basic concepts. :P
This is just a short post to hand out some suggestions about books. If you are studying a programmatic language, you may find a lot of books in the market which cover all the details of the language and from basic to complex all of the concepts.
However, I personally recommend HeadFirst books which are great if you are a beginner at language and complex books with lots of boring theories and background history are tiresome for you. You will find books on C++, C#, Java, JavaScript, Html, SQL and many other languages.There are also books on Design Patterns and Algorithms. The content and concept is explained in easy to understand and interesting way for you to have a great learning time. There are exercises and practices in the book too. The books cover all the basic and common concepts about the languages but if you want more details and advanced knowledge, you can refer to those complex books after acquiring basic concepts. :P
" The more you know, the more you grow. :) "
Sunday 21 January 2018
05:24:00
algorithms, binary search tree, bst, C++, Class, code, Concepts, Remove in BST, Search, search algorithms, searchalgo, Simple Programs
No comments
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:
(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! :)
Monday 15 January 2018
02:27:00
algorithms, binary search tree, bst, C++, Class, code, Concepts, Search, searchalgo, Simple Programs
No comments
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;
}
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;
}
{
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 *********************/
//************* 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);
}
}
{
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;
}
Thank you for reading and comment below if you have any questions! :)
Tuesday 9 January 2018
07:28:00
algorithms, binary search tree, bst, C++, Concepts, Search, search algorithms, searchalgo
No comments
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.
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! 😊😇
