The best AVL tree implementation.
Tried a few, could not get any source that actually did what I wanted : an AVL tree that can be accessed via an index and still be sorted.
So I wrote my own.
Some background : AVL trees are used as a way to do an "array" that can easily be accessed but also very fast with inserts and deletes. ArrayList is fast access, slow insert and deletes.
TreeMap has no index, so that will also not work. There is an Apache project Commons Collections that has something called a "TreeList", that is also implemented using an AVL tree, but its horrendously slow - not good enough. For a general description, checkout the
wiki page.
The best ways to do this seems to be between "Black an White" trees and AVL trees, so far I only have a AVL tree implementation.
This AVL tree works very well, it is one class, is faster than any I found so far and also consumes the least memory... 2015/08/28:
(this is only the tree, the sorted tee that uses this class will be in a later post)
package util.collections;
import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
/**
*
* @author Earl Bosch
* @param <V> Value
*/
public class AvlList<V extends Comparable> implements List<V>, ImmutableList<V> {
protected final Lock lock = new ReentrantLock();
protected final AVLRef ref;
public AvlList() {
ref = new AVLRef();
}
protected AvlList(AvlList<V> pAvlSortedList, int pStart, int pEnd) {
ref = pAvlSortedList.ref;
}
@Override
public int size() {
lock.lock();
try {
return ref.root == null ? 0 : ref.root.count;
} finally {
lock.unlock();
}
}
@Override
public String toString() {
lock.lock();
try {
if (ref.root == null) {
return "";
}
return ref.root.toString();
} finally {
lock.unlock();
}
}
public V firstValue() {
lock.lock();
try {
AVLNode<V> node = firstNode();
if (node == null) {
return null;
} else {
return node.value;
}
} finally {
lock.unlock();
}
}
public V lastValue() {
lock.lock();
try {
AVLNode<V> node = lastNode();
if (node == null) {
return null;
} else {
return node.value;
}
} finally {
lock.unlock();
}
}
protected AVLNode<V> firstNode() {
if (ref.first == null) {
ref.first = ref.root.firstNode();
}
return ref.first;
}
protected AVLNode<V> lastNode() {
if (ref.last == null) {
ref.last = ref.root.lastNode();
}
return ref.last;
}
@Override
public int indexOf(Object obj) {
lock.lock();
try {
return indexOf(findNode((V) obj));
} finally {
lock.unlock();
}
}
protected int indexOf(AVLNode<V> pNode) {
lock.lock();
try {
if (pNode != null) {
int index = pNode.left != null ? pNode.left.count : 0;
for (; pNode.parent != null; pNode = pNode.parent) {
if (pNode.parent.right == pNode) {
index += pNode.parent.count - pNode.count;
}
}
return index;
} else {
return -1;
}
} finally {
lock.unlock();
}
}
@Override
public int lastIndexOf(Object obj) {
lock.lock();
try {
V value = (V) obj;
int idx = 0;
for (AVLNode<V> loopNode = firstNode(); loopNode.hasNext(); loopNode = loopNode.next()) {
if (loopNode.value.equals(value)) {
loopNode = loopNode.next();
while (loopNode.value.equals(value)) {
idx++;
loopNode = loopNode.next();
}
return idx;
}
idx++;
}
return -1;
} finally {
lock.unlock();
}
}
protected AVLNode<V> findNode(V pValue) {
lock.lock();
try {
for (AVLNode<V> loopNode = (AVLNode<V>) firstNode(); loopNode.hasNext(); loopNode = loopNode.next()) {
if (loopNode.value.equals(pValue)) {
return loopNode;
}
}
return null;
} finally {
lock.unlock();
}
}
protected AVLNode<V> getNode(int pIndex) {
lock.lock();
try {
return getNode(ref.root, pIndex);
} finally {
lock.unlock();
}
}
private AVLNode<V> getNode(AVLNode<V> pStart, int pIndex) {
if (pStart == null || pIndex < 0 || pIndex >= pStart.count) {
throw new IndexOutOfBoundsException();
}
AVLNode<V> node = pStart;
while (node != null && pIndex >= 0) {
int leftSize = node.left != null ? node.left.count : 0;
if (pIndex < leftSize) {
node = node.left;
} else {
pIndex = pIndex - leftSize - 1;
if (pIndex < 0) {
return node;
}
node = node.right;
}
}
return null;
}
protected void rebalance(AVLNode<V> pNode) {
lock.lock();
try {
pNode.rebalance();
} finally {
lock.unlock();
}
}
protected AVLNode<V> addNode(final V pValue) {
lock.lock();
try {
return insertAfterNode(lastNode(), pValue);
} finally {
lock.unlock();
}
}
protected AVLNode<V> addNode(int pIndex, final V pValue) {
lock.lock();
try {
if (pIndex != 0 && (pIndex < 0 || pIndex > size())) {
throw new IndexOutOfBoundsException();
}
if (ref.root == null) {
ref.root = new AVLNode<V>(null, pValue);
return ref.root;
} else {
AVLNode<V> inserted = getNode(pIndex);
inserted = insertAfterNode(inserted, pValue);
return inserted;
}
} finally {
lock.unlock();
}
}
protected AVLNode<V> insertAfterNode(final AVLNode<V> pNode, final V pValue) {
ref.last = null;
ref.first = null;
AVLNode<V> newNode = new AVLNode(pNode, pValue);
if (pNode != null) {
AVLNode<V> childNode = pNode.right;
if (childNode != null) {
childNode.parent = newNode;
newNode.right = childNode;
newNode.count = childNode.count + 1;
}
pNode.right = newNode;
//newNode.parent = pNode;
newNode.addToParentCounts(1);
rebalance(newNode);
//rebalance(pNode);
return newNode;
} else {
AVLNode<V> childNode = firstNode();
newNode.count = 1;
childNode.left = newNode;
newNode.parent = childNode;
newNode.addToParentCounts(1);
rebalance(childNode);
}
/* if (ref.first == null || ref.first.left != null || ref.first.parent.right == ref.first) {
ref.first = newNode;
}
if (ref.last == null || ref.last.right != null || ref.last.parent.left == ref.last) {
ref.last = newNode;
}*/
return newNode;
}
protected AVLNode<V> insertBeforeNode(final AVLNode<V> pNode, final V pValue) {
ref.last = null;
ref.first = null;
AVLNode<V> newNode = new AVLNode(pNode, pValue);
if (pNode != null) {
AVLNode<V> childNode = pNode.left;
if (childNode != null) {
childNode.parent = newNode;
newNode.left = childNode;
newNode.count = childNode.count + 1;
}
pNode.left = newNode;
//newNode.parent = pNode;
newNode.addToParentCounts(1);
//rebalance(newNode);
rebalance(pNode);
return newNode;
} else {
AVLNode<V> childNode = firstNode();
newNode.count = 1;
childNode.left = newNode;
newNode.parent = childNode;
newNode.addToParentCounts(1);
rebalance(childNode);
}
/* if (ref.first == null || ref.first.left != null || ref.first.parent.right == ref.first) {
ref.first = newNode;
}
if (ref.last == null || ref.last.right != null || ref.last.parent.left == ref.last) {
ref.last = newNode;
}*/
return newNode;
}
protected AVLNode<V> insertAtSameNode(final AVLNode<V> pNode, final V pValue) {
if (pNode.right == null) {
return insertAfterNode(pNode, pValue);
} else if (pNode.left == null) {
return insertBeforeNode(pNode, pValue);
} else {
if (pNode.right.count <= pNode.left.count) {
return insertAfterNode(pNode, pValue);
} else {
return insertBeforeNode(pNode, pValue);
}
}
}
@Override
public boolean isEmpty() {
lock.lock();
try {
return ref.root == null;
} finally {
lock.unlock();
}
}
@Override
public boolean contains(Object o) {
lock.lock();
try {
return findNode((V) o) != null;
} finally {
lock.unlock();
}
}
@Override
public Object[] toArray() {
// copy values into the array
Object[] array = new Object[size()];
int index = 0;
lock.lock();
try {
for (AVLNode<V> loopNode = firstNode(); loopNode.hasNext(); loopNode = loopNode.next()) {
array[index] = loopNode.value;
index++;
}
return array;
} finally {
lock.unlock();
}
}
@Override
public <T> T[] toArray(T[] array) {
// create an array of the same type as the array passed
lock.lock();
try {
if (array.length < size()) {
array = (T[]) Array.newInstance(array.getClass().getComponentType(), size());
} else if (array.length > size()) {
array[size()] = null;
}
int index = 0;
for (AVLNode<V> loopNode = firstNode(); loopNode.hasNext(); loopNode = loopNode.next()) {
array[index] = (T) loopNode.value;
index++;
}
return array;
} finally {
lock.unlock();
}
}
@Override
public boolean add(V pValue) {
return addNode(size(), pValue) != null;
}
@Override
public void add(int index, V pValue) {
addNode(index, pValue);
}
@Override
public boolean containsAll(Collection<?> c) {
lock.lock();
try {
boolean ret = true;
for (Object o : c) {
if (!this.contains((V) o)) {
ret = false;
}
}
return ret;
} finally {
lock.unlock();
}
}
@Override
public boolean addAll(Collection<? extends V> c) {
lock.lock();
try {
boolean ret = true;
for (V value : c) {
if (addNode(value) == null) {
ret = false;
}
}
return ret;
} finally {
lock.unlock();
}
}
@Override
public boolean addAll(int index, Collection<? extends V> c) {
lock.lock();
try {
boolean ret = true;
for (V value : c) {
if (addNode(index, value) == null) {
ret = false;
}
}
return ret;
} finally {
lock.unlock();
}
}
@Override
public void clear() {
lock.lock();
try {
ref.first = null;
ref.last = null;
ref.root = null;
} finally {
lock.unlock();
}
}
@Override
public V get(int index) {
lock.lock();
try {
return (V) getNode(ref.root, index).value;
} finally {
lock.unlock();
}
}
@Override
public V set(int index, V element) {
lock.lock();
try {
return getNode(index).value = element;
} finally {
lock.unlock();
}
}
@Override
public boolean retainAll(Collection<?> c) {
lock.lock();
try {
boolean ret = true;
for (Object o : c) {
if (!contains((V) o)) {
ret = !remove((V) o);
}
}
return ret;
} finally {
lock.unlock();
}
}
@Override
public boolean removeAll(Collection<?> c) {
lock.lock();
try {
boolean ret = true;
for (Object o : c) {
if (!remove((V) o)) {
ret = false;
}
}
return ret;
} finally {
lock.unlock();
}
}
@Override
public boolean remove(Object o) {
return removeNode(findNode((V) o)) != null;
}
@Override
public V remove(int index) {
return removeNode(getNode(index)).value;
}
protected AVLNode<V> removeNode(AVLNode<V> pNode) {
lock.lock();
try {
if (pNode != null) {
pNode = pNode.remove();
}
return pNode;
} finally {
lock.unlock();
}
}
@Override
public Iterator<V> iterator() {
lock.lock();
try {
return new LinkedNodeListIterator(this);
} finally {
lock.unlock();
}
}
public Iterator<V> iterator(int index) {
lock.lock();
try {
return new LinkedNodeListIterator(this).goTo(index);
} finally {
lock.unlock();
}
}
@Override
public ListIterator<V> listIterator() {
lock.lock();
try {
return new SimpleListIterator(this);
} finally {
lock.unlock();
}
}
@Override
public ListIterator<V> listIterator(int index) {
lock.lock();
try {
return new SimpleListIterator(this, index);
} finally {
lock.unlock();
}
}
protected class AVLRef<N extends AVLNode<V>> {
public N first = null, last = null, root = null;
public AVLRef() {
}
public AVLRef(boolean pUnique, N pRoot, N pFirst, N pLast) {
root = pRoot;
first = pFirst;
last = pLast;
}
}
protected class AVLNode<E extends V> {
public E value;
public int count;
public AVLNode<E> left, right, parent;
public AVLNode() {
}
public AVLNode(final AVLNode<E> pParent, final E pValue) {
parent = pParent;
value = pValue;
count = 1;
}
public void addToParentCounts(final int pDelta) {
for (AVLNode<E> loopNode = this.parent; loopNode != null; loopNode = loopNode.parent) {
loopNode.count += pDelta;
}
}
final void refreshCounts(boolean countSelf) {
count = 0;
if (left != null) {
count += left.count;
}
if (right != null) {
count += right.count;
}
count += countSelf ? 1 : 0;
}
@Override
public String toString() {
StringBuffer result = new StringBuffer();
asTree(result);
return result.toString();
}
public void asTree(StringBuffer out) {
out.append("begin = ").append(value).append('\n');
asTree("", out);
}
private void asTree(String indentation, StringBuffer out) {
if (left != null) {
left.asTree(indentation + " ", out);
}
out.append(indentation);
if (value != null) {
out.append("- ");
if (value instanceof AVLNode) {
out.append("<Node>");
} else {
out.append(value).append(" : ").append(count).append(" : ").append(parent != null ? parent.value : "root");
}
}
out.append("\n");
if (right != null) {
right.asTree(indentation + " ", out);
}
}
public boolean hasNext() {
return (next() != null);
}
public boolean hasPrevious() {
return (previous() != null);
}
public AVLNode<E> previous() {
if (left != null) {
AVLNode<E> child = left;
while (child.right != null) {
child = child.right;
}
return child;
} else {
AVLNode<E> backNode = this;
while (backNode.parent != null && backNode.parent.left == backNode) {
backNode = backNode.parent;
}
return backNode.parent;
}
}
public AVLNode<E> next() {
if (right != null) {
AVLNode<E> child = right;
while (child.left != null) {
child = child.left;
}
return child;
} else {
AVLNode<E> backNode = this;
while (backNode.parent != null && backNode.parent.right == backNode) {
backNode = backNode.parent;
}
return backNode.parent;
}
}
protected AVLNode<E> firstNode() {
AVLNode result = this;
while (result.left != null) {
result = result.left;
}
return result;
}
protected AVLNode<E> lastNode() {
AVLNode result = this;
while (result.right != null) {
result = result.right;
}
return result;
}
protected AVLNode<E> nodeSmallest(final Comparator pComp, final E pElement) {
AVLNode result = this;
while (result != null && pComp.compare(pElement, result.value) < 0) {
while (result.left != null && pComp.compare(pElement, result.left.value) < 0) {
result = result.left;
}
result = result.previous();
}
return result;
}
protected AVLNode<E> nodeBiggest(final Comparator pComp, final E pElement) {
AVLNode<E> result = this;
AVLNode<E> prev = null;
while (result != null && pComp.compare(pElement, result.value) >= 0) {
while (result.right != null && pComp.compare(pElement, result.right.value) >= 0) {
result = result.right;
}
prev = result;
result = result.next();
}
return prev;
}
private AVLNode<E> rotateRight() {
AVLNode<E> leftNode = this;
AVLNode<E> rightNode = leftNode.right;
leftNode.right = rightNode.left;
if (leftNode.right != null) {
leftNode.right.parent = leftNode;
}
rightNode.left = leftNode;
rightNode.parent = leftNode.parent;
leftNode.parent = rightNode;
if (rightNode.parent != null) {
if (rightNode.parent.left == leftNode) {
rightNode.parent.left = rightNode;
} else {
rightNode.parent.right = rightNode;
}
}
leftNode.count = (leftNode.left != null ? leftNode.left.count : 0) + (leftNode.right != null ? leftNode.right.count : 0) + 1;
rightNode.count = (rightNode.left != null ? rightNode.left.count : 0) + (rightNode.right != null ? rightNode.right.count : 0) + 1;
return rightNode;
}
private AVLNode<E> rotateLeft() {
AVLNode<E> rightNode = this;
AVLNode<E> leftNode = rightNode.left;
rightNode.left = leftNode.right;
if (rightNode.left != null) {
rightNode.left.parent = rightNode;
}
leftNode.right = rightNode;
if (rightNode.parent != null) {
if (rightNode.parent.left == rightNode) {
rightNode.parent.left = leftNode;
} else {
rightNode.parent.right = leftNode;
}
}
leftNode.parent = rightNode.parent;
rightNode.parent = leftNode;
rightNode.count = (rightNode.left != null ? rightNode.left.count : 0) + (rightNode.right != null ? rightNode.right.count : 0) + 1;
leftNode.count = (leftNode.left != null ? leftNode.left.count : 0) + (leftNode.right != null ? leftNode.right.count : 0) + 1;
return leftNode;
}
protected AVLNode<E> replaceWith(final AVLNode<E> replacement) {
AVLNode<E> nodeParent = this.parent;
if (nodeParent != null) {
if (nodeParent.left == this) {
nodeParent.left = replacement;
} else if (nodeParent.right == this) {
nodeParent.right = replacement;
}
} else {
ref.root = replacement;
}
if (replacement != null) {
replacement.parent = nodeParent;
}
if (nodeParent != null) {
nodeParent.rebalance();
} else if (replacement != null) {
replacement.rebalance();
}
return replacement;
}
protected void rebalance() {
AVLNode<E> rotatedNode;
for (AVLNode<E> loopNode = this; loopNode != null; loopNode = loopNode.parent) {
int leftCount = loopNode.left != null ? loopNode.left.count : 0;
int rightCount = loopNode.right != null ? loopNode.right.count : 0;
if (leftCount - rightCount > 1) { // Left Right Case
if ((loopNode.left.left != null ? loopNode.left.left.count : 0) < (loopNode.left.right != null ? loopNode.left.right.count : 0)) {
rotatedNode = loopNode.left.rotateRight();
if (rotatedNode.parent == null) {
ref.root = rotatedNode;
}
}
loopNode = loopNode.rotateLeft();
if (loopNode.parent == null) {
ref.root = loopNode;
}
} else if (leftCount - rightCount < -1) { // Right Left Case
if ((loopNode.right.left != null ? loopNode.right.left.count : 0) > (loopNode.right.right != null ? loopNode.right.right.count : 0)) {
rotatedNode = loopNode.right.rotateLeft();
if (rotatedNode.parent == null) {
ref.root = rotatedNode;
}
}
loopNode = loopNode.rotateRight();
if (loopNode.parent == null) {
ref.root = loopNode;
}
}
}
}
protected AVLNode<E> remove() {
AVLNode<E> node = this;
if (node.right == null && node.left == null) {
if (node.parent != null) {
node.addToParentCounts(-1);
if (node.parent.left == node) {
node.parent.left = null;
} else if (node.parent.right == node) {
node.parent.right = null;
}
} else {
clear();
}
} else if (node.right == null) {
node = node.replaceWith(node.left);
} else if (node.left == null) {
node = node.replaceWith(node.right);
} else {
AVLNode<E> replacement = node.left.lastNode();
replacement.addToParentCounts(-1);
node = replacement.replaceWith(replacement.left);
// update the tree structure to point to the replacement
replacement.left = node.left;
if (replacement.left != null) {
replacement.left.parent = replacement;
}
replacement.right = node.right;
if (replacement.right != null) {
replacement.right.parent = replacement;
}
replacement.refreshCounts(true);
node = node.replaceWith(replacement);
replacement.parent.addToParentCounts(1);
}
if (node.parent == null) {
ref.root = (AVLNode) node;
}
if (ref.first == node) {
ref.first = (AVLNode) node.parent;
}
if (ref.last == node) {
ref.last = (AVLNode) node.parent;
}
return node;
}
}
private class LinkedNodeListIterator<E extends V> implements Iterator<E>, ListIterator<E> {
private final AvlList source;
private AVLNode cursor;
private int index;
public LinkedNodeListIterator(AvlList<E> pSource) {
source = pSource;
index = 0;
lock.lock();
try {
cursor = source.firstNode();
} finally {
lock.unlock();
}
}
public LinkedNodeListIterator goTo(int pIndex) {
lock.lock();
try {
AVLNode node = source.getNode(pIndex);
if (node == null) {
node = source.firstNode();
}
cursor = node;
} finally {
lock.unlock();
}
index = pIndex;
return this;
}
@Override
public boolean hasNext() {
lock.lock();
try {
return (cursor != null && cursor.hasNext());
} finally {
lock.unlock();
}
}
@Override
public E next() {
if (cursor == null) {
throw new NoSuchElementException("Cannot retrieve element next on a list of size " + source.size());
}
E ret = (E) cursor.value;
lock.lock();
try {
cursor = cursor.next();
return ret;
} finally {
lock.unlock();
}
}
@Override
public void remove() {
source.removeNode((AVLNode) cursor);
}
@Override
public boolean hasPrevious() {
lock.lock();
try {
return (cursor != null && cursor.hasPrevious());
} finally {
lock.unlock();
}
}
@Override
public E previous() {
lock.lock();
try {
cursor = cursor.previous();
} finally {
lock.unlock();
}
if (cursor == null) {
throw new NoSuchElementException("Cannot retrieve element next on a list of size " + source.size());
}
return (E) cursor.value;
}
@Override
public int nextIndex() {
next();
return ++index;
}
@Override
public int previousIndex() {
previous();
return --index;
}
@Override
public void set(E e) {
lock.lock();
try {
cursor.value = e;
} finally {
lock.unlock();
}
}
@Override
public void add(E e) {
source.add(e);
}
}
@Override
public AvlList<V> subList(int i, int i1) {
return null;
}
@Override
public ImmutableList<V> subImmutableList(int i, int i1) {
return null;
}
}
|
