Binary Search Tree

Binary Tree:-

We use binary tree because it combines the advantages of array and linked list both and also overcome disadvantages of both.

Advantages/disadvantages for array:-

1) Search is fast in an ordered array as we can use the approach of doing search using binary operation.
2) Insertion is slow in an array if the array is sorted. We have to first reach the place where we need to insert and then move the other required values.
3) Same applies to deletion also like insertion.

Advantages/disadvantages for linkedlist:-

1) Search is slow as we have to go through every node even if the linked list is sorted.
2) Insertion & deletion are fast as if we find the correct place to insert/delete all we have to do is change some reference of the first and last element

Trees :- They have both. Fast search and fast insert , delete.

Many kinds of trees are there, but we are talking about binary trees.Some terminologies in tree data structure:-

1) Path :- going from one node to another node.
2) Root :- Node at top of the tree.There is only one root in a tree.
3) Parent :- which has a child.
4) Child
5) Leaf :- A node which doesn't have any child.
6) Subtree
7) Visiting :-

Tree is a binary tree if every node can have atmost 2 children.

Binary search tree :- A tree will be called binary search tree if it has atmost 2 children and left child is lesser than parent and right child bigger than parent.

Unbalanced tree :- which do not have both children.

Binary search tree in Java :-

We can think of binary search tree as collection of object connected to each other through reference and structured in a parent-child relationship following the principal of binary search tree mentioned above.

Below are the steps to create a binary search tree:-

Step1 :-

Create a class whose objects can be used as nodes.

public class Node{

int key;      //every node has a key value

String data;     //this variable can carry any data. This data can be some other object also like parent.

//Every node will carry reference to its child (left & right)

Node leftChild;

Node rightChild;

}

Step2 :-

Next step is to create a program where we can play with these nodes and join them using binary search tree principal. We will call this class as Tree.

public class Tree{

Node root; // We will create this class variable for the root.

//To create a tree and play with nodes, we will write 3 methods

/*

* 1) Find

* 2) Insert

* 3) Delete

* */

public Node find(int key){

if(root==null)

return null;

Node current = root;

while(current.key!=key){

if(current.key>key){

current = current.rightChild;

}else{

current = current.leftChild;

}

if(current==null) {

return null;

} 

}

return current;

}

//------------------------------------------------------//

public void insert (int key, String data){

//First of all we will create a node

Node newChild = new Node();

newChild.key=key;

newChild.data=data;

//If the root is empty, we will make new child node as root.

if(root==null)

root = newChild;

Node current = root;

Node parent=null;

while(true){

parent=current;

if(current.key>key){

current=current.leftChild;

if(current==null){

parent.leftChild=newChild;

return;

}

}else if(current.key<key){

current=current.rightChild;

if(current==null){

parent.rightChild=newChild;

return;

}

}

}

}

}