Data structures throw java lab programs part 4

                                  Data structures throw java part 4


AVL Tree
28. Write a Java program to perform the following operations
(a) Insertion into an AVL-tree
(b) Deletion from an AVL-tree  6. Search Trees

67
An AVL tree is a binary search tree in which the heights of the left and right subtrees of the root differ
at most 1 and in which the left and right subtrees are again AVL trees. Each node of an AVL tree is
associated with a balance factor that is the left subtree has height greater than, equal to, or less than
that of the right subtree.
Program 28: AVL tree operations (deletion is not implemented; left as an exercise)
class AVLTree
{
private class AVLNode
 {
 int data; // Data in the node
 AVLNode left; // Left child
 AVLNode right; // Right child
 int height; // Height

 AVLNode( int d ) // Constructors
 {
 this( d, null, null );
 }
 AVLNode( int d, AVLNode lt, AVLNode rt )
 {
 data = d;
 left = lt;
 right = rt;
 height = 0;
 }
 }

 private AVLNode root; // The tree root

 public AVLTree( ) // Construct the tree
 {
 root = null;
 }
 /*
 Insert into the tree; duplicates are ignored.
 x the item to insert.
 */
 public void insert( int x )
 {
 root = insert( x, root );
 }
 /*
 Find an item in the tree.
 x the item to search for.
 return true if x is found.
 */
 public boolean search( int x )
 {
 return search( x, root );
 } 68 Lab Manual Data Structures through Java
 public void makeEmpty( ) // Make the tree logically empty.
 {
 root = null;
 }
 /*
 Test if the tree is logically empty.
 return true if empty, false otherwise.
 */
 public boolean isEmpty( )
 {
 return root == null;
 }
 /*
 Print the tree contents in sorted order.
 */
 public void printTree( )
 {
 if( isEmpty( ) )
 System.out.println( "Empty tree" );
 else
 printTree( root );
 }

 /*
 method to insert into a subtree.
 x the item to insert.
 t the node that roots the subtree.
 return the new root of the subtree.
 */
 private AVLNode insert( int x, AVLNode t )
 {
 if( t == null )
 return new AVLNode( x, null, null );

 if( x < t.data )
 {
 t.left = insert( x, t.left );
 if( height( t.left ) - height( t.right ) == 2 )
 if( x < t.left.data )
 t = rotateLeft( t );
 else
 t = doubleLeft( t );
 }
 else if( x > t.data )
 {
 t.right = insert( x, t.right );
 if( height( t.right ) - height( t.left ) == 2 )
 if( x > t.right.data )
 t = rotateRight( t );
 else
 t = doubleRight( t );
 }
 else
 ; // Duplicate; do nothing
 t.height = Math.max( height( t.left ), height( t.right )) + 1;
 return t;  6. Search Trees

69
 }
 /*
method to find an item in a subtree.
 x is item to search for.
 t the node that roots the tree.
 return true if x is found in subtree.
 */
 private boolean search( int x, AVLNode t )
 {
 while( t != null )
 {
 if( x < t.data )
 t = t.left;
 else if( x > t.data )
 t = t.right;
 else
 return true; // Match
 }
 return false; // No match
 }
 /*
method to print the tree in sorted order.
 t the node that roots the tree.
 */
 private void printTree( AVLNode t ) // inorder traversal
 {
 if( t != null )
 {
 printTree( t.left );
 System.out.print( t.data + " ");
 printTree( t.right );
 }
 }
 private int height( AVLNode t ) // return height of node t, or -1, if null.
 {
 if( t == null ) return -1;
 else return t.height;
 }
 /*
 Rotate binary tree node with left child.
 For AVL trees, this is a single rotation.
 Update heights, then return new root.
 */
 private AVLNode rotateLeft( AVLNode node2 )
 {
 AVLNode node1 = node2.left;
 node2.left = node1.right;
 node1.right = node2;
 node2.height = Math.max(height(node2.left), height(node2.right))+1;
 node1.height = Math.max(height(node1.left), node2.height)+1;
 return node1;
 } 70 Lab Manual Data Structures through Java
 /*
 Rotate binary tree node with right child.
 For AVL trees, this is a single rotation.
 Update heights, then return new root.
 */
 private AVLNode rotateRight( AVLNode node1 )
 {
 AVLNode node2 = node1.right;
 node1.right = node2.left;
 node2.left = node1;
 node1.height = Math.max(height(node1.left), height(node1.right))+1;
 node2.height = Math.max(height(node2.right), node1.height)+1;
 return node2;
 }
 /*
 Double rotate binary tree node: first left child with its right child;
then node node3 with new left child.
 For AVL trees, this is a double rotation.
 Update heights, then return new root.
 */
 private AVLNode doubleLeft( AVLNode node3 )
 {
 node3.left = rotateRight( node3.left );
 return rotateLeft( node3 );
 }
 /*
 Double rotate binary tree node: first right child with its left child;
then node node1 with new right child.
 For AVL trees, this is a double rotation.
 Update heights, then return new root.
 */
 private AVLNode doubleRight( AVLNode node1 )
 {
 node1.right = rotateLeft( node1.right );
 return rotateRight( node1 );
 }
}
//////////////////// AVLTreeDemo.java /////////////////////////////
class AVLTreeDemo
{
 public static void main( String [] args )
 {
 AVLTree avl = new AVLTree();
 int[] a = {30,80,50,40,20,60,70,10,90,95};
 // build tree by successive insertions of 30, 80, 50, 40 ...
 for( int i = 0; i < a.length; i++ )
 avl.insert( a[i] );
 System.out.println( "\nAVL Tree nodes in sorted order:");
 avl.printTree();

 avl.insert( 15 );  6. Search Trees

71
 avl.insert( 85 );
 System.out.println( "\n\nAfter insertion of 15 & 85");
 avl.printTree();
 int item = 82; // search for an item
 if( avl.search( item ) )
 System.out.println( "\n\n" + item + " found");
 else
 System.out.println( "\n\n" + item + " not found");
 }
}
Output of this program is as follows:
AVL Tree nodes in sorted order:
10 20 30 40 50 60 70 80 90 95
After insertion of 15 & 85
10 15 20 30 40 50 60 70 80 85 90 95
82 not found
B-Tree
29. Write a Java program to perform the following operations:
(a) Insertion into a B-tree
(b) Deletion from a B-tree
A B-tree of order m is an m-way tree in which
1. All leaf nodes are on the same level.
2. All nodes, except the root and the leaves, have between [m/2] and m children.
3. The nonleaf nodes store up to m-1 keys to guide the searching; and these keys partition the keys in
the children in the fashion of a search tree.
4. The root is either a leaf or has between two and m children.
5. If a node has ‘d’ number of children, then it must have d-1 number of keys.
Program 29: B-Tree operations (deletion is not implemented; left as an exercise)
class BTree
{
 final int MAX = 4;
 final int MIN = 2;
15 21 35 42
 29
11 12 18 20 23 25 27 31 33 36 39 45 47 50 55
B-Tree of order 5 72 Lab Manual Data Structures through Java
 class BTNode // B-Tree node
 {
 int count;
 int key[] = new int[MAX+1];
 BTNode child[] = new BTNode[MAX+1];
 }

 BTNode root = new BTNode();
 class Ref // This class creates an object reference
 { int m; } // and is used to retain/save index values
 // of current node between method calls.
/*
 * New key is inserted into an appropriate node.
 * No node has key equal to new key (duplicate keys are not allowed.
 */
 void insertTree( int val )
 {
 Ref i = new Ref();
 BTNode c = new BTNode();
 BTNode node = new BTNode();
 boolean pushup;
 pushup = pushDown( val, root, i, c );
 if ( pushup )
 {
 node.count = 1;
 node.key[1] = i.m;
 node.child[0] = root;
 node.child[1] = c;
 root = node;
 }
 }
/*
 * New key is inserted into subtree to which current node points.
 * If pushup becomes true, then height of the tree grows.
 */
 boolean pushDown( int val, BTNode node, Ref p, BTNode c )
 {
 Ref k = new Ref();
 if ( node == null )
 {
 p.m = val;
 c = null;
 return true;
 }
 else
 {
 if ( searchNode( val, node, k ) )
 System.out.println("Key already exists.");
 if ( pushDown( val, node.child[k.m], p, c ) )
 {  6. Search Trees

73
 if ( node.count < MAX )
 {
 pushIn( p.m, c, node, k.m );
 return false;
 }
 else
 {
 split( p.m, c, node, k.m, p, c );
 return true;
 }
 }
 return false;
 }
 }
/*
 * Search through a B-Tree for a target key in the node: val
 * Outputs target node and its position (pos) in the node
 */
 BTNode searchTree( int val, BTNode root, Ref pos )
 {
 if ( root == null )
 return null ;
 else
 {
 if ( searchNode( val, root, pos ) )
 return root;
 else
 return searchTree( val, root.child[pos.m], pos );
 }
 }
/*
 * This method determines if the target key is present in
 * the current node, or not. Seraches keys in the current node;
 * returns position of the target, or child on which to continue search.
 */
 boolean searchNode( int val, BTNode node, Ref pos )
 {
 if ( val < node.key[1] )
 {
 pos.m = 0 ;
 return false ;
 }
 else
 {
 pos.m = node.count ;
 while ( ( val < node.key[pos.m] ) && pos.m > 1 )
 (pos.m)--;
 if ( val == node.key[pos.m] )
 return true;
 else
 return false;
 }
 }
/*
 * Inserts the key into a node, if there is room 74 Lab Manual Data Structures through Java
 * for the insertion
 */
 void pushIn( int val, BTNode c, BTNode node, int k )
 {
 int i ;
 for ( i = node.count; i > k ; i-- )
 {
 node.key[i + 1] = node.key[i];
 node.child[i + 1] = node.child[i];
 }
 node.key[k + 1] = val ;
 node.child[k + 1] = c ;
 node.count++ ;
 }

/*
 * Splits a full node into current node and new right child
 * with median.
 */
 void split( int val, BTNode c, BTNode node,
 int k, Ref y, BTNode newnode )
 {
 int i, mid; // mid is median
 if ( k <= MIN )
 mid = MIN;
 else
 mid = MIN + 1;
 newnode = new BTNode();
 for ( i = mid+1; i <= MAX; i++ )
 {
 newnode.key[i-mid] = node.key[i];
 newnode.child[i-mid] = node.child[i];
 }
 newnode.count = MAX - mid;
 node.count = mid;
 if ( k <= MIN )
 pushIn ( val, c, node, k );
 else
 pushIn ( val, c, newnode, k-mid ) ;
 y.m = node.key[node.count];
 newnode.child[0] = node.child[node.count] ;
 node.count-- ;
 }
 // calls display( )
 void displayTree()
 {
 display( root );
 }
 // displays the B-Tree
 void display( BTNode root )
 {  6. Search Trees

75
 int i;
 if ( root != null )
 {
 for ( i = 0; i < root.count; i++ )
 {
 display( root.child[i] );
 System.out.print( root.key[i+1] + " " );
 }
 display( root.child[i] );
 }
 }
} // end of BTree class
////////////////////////// BTreeDemo.java /////////////////////////////
class BTreeDemo
{
 public static void main( String[] args )
 {
 BTree bt = new BTree();
 /*
 * Refer Textbook, the section 13.3 B-Trees,
 * inserting into a B-Tree
 * Figure 13.30: Building a B-tree of order 5
 */
 int[] arr = { 11, 23, 21, 12, 31, 18, 25, 35, 29, 20, 45,
 27, 42, 55, 15, 33, 36, 47, 50, 39 };
 for ( int i = 0; i < arr.length; i++ )
 bt.insertTree( arr[i] );
 System.out.println("B-Tree of order 5:");
 bt.displayTree();
 }
 }
Output of this program is as follows:
 B-Tree of order 5:
 11 12 15 18 20 21 23 25 27 29 31 33 35 36 39 42 45 47 50 55 Dictionary
30. Write a Java program to implement all the functions of a dictionary (ADT) using Hashing.
An ADT that supports the operations insert, delete, and search is called a dictionary. Dictionaries are
found applications in the design of numerous algorithms. A dictionary is a collection of pairs of key
and element. No two pairs in a dictionary have the same key.
Consider a database of books maintained in a library system. When a user wants to check whether
a particular book is available, a search operation is called for. If the book is available and is issued to
the user, a delete operation can be performed to remove this book from the set of available books.
When the user returns the book, it can be inserted back into the set.
It is essential that we are able to support the above-mentioned operations as efficiently as possible
since these operations are performed quite frequently. A number of data structures have been
developed to realize a dictionary. These can be broadly divided into comparison methods and direct
access methods. Hashing is an example of the latter. Comparison methods fit into binary search trees.
Program 30(a): Dictionary operations using Hash tables
class Entry
{ public String key; // word
 public String element; // word meaning

 public Entry(String k, String e) // constructor
 {
key = k;
 element = e;
 }
}
class HashTable
{
 Entry[] hashArray; // array holds hash table
 int size; // table size
 int count; // current number of items in the table
 public HashTable(int s) // constructor
 {
 size = s;
 count = 0;
 hashArray = new Entry[size];
 }
 int hashFunc( String theKey ) // convert the string into a numeric key
 {
 int hashVal=0;
// convert the string into a numeric key
 for(int i = 0; i < theKey.length(); i++)
 hashVal = 37*hashVal + (int)theKey.charAt(i);

 hashVal = hashVal % size;
  7. Dictionary

77
 if(hashVal < 0 )
 hashVal = hashVal + size;

 return hashVal;
 }

 public void insert(String theKey, String str) // insert a record
 {
 if( !isFull() )
 {
 int hashVal = hashFunc(theKey); // hash the key

 // until empty cell or null,
 while(hashArray[hashVal] != null )

 {
 ++hashVal; // go to next cell
 hashVal %= size; // wraparound if necessary
 }

 hashArray[hashVal] = new Entry(theKey, str);
 count++; // update count
 }
 else
 System.out.println("Table is full");
 }

 public Entry delete(String theKey) // delete a record with the key
 {
 if( !isEmpty() )
 {
 int hashVal = hashFunc(theKey); // hash the key

 while(hashArray[hashVal] != null) // until empty cell,
 {
 if(hashArray[hashVal].key == theKey) // found the key?
 { Entry tmp = hashArray[hashVal]; // save item
 hashArray[hashVal] = null; // delete item
 count--;
 return tmp; // return item
 }
 ++hashVal; // go to next cell
 hashVal %= size; // wraparound if necessary
 }
 return null; // cannot find item
 }
 else
 System.out.println("Table is empty");
 return null;
 }
 public Entry search(String theKey) // find item with key
 {
 int hashVal = hashFunc(theKey); // hash the key

 while(hashArray[hashVal] != null) // until empty cell,
 {
 if(hashArray[hashVal].key == theKey) // found the key? 78 Lab Manual Data Structures through Java
 return hashArray[hashVal]; // yes, return item
 ++hashVal; // go to next cell
 hashVal %= size; // wraparound if necessary
 }
 return null; // cannot find item
 }
 public void displayTable()
 {
 System.out.println("<< Dictionary Table >>\n");

 for(int i=0; i<size; i++)
 {
 if(hashArray[i] != null )
 System.out.println( hashArray[i].key + "\t" +
 hashArray[i].element );
 }
 }
 public boolean isEmpty() // returns true, if table is empty
 {
 return count == 0;
 }
 public boolean isFull() // returns true, if table is full
 {
 return count == size;
 }
 public int currentSize()
 {
 return count;
 }
}

///////////////////////// Dictionary.java ////////////////////////////
class Dictionary
{
 public static void main(String[] args)
 {
 HashTable ht = new HashTable(19); // create hash table of size, 19

 // Insert the following items into hash table
 ht.insert("man", "gentleman");
 ht.insert("watch", "observe");
 ht.insert("hope", "expect");
 ht.insert("arrange", "put together");
 ht.insert("run", "sprint");
 ht.insert("wish", "desire");
 ht.insert("help", "lend a hand");
 ht.insert("insert", "put in");
 ht.insert("count", "add up");
 ht.insert("format", "arrangement");
 ht.displayTable(); // Display the table items 7. Dictionary

79
 // Search an item
 String word = "wish";
 Entry item = ht.search(word);
 if( item != null )
 System.out.println("found: " + item.key + "\t" + item.element);
 else
 System.out.println(word + " not found");
 // Delete an item
 word = "hope";
 item = ht.delete(word);
 if( item != null )
 System.out.println("deleted: " + item.key + "\t" + item.element);
 else
 System.out.println(word + " not found - no deletion");
 // Current number of items in the table
 System.out.println("size: " + ht.currentSize());

 }
}
Output:
<< Dictionary Table >>
insert put in
help lend a hand
man gentleman
watch observe
format arrangement
run sprint
wish desire
arrange put together
hope expect
count add up
found: wish desire
deleted: hope expect

size: 9

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)