Java AVL Tree

A non-recursive Java AVL Tree implementation. Performance is comparable (insertion slightly worse, search slightly better) with TreeSet of SUN JDK. By specializing the generic version for primitive types the ~2.5 performance boost can be achieved. The tree can be further optimized via height-independent balances update. This is not done for the sake of the code simplicity.

package net.bobah.containers.trees.avl;

import java.util.Iterator;

public class AvlTreeSet<T extends Comparable<T>> {

  public int height() { ... }

  public int size() { ... }

  public Iterator<T> iterator() { ... }

  public boolean insert(T value) { ... }

  public boolean remove(T value) { ... }

  public boolean contains(T value) { ... }


avltree.zip3.87 KB