Source Code

Get programs to develop you own applications.

AVL Tree

Posted by mohammedmoulana on March 26, 2012

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.

AVL tree operations

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 );
}

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;

}
/*
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;
}

/*
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 );

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

About these ads

4 Responses to “AVL Tree”

  1. Eleazar said

    excuse me, i got the followin error while compiling:

    Exception in thread “main” java.lang.RuntimeException: Uncompilable source code – incompatible types
    required: boolean
    found: int
    at aavl.AVLTree.insert(AVLTree.java:105)
    at aavl.AVLTree.insert(AVLTree.java:46)
    at aavl.AVLTreeDemo.main(AVLTreeDemo.java:20)
    Java Result: 1

    do you know what can I do? :S .. thank you and greetings :S

  2. Eleazar said

    Forget about it :) i have solved the problem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 443 other followers

%d bloggers like this: