1.11M Members

Recursive AVL Binary Search Tree

 
2
 

This code demonstrates AVL insertion and deletion. The code was originally written in C by myself a little while back for a tutorial. The translation to Java was fairly trivial, and to add a little excitement I even threw in a few generics. Yes, I'm aware of this line:

tree.data = heir.data;

But thank you for your concern.

There are two significant differences between the C code and the Java code. First, In Java, boolean values cannot be used in integral context. Therefore my yummy design in C is a little bitter in Java because I had to either use the conditional operator to get my logical NOT, or duplicate a lot of code for symmetrical cases. Second, because Java Generics don't lend themselves well to arrays, I chose to use the ArrayList collection rather than a built in array for the links as I did in C.

All in all, a mildly interesting diversion, and now Daniweb has an AVL implementation to its name. :-)

package scratchpad;

import java.io.*;
import java.util.*;

class AVLNode<T extends Comparable> {
  T data;
  int balance;
  ArrayList<AVLNode<T>> link;
  
  AVLNode ( T data ) {
    this.data = data;
    balance = 2;
    link = new ArrayList<AVLNode<T>> ( 2 );
    link.add ( null ); link.add ( null );
  }
}

class AVLTree {
  private static boolean new_depth;
  
  private static<T extends Comparable>
  AVLNode<T> single_rotate ( AVLNode<T> tree, int dir ) {
    int not_dir = dir == 0 ? 1 : 0;
    AVLNode<T> save = tree.link.get ( dir );
    
    tree.link.set ( dir, save.link.get ( not_dir ) );
    save.link.set ( not_dir, tree );
    
    return save;
  }
  
  private static<T extends Comparable>
  AVLNode<T> double_rotate ( AVLNode<T> tree, int dir ) {
    int not_dir = dir == 0 ? 1 : 0;
    AVLNode<T> save = tree.link.get ( dir ).link.get ( not_dir );
    
    tree.link.get ( dir ).link.set ( not_dir, save.link.get ( dir ) );
    save.link.set ( dir, tree.link.get ( dir ) );
    tree.link.set ( dir, save );
    
    save = tree.link.get ( dir );
    tree.link.set ( dir, save.link.get ( not_dir ) );
    save.link.set ( not_dir, tree );
    
    return save;
  }
  
  private static<T extends Comparable>
  void fix_balance_factors ( AVLNode<T> tree, int dir ) {
    int not_dir = dir == 0 ? 1 : 0;
    
    if ( tree.link.get ( dir ).link.get ( not_dir ).balance == dir ) {
      tree.balance = 2;
      tree.link.get ( dir ).balance = not_dir;
    }
    else if ( tree.link.get ( dir ).link.get ( not_dir ).balance == not_dir ) {
      tree.balance = dir;
      tree.link.get ( dir ).balance = 2;
    }
    else {
      tree.balance = tree.link.get ( dir ).balance = 2;
    }
    
    tree.link.get ( dir ).link.get ( not_dir ).balance = 2;
  }
  
  private static<T extends Comparable>
  AVLNode<T> rebalance_insert ( AVLNode<T> tree, int dir ) {
    int not_dir = dir == 0 ? 1 : 0;
    
    if ( tree.balance == dir ) {
      if ( tree.link.get ( dir ).balance == dir ) {
        tree.link.get ( dir ).balance = 2;
        tree.balance = 2;
        
        tree = single_rotate ( tree, dir );
      }
      else {
        fix_balance_factors ( tree, dir );
        
        tree = double_rotate ( tree, dir );
      }
      
      new_depth = false;
    }
    else if ( tree.balance == not_dir ) {
      tree.balance = 2;
      new_depth = false;
    }
    else {
      tree.balance = dir;
    }
    
    return tree;
  }
  
  private static<T extends Comparable>
  AVLNode<T> rebalance_remove ( AVLNode<T> tree, int dir ) {
    int not_dir = dir == 0 ? 1 : 0;
    
    if ( tree.balance == dir ) {
      tree.balance = 2;
    }
    else if ( tree.balance == not_dir ) {
      if ( tree.link.get ( not_dir ).balance == not_dir ) {
        tree.link.get ( not_dir ).balance = 2;
        tree.balance = 2;
        
        tree = single_rotate ( tree, not_dir );
      }
      else if ( tree.link.get ( not_dir ).balance == 2 ) {
        tree.link.get ( not_dir ).balance = dir;
        
        tree = single_rotate ( tree, not_dir );
      }
      else {
        fix_balance_factors ( tree, not_dir );
        
        tree = double_rotate ( tree, not_dir );
      }
      
      new_depth = false;
    }
    else {
      tree.balance = not_dir;
      new_depth = false;
    }
    
    return tree;
  }

  private static<T extends Comparable>
  AVLNode<T> insert_r ( AVLNode<T> tree, T data ) {
    if ( tree == null ) {
      tree = new AVLNode<T> ( data );
      new_depth = true;
    }
    else {
      int dir = data.compareTo ( tree.data ) > 0 ? 1 : 0;
      
      tree.link.set ( dir, insert ( tree.link.get ( dir ), data ) );
      
      if ( new_depth ) {
        tree = rebalance_insert ( tree, dir );
      }
    }
    
    return tree;
  }
  
  private static<T extends Comparable>
  AVLNode<T> remove_r ( AVLNode<T> tree, T data ) {
    if ( tree == null ) {
      new_depth = false;
    }
    else if ( data.compareTo ( tree.data ) == 0 ) {
      if ( tree.link.get ( 0 ) != null && tree.link.get ( 1 ) != null ) {
        AVLNode<T> heir = tree.link.get ( 0 );
        
        while ( heir.link.get ( 1 ) != null ) {
          heir = heir.link.get ( 1 );
        }
        
        tree.data = heir.data;
        
        tree.link.set ( 0, remove_r ( tree.link.get ( 0 ), tree.data ) );
        
        if ( new_depth ) {
          tree = rebalance_remove ( tree, 0 );
        }
      }
      else {
        AVLNode<T> save = tree;
        
        tree = tree.link.get ( tree.link.get ( 0 ) == null ? 1 : 0 );
        
        new_depth = true;
      }
    }
    else {
      int dir = data.compareTo ( tree.data ) > 0 ? 1 : 0;
      
      tree.link.set ( dir, remove_r ( tree.link.get ( dir ), data ) );
      
      if ( new_depth ) {
        tree = rebalance_remove ( tree, dir );
      }
    }
    
    return tree;
  }
  
  public static<T extends Comparable>
  AVLNode<T> insert ( AVLNode<T> tree, T data ) {
    new_depth = false;
    return insert_r ( tree, data );
  }
  
  public static<T extends Comparable>
  AVLNode<T> remove ( AVLNode<T> tree, T data ) {
    new_depth = false;
    return remove_r ( tree, data );
  }

  public static<T extends Comparable>
  void structure ( AVLNode<T> tree, int level ) {
    int i;
    
    if ( tree == null ) {
      for ( i = 0; i < level; i++ ) {
        System.out.print ( "\t" );
      }
      System.out.println();
      
      return;
    }
    
    structure ( tree.link.get ( 1 ), level + 1 );
    
    for ( i = 0; i < level; i++ ) {
      System.out.print ( "\t" );
    }
    System.out.println ( tree.data + "(" + tree.balance + ")" );
    
    structure ( tree.link.get ( 0 ), level + 1 );
  }
}

public class Main {
  public static void main ( String[] args ) throws IOException {
    AVLNode<Integer> tree = null;
    
    for ( int i = 0; i < 10; i++ ) {
      tree = AVLTree.insert ( tree, i );
      
      AVLTree.structure ( tree, 0 );
      System.out.println ( "\n------------------------" );
      
      System.in.read();
    }
    
    for ( int i = 0; i < 10; i++ ) {
      tree = AVLTree.remove ( tree, i );
      
      AVLTree.structure ( tree, 0 );
      System.out.println ( "\n------------------------" );
      
      System.in.read();
    }
  }
}
 
0
 

Well, Thank you very much for that code.

It helped me alot in my work

 
0
 

code is really gud for my work

 
0
 

Hi Narue,
I am doing a project for school where I was requested to test an implementation of AVL trees. It seems you have a bug in your class, which I actually discovered by accident.

I think you omit an RR rotation when deleting.

Here is my test:

private static Integer[] TREE_RR_INSERT = new Integer[]{20, 10, 30, 5, 15, 25, 40, 4, 8, 13, 18, 50, 3, 7, 9, 12, 14, 17, 19};

public void testDeleteNoRotation() {
        AVLNode<Integer> tree = null;
        // construct a tree
        for (Integer i : TREE_RR_INSERT) {
            tree = AVLTree.insert(tree, i);
        }
        for (Integer i : TREE_RR_INSERT) {
            tree = AVLTree.remove(tree, i);
            // test the tree is avl
            AVLTree.structure(tree, 0);
            System.out.println("---------------------------------------------------------");
            check(tree);
        }
    }

// -------HELPER METHODS-----------------------------------------
    private Integer getHeight(AVLNode tree) {
        if (tree == null) {
            return 0;
        }
        int leftHeight = (tree.link.get(0) != null) ? getHeight((AVLNode) tree.link.get(0)) : 0;
        int rightHeight = (tree.link.get(1) != null) ? getHeight((AVLNode) tree.link.get(1)) : 0;
        return (1 + Math.max(leftHeight, rightHeight));
    }

    private void check(AVLNode tree) {
        if (tree == null)
            return;
        // First verify that subtrees are correct
        AVLNode leftTree = (AVLNode) tree.link.get(0);
        AVLNode rightTree = (AVLNode) tree.link.get(1);
        check(leftTree);
        check(rightTree);

        // Now get the height of each subtree
        int leftHeight = getHeight(leftTree);
        int rightHeight = getHeight(rightTree);

        // Verify that AVL tree property is satisfied
        int diffHeight = rightHeight - leftHeight;
        if (Math.abs(diffHeight) > 1) {
            fail("Height difference is wrong for node: <" + tree.data + ">");
        }

        // Verify that search-tree property is satisfied
        // left
        if (leftTree != null) {
            if (tree.data.compareTo(leftTree.data) < 0) {
                fail("Left node greater than parent, for parent: <" + tree.data + ">");
            }
        }
        // right
        if (rightTree != null) {
            if (tree.data.compareTo(rightTree.data) > 0) {
                fail("Right node less than parent, for parent: <" + tree.data + ">");
            }
        }
    }
Isn't it about time forums rewarded their contributors?

Earn rewards points for helping others. Gain kudos. Cash out. Get better answers yourself.

It's as simple as contributing editorial or replying to discussions labeled or OP Kudos

You
This is an OP Kudos discussion and contributors may be rewarded
Post:
Start New Discussion
Tags Related to this Article