AVL tree/Java
< AVL tree
Code
<lang java>import java.util.Iterator; import java.util.Comparator; import java.io.*;
@SuppressWarnings("unchecked")
public enum State { Header, LeftHigh, Balanced, RightHigh }
public class Node { public Node Left; public Node Right; public Node Parent; public State Balance;
public Node() { Left = this; Right = this; Parent = null; Balance = State.Header; }
public Node(Node p) { Left = null; Right = null; Parent = p; Balance = State.Balanced; } public Boolean isHeader () { return Balance == State.Header; } }
public class Utility {
static int depth(Node root) { if (root != null) { int Left = root.Left != null ? depth(root.Left) : 0; int Right = root.Right != null ? depth(root.Right) : 0; return Left < Right ? Right + 1 : Left + 1; } else return 0; }
static void swapNodes(Node A, Node B) { if (B == A.Left) { if (B.Left != null) B.Left.Parent = A; if (B.Right != null) B.Right.Parent = A;
if (A.Right != null) A.Right.Parent = B;
if (!A.Parent.isHeader()) { if (A.Parent.Left == A) A.Parent.Left = B; else A.Parent.Right = B; } else A.Parent.Parent = B;
B.Parent = A.Parent; A.Parent = B;
A.Left = B.Left; B.Left = A;
Node Temp = A.Right; A.Right = B.Right; B.Right = Temp; } else if (B == A.Right) { if (B.Right != null) B.Right.Parent = A; if (B.Left != null) B.Left.Parent = A;
if (A.Left != null) A.Left.Parent = B;
if (!A.Parent.isHeader()) { if (A.Parent.Left == A) A.Parent.Left = B; else A.Parent.Right = B; } else A.Parent.Parent = B;
B.Parent = A.Parent; A.Parent = B;
A.Right = B.Right; B.Right = A;
Node Temp=A.Left; A.Left = B.Left; B.Left = Temp; } else if (A == B.Left) { if (A.Left != null) A.Left.Parent = B; if (A.Right != null) A.Right.Parent = B;
if (B.Right != null) B.Right.Parent = A;
if (!B.Parent.isHeader()) { if (B.Parent.Left == B) B.Parent.Left = A; else B.Parent.Right = A; } else B.Parent.Parent = A;
A.Parent = B.Parent; B.Parent = A;
B.Left = A.Left; A.Left = B;
Node Temp = A.Right; A.Right = B.Right; B.Right = Temp; } else if (A == B.Right) { if (A.Right != null) A.Right.Parent = B; if (A.Left != null) A.Left.Parent = B;
if (B.Left != null) B.Left.Parent = A;
if (!B.Parent.isHeader()) { if (B.Parent.Left == B) B.Parent.Left = A; else B.Parent.Right = A; } else B.Parent.Parent = A;
A.Parent = B.Parent; B.Parent = A;
B.Right = A.Right; A.Right = B;
Node Temp = A.Left; A.Left = B.Left; B.Left = Temp; } else { if (A.Parent == B.Parent) { Node Temp = A.Parent.Left; A.Parent.Left = A.Parent.Right; A.Parent.Right = Temp; } else { if (!A.Parent.isHeader()) { if (A.Parent.Left == A) A.Parent.Left = B; else A.Parent.Right = B; } else A.Parent.Parent = B;
if (!B.Parent.isHeader()) { if (B.Parent.Left == B) B.Parent.Left = A; else B.Parent.Right = A; } else B.Parent.Parent = A; }
if (B.Left != null) B.Left.Parent = A; if (B.Right != null) B.Right.Parent = A;
if (A.Left != null) A.Left.Parent = B; if (A.Right != null) A.Right.Parent = B;
Node Temp1 = A.Left; A.Left = B.Left; B.Left = Temp1; Node Temp2 = A.Right; A.Right = B.Right; B.Right = Temp2;
Node Temp3 = A.Parent; A.Parent = B.Parent; B.Parent = Temp3; }
State Balance = A.Balance; A.Balance = B.Balance; B.Balance = Balance; }
static Node rotateLeft(Node root) { Node Parent = root.Parent; Node x = root.Right;
root.Parent = x; x.Parent = Parent; if (x.Left != null) x.Left.Parent = root;
root.Right = x.Left; x.Left = root; root = x; return root; }
static Node rotateRight(Node root) { Node Parent = root.Parent; Node x = root.Left;
root.Parent = x; x.Parent = Parent; if (x.Right != null) x.Right.Parent = root;
root.Left = x.Right; x.Right = root; root = x; return root; } static Node balanceLeft(Node root) { Node left = root.Left;
switch (left.Balance) { case LeftHigh: root.Balance = State.Balanced; left.Balance = State.Balanced; root = rotateRight(root); break;
case RightHigh: { Node subRight = left.Right; switch (subRight.Balance) { case Balanced: root.Balance = State.Balanced; left.Balance = State.Balanced; break;
case RightHigh: root.Balance = State.Balanced; left.Balance = State.LeftHigh; break;
case LeftHigh: root.Balance = State.RightHigh; left.Balance = State.Balanced; break; } subRight.Balance = State.Balanced; left = rotateLeft(left); root.Left = left; root = rotateRight(root); } break;
case Balanced: root.Balance = State.LeftHigh; left.Balance = State.RightHigh; root = rotateRight(root); break; } return root; }
static Node balanceRight(Node root) { Node right = root.Right;
switch (right.Balance) { case RightHigh: root.Balance = State.Balanced; right.Balance = State.Balanced; root = rotateLeft(root); break;
case LeftHigh: { Node subLeft = right.Left; // Left Subtree of Right switch (subLeft.Balance) { case Balanced: root.Balance = State.Balanced; right.Balance = State.Balanced; break;
case LeftHigh: root.Balance = State.Balanced; right.Balance = State.RightHigh; break;
case RightHigh: root.Balance = State.LeftHigh; right.Balance = State.Balanced; break; } subLeft.Balance = State.Balanced; right = rotateRight(right); root.Right = right; root = rotateLeft(root); } break;
case Balanced: root.Balance = State.RightHigh; right.Balance = State.LeftHigh; root = rotateLeft(root); break; } return root; }
static void balanceTree(Node root, Direction From) { Boolean Taller = true;
while (Taller) { Node Parent = root.Parent; Direction NextFrom = (Parent.Left == root) ? Direction.FromLeft : Direction.FromRight;
if (From == Direction.FromLeft) { switch (root.Balance) { case LeftHigh: if (Parent.isHeader()) Parent.Parent = balanceLeft(Parent.Parent); else if (Parent.Left == root) Parent.Left = balanceLeft(Parent.Left); else Parent.Right = balanceLeft(Parent.Right); Taller = false; break;
case Balanced: root.Balance = State.LeftHigh; Taller = true; break;
case RightHigh: root.Balance = State.Balanced; Taller = false; break; } } else { switch (root.Balance) { case LeftHigh: root.Balance = State.Balanced; Taller = false; break;
case Balanced: root.Balance = State.RightHigh; Taller = true; break;
case RightHigh: if (Parent.isHeader()) Parent.Parent = balanceRight(Parent.Parent); else if (Parent.Left == root) Parent.Left = balanceRight(Parent.Left); else Parent.Right = balanceRight(Parent.Right); Taller = false; break; } }
if (Taller) // skip up a level { if (Parent.isHeader()) Taller = false; else { root = Parent; From = NextFrom; } } } } static void balanceTreeRemove(Node root, Direction From) { if (root.isHeader()) return;
Boolean Shorter = true;
while (Shorter) { Node Parent = root.Parent; Direction NextFrom = (Parent.Left == root) ? Direction.FromLeft : Direction.FromRight;
if (From == Direction.FromLeft) { switch (root.Balance) { case LeftHigh: root.Balance = State.Balanced; Shorter = true; break;
case Balanced: root.Balance = State.RightHigh; Shorter = false; break;
case RightHigh: if (root.Right.Balance == State.Balanced) Shorter = false; else Shorter = true; if (Parent.isHeader()) Parent.Parent = balanceRight(Parent.Parent); else if (Parent.Left == root) Parent.Left = balanceRight(Parent.Left); else Parent.Right = balanceRight(Parent.Right); break; } } else { switch (root.Balance) { case RightHigh: root.Balance = State.Balanced; Shorter = true; break;
case Balanced: root.Balance = State.LeftHigh; Shorter = false; break;
case LeftHigh: if (root.Left.Balance == State.Balanced) Shorter = false; else Shorter = true; if (Parent.isHeader()) Parent.Parent = balanceLeft(Parent.Parent); else if (Parent.Left == root) Parent.Left = balanceLeft(Parent.Left); else Parent.Right = balanceLeft(Parent.Right); break; } }
if (Shorter) { if (Parent.isHeader()) Shorter = false; else { From = NextFrom; root = Parent; } } } } static Node previousNode(Node Node) { if (Node.isHeader()) { return Node.Right; }
if (Node.Left != null) { Node = Node.Left; while (Node.Right != null) Node = Node.Right; } else { Node y = Node.Parent; if (y.isHeader()) return y; while (Node == y.Left) { Node = y; y = y.Parent; } Node = y; } return Node; }
static Node nextNode(Node Node) { if (Node.isHeader()) return Node.Left;
if (Node.Right != null) { Node = Node.Right; while (Node.Left != null) Node = Node.Left; } else { Node y = Node.Parent; if (y.isHeader()) return y; while (Node == y.Right) { Node = y; y = y.Parent; } Node = y; } return Node; }
}
public class SetNode<T> extends Node { public T Data;
public SetNode(T dataType, Node Parent) { super(Parent); Data = dataType; } }
public interface Cloneable { T clone(); }
public interface Cloner<T> { T clone(T t); }
public class DefaultCloner implements Cloner, Serializable { public T clone(T t) { try { Cloneable copier = (Cloneable)t; return copier.clone(); } catch(Exception e) { return t; } } }
public class DefaultComparator implements Comparator, Serializable { public int compare(T t1, T t2) { Comparable key = (Comparable)t1; return key.compareTo(t2); }
public boolean equals(T t1, T t2) { Comparable key = (Comparable)t1; return key.compareTo(t2) != 0; }
}
public enum Direction { FromLeft, FromRight }
public class SetEntry implements Iterator { public SetEntry(Node n) { _Node = n; }
public T value() { return ((SetNode)_Node).Data; }
public Boolean isHeader() { return _Node.isHeader(); }
public boolean equals(SetEntry other) { return _Node == other._Node; } public String toString() { return value().toString(); }
public boolean hasNext() { Node _Next = Utility.nextNode(_Node); return _Next.isHeader() ? false : true; }
public T next() { _Node = Utility.nextNode(_Node); return ((SetNode)_Node).Data; }
public T previous() { _Node = Utility.previousNode(_Node); return ((SetNode)_Node).Data; }
public Boolean moveNext() { _Node = Utility.nextNode(_Node); return _Node.isHeader() ? false : true; }
public Boolean movePrevious() { _Node = Utility.previousNode(_Node); return _Node.isHeader() ? false : true; }
public Node _Node; }
public enum SetOperation { Union, Intersection, SymmetricDifference, Difference }
public class EntryAlreadyExistsException extends Exception { public EntryAlreadyExistsException() { super("An entry already exists in the collection."); } }
public class EntryNotFoundException extends Exception { public EntryNotFoundException() { super("An entry could not be found."); } }
public class InvalidSetOperationException extends Exception { public InvalidSetOperationException() { super("An invalid set operation was specified."); } }
public class Set<T> implements Iterable<T>, Cloneable<Set<T>>, Serializable { public Node Header; public long Nodes; Comparator<T> Compare; Cloner<T> Clone; public Set() { Nodes = 0; Header = new Node(); Compare = new DefaultComparator<T>(); Clone = new DefaultCloner<T>(); }
public Set(Iterable<T> Iterable) { Nodes = 0; Header = new Node(); Compare = new DefaultComparator<T>(); Clone = new DefaultCloner<T>(); for(T t : Iterable) { try { add(Clone.clone(t)); } catch (EntryAlreadyExistsException e) {} } }
public Set(Comparator<T> ComparatorIn) { Nodes = 0; Header = new Node(); Compare = ComparatorIn; Clone = new DefaultCloner<T>(); }
public Set(Iterable<T> Iterable, Comparator<T> ComparatorIn) { Nodes = 0; Header = new Node(); Compare = ComparatorIn; Clone = new DefaultCloner<T>(); for(T t : Iterable) { try { add(Clone.clone(t)); } catch (EntryAlreadyExistsException e) {} } }
public Set(T... params) { Nodes = 0; Header = new Node(); Compare = new DefaultComparator<T>(); Clone = new DefaultCloner<T>(); for(T t : params) { try { add(Clone.clone(t)); } catch (EntryAlreadyExistsException e) {} } } public Set(Set<T> A, Set<T> B, SetOperation operation) throws EntryAlreadyExistsException, InvalidSetOperationException { synchronized(A) { synchronized(B) { Compare = A.Compare; Nodes = 0; Header = new Node(); Clone = new DefaultCloner<T>();
SetEntry<T> first1 = A.begin(); SetEntry<T> last1 = A.end(); SetEntry<T> first2 = B.begin(); SetEntry<T> last2 = B.end();
switch (operation) { case Union: while (!first1.equals(last1) && !first2.equals(last2)) { int order = Compare.compare(first1.value(),first2.value());
if (order < 0) { add(Clone.clone(first1.value())); first1.moveNext(); }
else if (order > 0) { add(Clone.clone(first2.value())); first2.moveNext(); }
else { add(first1.value()); first1.moveNext(); first2.moveNext(); } } while (!first1.equals(last1)) { add(Clone.clone(first1.value())); first1.moveNext(); } while (!first2.equals(last2)) { add(Clone.clone(first2.value())); first2.moveNext(); } return;
case Intersection: while (!first1.equals(last1) && !first2.equals(last2)) { int order = Compare.compare(first1.value(),first2.value());
if (order < 0) first1.moveNext();
else if (order > 0) first2.moveNext();
else { add(Clone.clone(first1.value())); first1.moveNext(); first2.moveNext(); } } return;
case SymmetricDifference: while (!first1.equals(last1) && !first2.equals(last2)) { int order = Compare.compare(first1.value(),first2.value());
if (order < 0) { add(Clone.clone(first1.value())); first1.moveNext(); }
else if (order > 0) { add(Clone.clone(first2.value())); first2.moveNext(); }
else { first1.moveNext(); first2.moveNext(); } }
while (!first1.equals(last1)) { add(Clone.clone(first1.value())); first1.moveNext(); }
while (!first2.equals(last2)) { add(Clone.clone(first2.value())); first2.moveNext(); } return;
case Difference: while (!first1.equals(last1) && !first2.equals(last2)) { int order = Compare.compare(first1.value(),first2.value());
if (order < 0) { add(Clone.clone(first1.value())); first1.moveNext(); }
else if (order > 0) { add(Clone.clone(first1.value())); first1.moveNext(); first2.moveNext(); }
else { first1.moveNext(); first2.moveNext(); } }
while (!first1.equals(last1)) { add(Clone.clone(first1.value())); first1.moveNext(); } return; }
throw new InvalidSetOperationException(); } } }
public Set(Set<T> SetToCopy) { synchronized(SetToCopy) { Nodes = 0; Header = new Node(); Compare = SetToCopy.Compare; Clone = SetToCopy.Clone; for(T t : SetToCopy) { try { add(Clone.clone(t)); } catch (EntryAlreadyExistsException e) {} } } } private void readObject(java.io.ObjectInputStream stream) throws IOException, ClassNotFoundException { Header = new Node(); Nodes = 0; int Count = stream.readInt(); Compare = (Comparator<T>)stream.readObject(); Clone = (Cloner<T>)stream.readObject(); for (int i=0; i<Count; i++) try { add((T)stream.readObject()); } catch(EntryAlreadyExistsException e) {} }
private void writeObject(java.io.ObjectOutputStream stream) throws IOException { synchronized (this) { stream.writeInt((int)Nodes); stream.writeObject(Compare); stream.writeObject(Clone); for (T t : this) stream.writeObject(t); } }
private void readObjectNoData() throws ObjectStreamException { Header = new Node(); Nodes = 0; } public long length() {return Nodes;} public Iterator<T> iterator() { return new SetEntry<T>(Header); }
public SetEntry<T> after(T key, boolean equals) { synchronized (this) { return new SetEntry<T>(equals ? afterEquals(key) : after(key)); } } public SetEntry<T> before(T key, boolean equals) { synchronized (this) { return new SetEntry<T>(equals ? beforeEquals(key) : before(key)); } } public Comparator<T> getComparator() { return Compare; } public Set<T> clone() { synchronized(this) { Set<T> Out = new Set<T>(Compare); Out.Clone = Clone; for (T t : this) { try { Out.add(Clone.clone(t)); } catch (EntryAlreadyExistsException e) {} } return Out; } } public long depth() { synchronized (this) { return Utility.depth(Header.Parent); } } public Cloner<T> getCloner() {synchronized (this) {return Clone;} } public void setCloner(Cloner<T> C) {synchronized (this) {Clone = C;}}
public SetEntry<T> insert(T data) throws EntryAlreadyExistsException { return new SetEntry<T>(add(data)); } public SetNode<T> add(T data) throws EntryAlreadyExistsException { synchronized(this) { if (Header.Parent == null) { SetNode<T> newNode = new SetNode<T>(data, Header); Header.Parent = newNode; Nodes++; Header.Left = Header.Parent; Header.Right = Header.Parent; return newNode; } else { SetNode<T> newRoot = (SetNode<T>)Header.Parent; for (; ; ) { int compare = Compare.compare(data,newRoot.Data);
if (compare == 0) // Item Exists throw new EntryAlreadyExistsException();
else if (compare < 0) { if (newRoot.Left != null) newRoot = (SetNode<T>)newRoot.Left; else { SetNode<T> NewNode = new SetNode<T>(data, newRoot); Nodes++; newRoot.Left = NewNode; if (Header.Left == newRoot) Header.Left = NewNode; Utility.balanceTree(newRoot, Direction.FromLeft); return NewNode; } }
else { if (newRoot.Right != null) newRoot = (SetNode<T>)newRoot.Right; else { SetNode<T> NewNode = new SetNode<T>(data, newRoot); Nodes++; newRoot.Right = NewNode; if (Header.Right == newRoot) Header.Right = NewNode; Utility.balanceTree(newRoot, Direction.FromRight); return NewNode; } } } } } }
public long remove() { synchronized (this) { long count = Nodes; Header.Parent = null; Header.Left = Header; Header.Right = Header; Nodes = 0; return count; }
}
public void remove(T data) throws EntryNotFoundException { synchronized (this) { SetNode<T> root = (SetNode<T>)Header.Parent;
for (; ; ) { if (root == null) throw new EntryNotFoundException();
int compare = Compare.compare(data,root.Data);
if (compare < 0) root = (SetNode<T>)root.Left;
else if (compare > 0) root = (SetNode<T>)root.Right;
else // Item is found { if (root.Left != null && root.Right != null) { Node replace = root.Left; while (replace.Right != null) replace = replace.Right; Utility.swapNodes(root, replace); }
Node Parent = root.Parent;
Direction From = (Parent.Left == root) ? Direction.FromLeft : Direction.FromRight;
if (Header.Left == root) { Node n = Utility.nextNode(root);
if (n.isHeader()) { Header.Left = Header; Header.Right = Header; } else Header.Left = n; } else if (Header.Right == root) { Node p = Utility.previousNode(root);
if (p.isHeader()) { Header.Left = Header; Header.Right = Header; } else Header.Right = p; }
if (root.Left == null) { if (Parent == Header) Header.Parent = root.Right; else if (Parent.Left == root) Parent.Left = root.Right; else Parent.Right = root.Right;
if (root.Right != null) root.Right.Parent = Parent; } else { if (Parent == Header) Header.Parent = root.Left; else if (Parent.Left == root) Parent.Left = root.Left; else Parent.Right = root.Left;
if (root.Left != null) root.Left.Parent = Parent; }
Utility.balanceTreeRemove(Parent, From);
Nodes--; break; } } } }
public boolean exists(T data) { synchronized (this) { if (Header.Parent == null) return false; else { Node search = Header.Parent;
do { int Result = Compare.compare(data,((SetNode<T>)search).Data);
if (Result < 0) search = search.Left;
else if (Result > 0) search = search.Right;
else break;
} while (search != null);
return search != null; } } }
public T find(T data) throws EntryNotFoundException { synchronized (this) { if (Header.Parent == null) throw new EntryNotFoundException(); else { Node search = Header.Parent;
do { int Result = Compare.compare(data,((SetNode<T>)search).Data);
if (Result < 0) search = search.Left;
else if (Result > 0) search = search.Right;
else break;
} while (search != null);
if (search != null) throw new EntryNotFoundException(); return ((SetNode<T>)search).Data; } } }
public SetEntry<T> locate(T data) throws EntryNotFoundException { synchronized (this) { if (Header.Parent == null) throw new EntryNotFoundException(); else { Node search = Header.Parent;
do { int Result = Compare.compare(data,((SetNode<T>)search).Data);
if (Result < 0) search = search.Left;
else if (Result > 0) search = search.Right;
else break;
} while (search != null);
if (search != null) throw new EntryNotFoundException(); return new SetEntry(search); } } }
public SetEntry<T> begin() { return new SetEntry<T>(Header.Left); } public SetEntry<T> end() { return new SetEntry<T>(Header); }
public String toString() { synchronized(this) { String StringOut = "{";
SetEntry<T> start = begin(); SetEntry<T> end = end(); SetEntry<T> last = end(); last.movePrevious();
while (!start.equals(end)) { String NewStringOut = start.value().toString(); if (!start.equals(last)) NewStringOut = NewStringOut + ","; StringOut = StringOut + NewStringOut; start.moveNext(); }
StringOut = StringOut + "}"; return StringOut; } }
Node after(T data) { Node y = Header; Node x = Header.Parent;
while (x != null) if (Compare.compare(data,((SetNode<T>)x).Data) < 0) { y = x; x = x.Left; } else x = x.Right;
return y; }
Node afterEquals(T data) { Node y = Header; Node x = Header.Parent;
while (x != null) { int c = Compare.compare(data,((SetNode<T>)x).Data); if (c == 0) { y = x; break; } else if (c < 0) { y = x; x = x.Left; } else x = x.Right; }
return y; } Node before(T data) { Node y = Header; Node x = Header.Parent;
while (x != null) if (Compare.compare(data,((SetNode<T>)x).Data) <= 0) x = x.Left; else { y = x; x = x.Right; }
return y; }
Node beforeEquals(T data) { Node y = Header; Node x = Header.Parent;
while (x != null) { int c = Compare.compare(data,((SetNode<T>)x).Data); if (c == 0) { y = x; break; } else if (c < 0) x = x.Left; else { y = x; x = x.Right; } }
return y; } public boolean equals(Set<T> compare) { synchronized (this) { SetEntry<T> first1 = begin(); SetEntry<T> last1 = end(); SetEntry<T> first2 = compare.begin(); SetEntry<T> last2 = compare.end();
Boolean equals = true;
while (!first1.equals(last1) && !first2.equals(last2)) { if (Compare.compare(first1.value(),first2.value()) == 0) { first1.moveNext(); first2.moveNext(); } else { equals = false; break; } }
if (equals) { if (!first1.equals(last1)) equals = false; if (!first2.equals(last2)) equals = false; }
return equals; } } public boolean isSubset(Set<T> S) { synchronized (this) { synchronized (S) { SetEntry<T> first1 = begin(); SetEntry<T> last1 = end(); SetEntry<T> first2 = S.begin(); SetEntry<T> last2 = S.end();
boolean subset = true;
while (!first1.equals(last1) && !first2.equals(last2)) { int order = Compare.compare(first1.value(), first2.value()); if (order < 0) { subset = false; break; } else if (order > 0) first2.moveNext(); else { first1.moveNext(); first2.moveNext(); } }
if (subset) if (!first1.equals(last1)) subset = false;
return subset; } } } }
</lang>