Building Binary Search Tree in Java - Insertion

In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties: [from wiki]

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Node Structure.
Each node has left-child, right-child, height, value, and parent member. In fact, the parent member is not necessary, but it is added for easy understanding of binary tree, and especially when deleting node from the tree. With children of node, the parent of a node can be found easily. (see BinarySearchTree.java)

The setHeight() and getHeight() methods are not necessay too for binary search tree. They need for balanced tree such as AVL tree and Red-Black Tree.

download Node.java

public class Node {
private Node leftChild;
private Node rightChild;
private Node parent;
private int value;
private int height;

public Node(Node p, Node l, Node r, int v, int h) {
leftChild = l;
rightChild = r;
value = v;
height = h;
parent = p;
}

public Node(int v, Node p) {
this(p, null, null, v, 0);

}
public Node (int v) {
this(null, null, null, v, 0);
}

public boolean isBalanced() {
if(leftChild == null && rightChild == null)
return true;
else if (leftChild == null)
return rightChild.getHeight() == 0;
else if (rightChild == null)
return leftChild.getHeight() == 0;

return Math.abs(leftChild.getHeight()- rightChild.getHeight()) < 2;
}

public void setParent(Node parent) {
this.parent = parent;
}

public Node getParent() {
return parent;
}

public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}

public Node getLeftChild() {
return leftChild;
}

public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}

public Node getRightChild() {
return rightChild;
}

public void setValue(int value) {
this.value = value;
}

public int getValue() {
return value;
}

public void setHeight() {
if(leftChild == null && rightChild == null)
height = 0;
else if (leftChild == null)
height = rightChild.getHeight() + 1;
else if (rightChild == null)
height = leftChild.getHeight() + 1;
else
height= leftChild.getHeight() >= rightChild.getHeight()?
leftChild.getHeight() + 1: rightChild.getHeight() +1;
}

public int getHeight() {
setHeight();
return height;
}
}

Building BST, inserting node.
Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.

download BinarySearchTree.java

public class BinarySearchTree {
private Node root;

public BinarySearchTree(Node root) {
this.root = root;
}
public BinarySearchTree() {
this.root = (Node)null;
}

private void setRoot(Node r) {
root = r;
}

private Node getRoot() {
return root;
}

public Node findParent(int value, Node node) {
if (node.getValue() == value)
return (Node)null; // root itself
else if(node.getLeftChild() != null && node.getLeftChild().getValue() == value)
return node;
else if(node.getRightChild() != null && node.getRightChild().getValue() == value)
return node;
else if (node.getValue() > value)
return findParent(value, node.getLeftChild());
else
return findParent(value, node.getRightChild());
}

public Node insertNode(int value) {
return insertNode(value, null, null);
}

public Node insertNode(int value, Node node, Node parent) {
if(node == (Node)null)
node = new Node(parent, null, null, value, 0);
else if (value < node.getValue())
node.setLeftChild(insertNode(value,node.getLeftChild(), node));
else if (value > node.getValue())
node.setRightChild(insertNode(value, node.getRightChild(), node));
node.setHeight();
return node;
}

/* in-order traversal for showing inside of tree */
public void traverseInOrder(Node node) {
if(node.getLeftChild() != (Node)null)
traverseInOrder(node.getLeftChild());
System.out.print("Value: [" + node.getValue() + "], Height: [" +
node.getHeight() + "], Parent: [");

Node n = findParent(node.getValue(), getRoot());
if(n == (Node)null)
System.out.println("root]");
else
System.out.println(n.getValue() + "]");

if(node.getRightChild()!= (Node)null)
traverseInOrder(node.getRightChild());
}

public static void main(String[] args) {
TestCode tree = new TestCode();
Node root = new Node(5);
tree.setRoot(root);
int[] input = {7, 9, 3, 1, 2, 8, 10, 6};

for (int i = 0; i<input.length; i++)
tree.setRoot(tree.insertNode(input[i], root, null));

tree.traverseInOrder(tree.getRoot());
}
}

Read More [...]

Posted in Algorithm, Binary Search, Binary Search Tree, C, Insert Binary Tree, Java, Programming, Search Algorithm, Tree, Tree Structure

In-Place Quick Sort of An Integer Array

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists. [From wiki]
The steps are:

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

Time Complexity: for n entries,
   Θ(n log(n)) in the average case.
   Θ(n^2) in the worst case.

Space Complexity:
   Θ(log(n)) in the average case.
   Θ(n log(n)) when the input array is very large. the space is needed for storing variables like left, right and pivot. .

Java code for in-place Quick Sort here:

public void quickSort(int input[], int left, int right) {
int pivot = input[(left +right)/2];
int i = left, j = right;
int temp;


while (i <= j){
while(input[i] < pivot && i < right)
i++;
while(input[j] > pivot && j > left)
j--;

if (i <= j ) {
temp = input[j];
input[j] = input[i];
input[i] = temp;
i++; j--;
}
}

if (left <j)
quickSort(input, left, j);
if (i < right)
quickSort(input, i, right);
}

Read More [...]

Posted in Java, Programming, qsort, Quick Sort, quicksort, Search Algorithm, sorting algorithm

Binary Search of an Integer Array

Binary Search Program. It's written in Java, but it's almost same as C program. All you need is just use 'sizeOf()' macro (fuction) to get the length of array.

public static void main(String[] args) {
int input[] = {1,3,5,6,7,8,9,10,11};
                int query = 3;
System.out.println(query + " is in input[" + binarySearch(input, query) + "].");
}

public static int binarySearch(int tree[], int query) {
int beg = 0;
int end = tree.length-1;
int mid = (beg+end)/2;

for(int i=1; mid >=0 ;i++) {
System.out.println(i+ "th try - index:" + (mid + 1) + "/" + tree.length);
if(tree[mid] == query)
break;
else if(tree[mid] > query)
end = mid - 1;
else
beg = mid +1;

mid = (beg + end)/2;
   if (beg >= med)
      mid = -1;
}
return mid;
}

Read More [...]

Posted in Binary Search, C, Java, Programming, Search Algorithm