Recursive AVL Binary Search Tree

Narue 2 333 Views

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. :-)

tux4life commented: Great to 'C' you writing in another language than C/C++ ;) +13 
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();
    }
  }
}
Member Avatar for start_game316
start_game316 0 Newbie Poster

Well, Thank you very much for that code.

It helped me alot in my work

Member Avatar for karthikeyand
karthikeyand 0 Newbie Poster

code is really gud for my work

Member Avatar for easternRAT
easternRAT 0 Newbie Poster

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 + ">");
            }
        }
    }
Edited by Nick Evan because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview