**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:3__Right 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:

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

b)Rebuild the heap after the deletion.

c)Place the deleted node in the output.

- 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_{1} P_{2} P_{3} P_{4} P_{5} P_{6} P_{7} P_{8 }P_{9 }P_{10}Priority: 5 4 3 4 5 5 3 2 1 5

__Solution:__

The processes are served in the sequence as :

P_{1} P_{5} P_{6} P_{10} P_{2} P_{4} P_{3} P_{7} P_{8} P_{9}

1) Priority queue heap

2) After the removal of P_{1}

3) When P_{5} is removed from heap

4) When P_{6} is removed from heap

5) After the removal of P_{10}(5)

6) When P_{2}(4) is removed

7) When P_{4}(4) is removed

8) When P_{3}(3) is removed

9) When P_{4}(3) is removed

10) When P_{5}(2) is removed