SUMMER TRAINING Free Tutorials  Go To Your University  Placement Preparation 
Project Based Best Summer Training Courses in Jaipur
Join our Telegram Channel To take free Online Courses
0 like 0 dislike
123 views
in Examples, Exercises and Projects by (562 points)
edited by

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

  1. Binary tree
  2. Heap tree

1 Answer

0 like 0 dislike
by (562 points)
edited by
 
Best answer

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. 

tree

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 : 

                                     binary tree

To insert the key element is 11

                          insert element 11

Suppose to insert key element is 89

                                 tree

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:

binary search tree

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

                                    tree

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. 

                                     binary search tree

Case:3 N contains two child nodes. 

To delete 22 node from Binary search tree . Then, 

                                    binary search tree

Example:2

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

                                     binary tree

To delete 36

                                  binary search tree

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

                                 maximum heap tree

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. 

                           minimum heap tree

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:

     heap 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. 

  1. 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.

                        heap tree

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

                     step 2 a

Step:2(b) 

                  step 2 b

Step:3 continue the step:2 after selecting 98

                      step 3

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

                      final sorted list

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: P1 P2 P3 P4 P5 P6 P7 PPP10Priority:  5   4     3    4  5   5    3   2   1    5

Solution:

The processes are served in the sequence as :

P1 P5 P6 P10 P2 P4 P3 P7 P8 P9 

1) Priority queue heap

       Priority queue heap

2) After the removal of P1

    step 2

3) When P5 is removed from heap

   step 3

4) When P6 is removed from heap

               step 4

5) After the removal of P10(5)

                     step 5

6) When P2(4) is removed

                       step 6

7) When P4(4) is removed

                    step 7

8) When P3(3) is removed

                                     step 8

9) When P4(3) is removed

                                              step 9

10) When P5(2) is removed

                                                               step 10

Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...