Welcome to my blog

Wednesday, 29 November 2017

4 HEAP IMPLEMENTATION





4. HEAP IMPLEMENTATION

 AIM:
     To write a java program for heap implement
ALGORITHM:
  1. Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds a heap from a list in O(n) operations.
  2. Swap the first element of the list with the final element. Decrease the considered range of the list by one.
  3. Call the siftDown() function on the list to sift the new first element to its appropriate index in the heap.
  4. Go to step (2) unless the considered range of the list is one element.
  5. The buildMaxHeap() operation is run once, and is O(n) in performance. The siftDown() function is O(log n), and is called n times. Therefore, the performance of this algorithm is O(n + n log n) = O(n log n).

PROGRAM :
import java.util.Scanner;
class Heap
{
private int[] heapArray;
private int maxSize;
private int heapSize;
public Heap(int mx)
{
maxSize = mx;
heapSize = 0;
heapArray = new int[maxSize];
}
public boolean isEmpty()
{
return heapSize == 0;
}
public boolean insert(int ele)
{
if (heapSize + 1 == maxSize)
return false;
heapArray[++heapSize] = ele;
int pos = heapSize;
while (pos != 1 && ele > heapArray[pos/2])
{
heapArray[pos] = heapArray[pos/2];
pos /=2;
}
heapArray[pos] = ele;
return true;
}
public int remove()
{
int parent, child;
int item, temp;
if (isEmpty() )
throw new RuntimeException("Error : Heap empty!");
item = heapArray[1];
temp = heapArray[heapSize--];
parent = 1;
child = 2;
while (child <= heapSize)
{
if (child < heapSize && heapArray[child] < heapArray[child + 1])
child++;
if (temp >= heapArray[child])
break;
heapArray[parent] = heapArray[child];
parent = child;
child *= 2;
}
heapArray[parent] = temp;
return item;
}
public void displayHeap()
{
System.out.print("\nHeap array: ");
for(int i = 1; i <= heapSize; i++)
System.out.print(heapArray[i] +" ");
System.out.println("\n");
}
}
public class HeapTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Heap Test\n\n");
System.out.println("Enter size of heap");
Heap h = new Heap(scan.nextInt() )
char ch;
do
{
System.out.println("\nHeap Operations\n");
System.out.println("1. insert ");
System.out.println("2. delete item with max key ");
System.out.println("3. check empty");
boolean chk;
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
chk = h.insert( scan.nextInt() );
if (chk)
System.out.println("Insertion successful\n");
else
System.out.println("Insertion failed\n");
break;
case 2 :
System.out.println("Enter integer element to delete");
if (!h.isEmpty())
h.remove();
else
System.out.println("Error. Heap is empty\n");
break;
case 3 :
System.out.println("Empty status = "+ h.isEmpty());
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
h.displayHeap();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}


Posted by

3 RED-BLACK TREE IMPLEMENTATION



3 RED-BLACK TREE IMPLEMENTATION



AIM:
To write a java program to implement Red-Black Tree.
ALGORITHM:
1. Check whether tree is Empty.
2. If tree is Empty then insert the newNode as Root node with color Black and exit from the operation.
3. If tree is not Empty then insert the newNode as a leaf node with Red color.
4. If the parent of newNode is Black then exit from the operation.
5. If the parent of newNode is Red then check the color of parent node's sibling of newNode.
6. If it is Black or NULL node then make a suitable Rotation and Recolor it.
7. If it is Red colored node then perform Recolor and Recheck it. Repeat the same until tree becomes Red Black Tree.



PROGRAM:
import java.util.Scanner;
class RedBlackNode
{
RedBlackNode left, right;
int element;
int color;
public RedBlackNode(int theElement)
{
this( theElement, null, null );
}
public RedBlackNode(int theElement, RedBlackNode lt, RedBlackNode rt)
{
left = lt;
right = rt;
element = theElement;
color = 1;
}
}
class RBTree
{
private RedBlackNode current;
private RedBlackNode parent;
private RedBlackNode grand;
private RedBlackNode great;
private RedBlackNode header;
private static RedBlackNode nullNode;
static
{
nullNode = new RedBlackNode(0);
nullNode.left = nullNode;
nullNode.right = nullNode;
}
static final int BLACK = 1;
static final int RED   = 0;
public RBTree(int negInf)
{
header = new RedBlackNode(negInf);
header.left = nullNode;
header.right = nullNode;
}
public boolean isEmpty()
{
return header.right == nullNode;
}
public void makeEmpty()
{
header.right = nullNode;
}
public void insert(int item )
{
current = parent = grand = header;
nullNode.element = item;
while (current.element != item)
{
great = grand;
grand = parent;
parent = current;
current = item < current.element ? current.left : current.right;
if (current.left.color == RED && current.right.color == RED)
handleReorient( item );
}
if (current != nullNode)
return;
current = new RedBlackNode(item, nullNode, nullNode);
if (item < parent.element)
parent.left = current;
else
parent.right = current;
handleReorient( item );
}
private void handleReorient(int item)
{
current.color = RED;
current.left.color = BLACK;
current.right.color = BLACK;
if (parent.color == RED)
{
grand.color = RED;
if (item < grand.element != item < parent.element)
parent = rotate( item, grand );
current = rotate(item, great );
current.color = BLACK;
}
header.right.color = BLACK;
}
private RedBlackNode rotate(int item, RedBlackNode parent)
{
if(item < parent.element)
return parent.left = item < parent.left.element ? rotateWithLeftChild(parent.left) : rotateWithRightChild(parent.left) ;
else
return parent.right = item < parent.right.element ? rotateWithLeftChild(parent.right) : rotateWithRightChild(parent.right);
}
private RedBlackNode rotateWithLeftChild(RedBlackNode k2)
{
RedBlackNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
private RedBlackNode rotateWithRightChild(RedBlackNode k1)
{
RedBlackNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
public int countNodes()
{
return countNodes(header.right);
}
private int countNodes(RedBlackNode r)
{
if (r == nullNode)
return 0;
else
{
int l = 1;
l += countNodes(r.left);
l += countNodes(r.right);
return l;
}
}
public boolean search(int val)
{
return search(header.right, val);
}
private boolean search(RedBlackNode r, int val)
{
boolean found = false;
while ((r != nullNode) && !found)
{
int rval = r.element;
if (val < rval)
r = r.left;
else if (val > rval)
r = r.right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
public void inorder()
{
inorder(header.right);
}
private void inorder(RedBlackNode r)
{
if (r != nullNode)
{
inorder(r.left);
char c = 'B';
if (r.color == 0)
c = 'R';
System.out.print(r.element +""+c+" ");
inorder(r.right);
}
}
public void preorder()
{
preorder(header.right);
}
private void preorder(RedBlackNode r)
{
if (r != nullNode)
{
char c = 'B';
if (r.color == 0)
c = 'R';
System.out.print(r.element +""+c+" ");
preorder(r.left);
preorder(r.right);
}
}
public void postorder()
{
postorder(header.right);
}
private void postorder(RedBlackNode r)
{
if (r != nullNode)
{
postorder(r.left);
postorder(r.right);
char c = 'B';
if (r.color == 0)
c = 'R';
System.out.print(r.element +""+c+" ");
}
}
}
public class RedBlackTree
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of RedBlack Tree */
RBTree rbt = new RBTree(Integer.MIN_VALUE);
System.out.println("Red Black Tree Test\n");
char ch;
do
{
System.out.println("\nRed Black Tree Operations\n");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. count nodes");
System.out.println("4. check empty");
System.out.println("5. clear tree");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
rbt.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ rbt.search( scan.nextInt() ));
break;
case 3 :
System.out.println("Nodes = "+ rbt.countNodes());
break;
case 4 :
System.out.println("Empty status = "+ rbt.isEmpty());
break;
case 5 :
System.out.println("\nTree Cleared");
rbt.makeEmpty();
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
System.out.print("\nPost order : ");
rbt.postorder();
System.out.print("\nPre order : ");
rbt.preorder();
System.out.print("\nIn order : ");
rbt.inorder();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}

Posted by

2. IMPLEMENTATION OF BINARY SEARCH TREE



2. IMPLEMENTATION OF BINARY SEARCH TREE




AIM:

      To write a java program for implementing Binary Search Tree.
ALGORITHM:
1.      Read the search element from the user
2.      Compare, the search element with the value of root node in the tree.
3.      If both are matching, then display "Given node found!!!" and terminate the function
4.      If both are not matching, then check whether search element is smaller or larger than that node value.
5.      If search element is smaller, then continue the search process in left subtree.
6.      If search element is larger, then continue the search process in right subtree.
7.      Repeat the same until we found exact element or we completed with a leaf node
8.      If we reach to the node with search value, then display "Element is found" and terminate the function.
9.      If we reach to a leaf node and it is also not matching, then display "Element not found" and terminate the function.



 PROGRAM :
public class BinarySearchTree
{
public static  Node root;
public BinarySearchTree()
{
this.root = null;
}

public boolean find(int id)
{
Node current = root;
while(current!=null)
{
if(current.data==id)
{
return true;
}
else if(current.data>id)
{
current = current.left;
}
Else
{
current = current.right;
}
}
return false;
}
public boolean delete(int id)
{
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.data!=id)
{
parent = current;
if(current.data>id)
{
isLeftChild = true;
current = current.left;
}
Else
{
isLeftChild = false;
current = current.right;
}
if(current ==null)
{
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if(current.left==null && current.right==null)
{
if(current==root)
{
root = null;
}
if(isLeftChild ==true)
{
parent.left = null;
}
Else
{
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.right==null)
{
if(current==root)
{
root = current.left;
}
else if(isLeftChild)
{
parent.left = current.left;
}
Else
{
parent.right = current.left;
}
}
else if(current.left==null)
{
if(current==root)
{
root = current.right;
}
else if(isLeftChild)
{
parent.left = current.right;
}
Else
{
parent.right = current.right;
}
}
else if(current.left!=null && current.right!=null)
{
//now we have found the minimum element in the right sub tree
Node successor           = getSuccessor(current);
if(current==root)
{
root = successor;
}
else if(isLeftChild)
{
parent.left = successor;
}
Else
{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}

public Node getSuccessor(Node deleleNode)
{
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.right;
while(current!=null)
{
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
//                      successsorParent
if(successsor!=deleleNode.right)
{
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public void insert(int id)
{
Node newNode = new Node(id);
if(root==null)
{
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true)
{
parent = current;
if(id<current.data)
{
current = current.left;
if(current==null)
{
parent.left = newNode;
return;
}
}
Else
{
current = current.right;
if(current==null)
{
parent.right = newNode;
return;
}
}
}
}
public void display(Node root)
{
if(root!=null)
{
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public static void main(String arg[])
{
BinarySearchTree b = new BinarySearchTree();
b.insert(3);b.insert(8);
b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
b.insert(20);b.insert(25);b.insert(15);b.insert(16);
System.out.println("Original Tree : ");
b.display(b.root);
System.out.println("");
System.out.println("Check whether Node with value 4 exists : " + b.find(4));
System.out.println("Delete Node with no children (2) : " + b.delete(2));
b.display(root);
System.out.println("\n Delete Node with one child (4) : " + b.delete(4));
b.display(root);
System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));
b.display(root);
}
}

class Node
{
int data;
Node left;
Node right;
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
}

 
Posted by
Subscribe to: Comments (Atom)