AvlTree without parent

AvlTree.java

  private static class Entry<T extends Comparable<T>> {
    private Entry<T> avlRight = null;
    private Entry<T> avlLeft = null;
    private int avlHeight = 1;
    private T key;

    public Entry(T k) { key = k;}

    public int compareKey(T cmpKey) {
      return key.compareTo(cmpKey);
    }

    public int compareTo(Entry<T> other) {
      return compareKey(other.key);
    }

    public String toString() {
      return String.format("Entry(%s)", key);
    }
  }

  private static class AvlTree {
    public static <T extends Comparable<T>> Entry<T> get(Entry<T> root, T key) {
      while (root != null) {
        int cmp = root.compareKey(key);
        if (cmp > 0) {
          root = root.avlLeft;
        } else if (cmp < 0) {
          root = root.avlRight;
        } else {
          return root;
        }
      }
      return null;
    }

    private static <T extends Comparable<T>> Entry<T> getFirstEntry(Entry<T> root) {
      if (root != null) {
        while (root.avlLeft != null) {
          root = root.avlLeft;
        }
      }
      return root;
    }

    private static <T extends Comparable<T>> Entry<T> getLastEntry(Entry<T> root) {
      if (root != null) {
        while (root.avlRight != null) {
          root = root.avlRight;
        }
      }
      return root;
    }

    public static <T extends Comparable<T>> Entry<T> insert(Entry<T> root, Entry<T> node) {
      if (root == null) return node;
      if (node.compareTo(root) < 0) {
        root.avlLeft = insert(root.avlLeft, node);
      } else {
        root.avlRight = insert(root.avlRight, node);
      }
      return balance(root);
    }

    private static <T extends Comparable<T>> Entry<T> removeMin(Entry<T> p) {
      if (p.avlLeft == null)
        return p.avlRight;
      p.avlLeft = removeMin(p.avlLeft);
      return balance(p);
    }

    private static <T extends Comparable<T>> Entry<T> remove(Entry<T> root, T key) {
      if (root == null) return null;

      int cmp = root.compareKey(key);
      if (cmp == 0) {
        Entry<T> q = root.avlLeft;
        Entry<T> r = root.avlRight;
        if (r == null) return q;
        Entry<T> min = getFirstEntry(r);
        min.avlRight = removeMin(r);
        min.avlLeft = q;
        return balance(min);
      } else if (cmp > 0) {
        root.avlLeft = remove(root.avlLeft, key);
      } else /* if (cmp < 0) */ {
        root.avlRight = remove(root.avlRight, key);
      }
      return balance(root);
    }

    private static <T extends Comparable<T>> Entry<T> balance(Entry<T> p) {
      fixHeight(p);
      switch (balanceFactor(p)) {
        case 2:
          if (balanceFactor(p.avlRight) < 0) {
            p.avlRight = rotateRight(p.avlRight);
          }
          return rotateLeft(p);
        case -2:
          if (balanceFactor(p.avlLeft) > 0) {
            p.avlLeft = rotateLeft(p.avlLeft);
          }
          return rotateRight(p);
      }
      return p;
    }

    private static <T extends Comparable<T>> Entry<T> rotateRight(Entry<T> p) {
      Entry<T> q = p.avlLeft;
      p.avlLeft = q.avlRight;
      q.avlRight = p;
      fixHeight(p);
      fixHeight(q);
      return q;
    }

    private static <T extends Comparable<T>> Entry<T> rotateLeft(Entry<T> q) {
      Entry<T> p = q.avlRight;
      q.avlRight = p.avlLeft;
      p.avlLeft = q;
      fixHeight(q);
      fixHeight(p);
      return p;
    }

    private static <T extends Comparable<T>> void fixHeight(Entry<T> node) {
      int heightLeft = height(node.avlLeft);
      int heightRight = height(node.avlRight);
      node.avlHeight = 1 + Math.max(heightLeft, heightRight);
    }

    private static <T extends Comparable<T>> int height(Entry<T> node) {
      return node != null ? node.avlHeight : 0;
    }

    private static <T extends Comparable<T>> int balanceFactor(Entry<T> node) {
      return height(node.avlRight) - height(node.avlLeft);
    }
  }

  public static void main(String[] args) {
    java.util.TreeMap<Long, Object> treeMap = new java.util.TreeMap<Long, Object>();
    Entry<Long> root = null;

    final int NELEM = 10000;
    java.util.Random rand = new java.util.Random();
    for (int i = 0; i < NELEM; ++i) {
      long key = rand.nextInt(99999999);
      if (AvlTree.get(root, key) != null) {
        i--;
        continue;
      }
      root = AvlTree.insert(root, new Entry<Long>(key));
      treeMap.put(key, null);
      for (Long keyX: treeMap.keySet()) {
        Entry<Long> node = AvlTree.get(root, keyX);
        assert node != null;
        assert node.key.equals(keyX);
      }
    }

    for (int i = 0; i < NELEM; ++i) {
      long key = rand.nextInt(99999999);
      Entry<Long> node = AvlTree.get(root, key);
      if (!treeMap.containsKey(key)) {
        assert node == null;
        continue;
      }
      treeMap.remove(key);
      assert node.key == key;
      root = AvlTree.remove(root, key);
      for (Long keyX: treeMap.keySet()) {
        node = AvlTree.get(root, keyX);
        assert node != null;
        assert node.key.equals(keyX);
      }
    }
  }

Suggestion: to prevent memory leaks you should make the parent link be a weak reference.