What do you mean by binary trees and heap tree in Data Structure and Algorithm?

Question

Here, in this article,  you will get to know more about 

1. Binary tree
2. Heap tree

Answer 1

Binary Search Tree(BST) 

• A binary  search tree , it may be empty binary tree if it not empty. Then, following are the properties:
• Each node contains a key value and that keys are distinct(diffferent) to each other. 
• The keys in the left subtree are smaller than the root node. 
• The keys in the right subtree are greater or higher than the root node. 

Examples

1) A binary search tree with numeric data. 

2) A binary search tree with alphabetic data. 

Operations on binary search tree

• Searching data
• Inserting data
• Deleting data
• Traversing the data. 

Searching

• To perform searching operation , there are following three conditions :
• Input:Key is the that element, we will search in the binary search tree. 
• Condition(1) :If ROOT==KEY then searching is successfull and the item or data element is presented in root node. 
• Condition(2) :If KEY<ROOT then , searching operation go to left subtree of the root node. 
• Condition(3) :If KEY>ROOT then, searching operation go to right subtree of a root node. 

Example:

Find out the key element 45 presented in the above binary search tree. 

Solution

Step:1 if key==root (45==50)  false 

Then if (key<root ) True(45<50) 

Then go to left subtree of root node. 

Step:2 Root of the left subtree is 30≠key value

if (key<root) false

then if(key>root) true

go to right subtree of 30 root node. 

Step:3Right sub-tree of root node is equal to the key element is 45.

The searching operation completed successfully. 

Insertion

• To perform insertion, first we use search operation to find out the key element is presented in binary search tree. 
• Do not insert the key element in binary search tree. 
• If key is not present, performs insertion operation.

The given binary tree is : 

                                     

To insert the key element is 11

                          

Suppose to insert key element is 89

                                 

Deletion

• To perform deletion operation on Binary Search Tree, first perform the searching operation and find out the key element is presented or not presented in binary search tree. 
• Mainly three cases are used to delete the node N from the binary search tree. 
• Case:1 N is a leaf node. 
• N contains leaf node in the tree, then easily perform the deletion operation. 

Eg:

To delete 23 node from binary search tree. The node is leaf node

                                    

N have only one child node. 

• Case:2 To delete 50 data element from BST. 50  node contains only one child i.e. right child. 

After deleting 50 node. Then, the child node is 50 goes to the index position of the 50 node. 

                                     

Case:3 N contains two child nodes. 

To delete 22 node from Binary search tree . Then, 

                                    

Example:2

To delete 36,data element from the BST to contains  child nodes and also grand child nodes , then remove the node. 

                                     

To delete 36

                                 

Traversal

• Traversal operations on  binary search tree are same as traversal operations on binary tree. They are as follows:
• preorder
• inorder
• postorder

---

Binary sorted tree:

• The inorder traversal on a binary search tree will give the sorted order of data in ascending order. 
• This method of sorting is known as binary sort tree and this is why binary search tree is also termed as a binary sorted tree. 

Applications of binary search trees

• The binary search tree is one of the most important data structures and it has a large number of application. 
• It can be used in sorting method. 
• Used in the searching method 
• Can be used to define other data structures, for example B-tree. 

  ---

Heap trees:

Suppose it is a complete binary tree. It is called as heap tree,if it satisfies the follwing properties:

(i) For each node N in H, the value at N is greater than or equal to the value of each of the children of N. 

(ii) In otherwords, N has a value which is greater than or equal to the value of every successor of N. 

Maximum heap:

• In the heap tree  defined above is called as maximum heap or max. heap

                                 

Min heap or minimum heap:

• In this, any node N has a value less than or equal to the value of any of the successor of N. 

                           

Representation of a heap tree

A heap tree can be represented by using an array or a linked structure. But a single array representation has certain advantages over linked representation. 

Example:Single array representation  of heap(min) tree:

     

Advantages of Array representation

• Heap tree is a complete binary tree, there will be no wastage of array. Space between the two non-null entries, if there are any null entries, there are only at the tail of the array. 
• We do not have to maintain any links of child nodes. 
• Major advantage is from a node that we can go in both directions, i. e., towards its ancestors and towards its successors as well. 

Operations on a heap tree:

The major operations required to be performed on a heap tree are:

• Insertion 
• Deletion
• Merging

Applications of heap trees

There are two known main applications of heap trees. 

a) Sorting:

Any kind of data can be sorted either in ascending order or in descending order using a heap tree. This actually consists of the following steps:

1. Build a heap tree with the given set of data. 
2. a)Delete the root node from the heap

b)Rebuild the heap after the deletion. 

c)Place the deleted node in the output. 

3. Continue the step:2  until the heap is empty. 

Example:The case of sorting the following set of data in ascending order. 

33,14,65,02,76,69,59,85,47,99,98

Solution:

Step:1 A heap tree from a given set of data.

                        

Step:2(a)   deleting the root and last node from the heap

                     

Step:2(b) 

                  

Step:3 continue the step:2 after selecting 98

                      

Step:4  sorted list when the heap tree is empty.

                     

b)Priority queue implementation using a heap tree:

• Priority queue can be implemented using a circular array , linked list, etc. 
• Another  simplified implementation is possible using a heap tree, the heap , however can be represented using an array. 
• This implementation is therefore free from the complexities of the circular array and the linked list but gets the advantage of simplicity of the array. 
• It may be recalled that heap trees allow the duplicity of the data in them. 
• Elements associated with their priority values are to be stored in the form of a heap tree, which can be formed based on their priority values. 
• The top priority element that has to be processed first is at the root, so it can be deleted and the heap can be  rebuilt to get the next element to be processed and so on . 

Example:As an illustration, consider the following process with their priorites:

Process: P₁ P₂ P₃ P₄ P₅ P₆ P₇ P₈ P₉ P₁₀Priority:  5   4     3    4  5   5    3   2   1    5

Solution:

The processes are served in the sequence as :

P₁ P₅ P₆ P₁₀ P₂ P₄ P₃ P₇ P₈ P₉ 

1) Priority queue heap

       

2) After the removal of P₁

    

3) When P₅ is removed from heap

   

4) When P₆ is removed from heap

               

5) After the removal of P₁₀(5)

                     

6) When P₂(4) is removed

                       

7) When P₄(4) is removed

                    

8) When P₃(3) is removed

                                     

9) When P₄(3) is removed

                                              

10) When P₅(2) is removed