AVL Trees in Java
| AVL tree | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | tree | ||||||||||||||||||||
| Invented | 1962 | ||||||||||||||||||||
| Invented by | Georgy Adelson-Velsky and Evgenii Landis | ||||||||||||||||||||
| Time complexity in big O notation | |||||||||||||||||||||
| |||||||||||||||||||||
In computer science, an AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
The AVL tree is named after its two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper "An algorithm for the organization of information".[1]
AVL Tree Rotations[edit]
The Russian mathematicians Georgy Adelson-Velsky and Evgenii Landis were the first to notice that certain operations can be performed on binary trees without affecting their validity. For example, please consider the following diagram.
The second tree is obtained from the first by rotating the node 7 left and upwards. It is called a left rotation. The things to notice about this transformation are:
- the resultant tree (with 7 at the root) is still in key order and
- the transformation has altered the heights of the left and right subtrees.
There is also a right rotation. Once left and right rotations have been discovered, it is possible to use them to maintain balancing when adding and removing entries from a tree. The type of tree to be considered is constrained in that left and right subtrees of any node are restricted to being at most 1 different in height (both of the trees above satisfy this condition). This type of tree is almost balanced, and is referred to as an AVL tree in honour of the Russian mathematicians mentioned above. It is possible (using rotations) to always satisfy the AVL condition when adding and removing entries from the tree.
Definition of an AVL Set[edit]
An AVL set is a binary tree in which the heights of the left and right subtrees of the root differ by at most 1 and in which the left and right subtrees are again AVL sets.
With each node of an AVL set is associated a balance factor that is either left high, equal or right high according to whether the left subtree has height greater than, equal to or less than the height of the right subtree (respectively).
Balance Factor[edit]
In addition to the tree states mentioned in the definition above, we include a fourth state indicating that the node is a header node. This precludes having to define a separate boolean in the node.
public enum State { Header, LeftHigh, Balanced, RightHigh };
Properties[edit]
Balance factors can be kept up-to-date by knowing the previous balance factors and the change in height – it is not necessary to know the absolute height. For holding the AVL balance information, two bits per node are sufficient.[2]
The height h of an AVL tree with n nodes lies in the interval:[3]
- log2(n+1) ≤ h < c log2(n+2)+b
with the golden ratio φ := (1+√5) ⁄2 ≈ 1.618, c := 1⁄ log2 φ ≈ 1.44, and b := c⁄2 log2 5 – 2 ≈ –0.328. This is because an AVL tree of height h contains at least Fh+2 – 1 nodes where {Fh} is the Fibonacci sequence with the seed values F1 = 1, F2 = 1.
Direction[edit]
When a node is inserted or deleted, it is known whether the left or right node is being inserted or deleted. This leads to the following enum for direction.
public enum Direction { FromLeft, FromRight }
Node Classes[edit]
A non-generic base class will be used for nodes. This is so that non-generic balancing and iteration routines can be developed. This precludes code bloat. The above definition leads to the following base class for node and class for a set node.
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; }
}
Then set nodes are defined to inherit from the base class node, as shown below.
public class SetNode<T> extends Node
{
public T Data;
public SetNode(T dataType, Node Parent)
{
super(Parent);
Data = dataType;
}
}
There is a non-generic base class Node. This facilitates non-generic balancing. The header node is an instance of the class Node, whereas all other nodes are instances of the class SetNode<T>. Apart from the references to the left and right subtrees and parent, a node contains a balance factor. The balance factor is one of the values from the above enumeration State. With just the addition of the member (Balance), sets can be balanced (which is quite efficient in terms of node storage).
AVL Utilities[edit]
Once these definitions are in place, a Utility class using the base node class only can be defined as follows.
public class Utility
{
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;
return x;
}
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;
return x;
}
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;
}
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;
}
}
Explanation of Balancing[edit]
In balanceSet, if the direction is from the left, left set balancing is instigated. If the direction is from the right, right set balancing is performed. This algorithm progresses up the parent chain of the set until the set is balanced. Certain cases can be taken care of immediately. For example, when inserting into the right subtree (FromRight), if the current node is left high, the balance factor is immediately set to State.Balanced and the job is done. Yet other cases require the set to be restructured. Ancilliary procedures balanceLeft and balanceRight have been created for this job. They restructure the set as required.
In balanceLeft and balanceRight, reference rotations are performed based upon the cases of the insertion. The procedures balanceLeft and balanceRight are symmetric under left/right reflection.
In the procedure balanceSet, the case (with FromRight) where a new node has been inserted into the taller subtree of the root and its height has increased will now be considered. Under such conditions, one subtree has a height of 2 more than the other so that the set no longer satisfies the AVL condition. Part of the set must be rebuilt to restore its balance. To be specific, assume the node was inserted into the right subtree, its height has increased and originally it was right high. That is, the case where balanceRight is called from balanceSet will be covered. Let the root of the set be r and let x be the root of the right subtree. There are three cases to be considered depending upon the balance factor of x.
Case1: Right High[edit]
The first case (in balanceRight) is illustrated in the diagram below.
The required action is a left rotation. In the diagram, the node x is rotated upward and r is made the left subtree of x. The left subtree T2 of x becomes the right subtree of r. A left rotation is described in the appropriate C# function (see rotateLeft). Note that when done in the appropriate order, the steps constitute a rotation of three reference values. After the rotation, the height of the rotated set has decreased by 1 whereas it had previously increased because of the insertion, thus the height finishes where it began.
Case2: Left High[edit]
The second case is when the balance factor of x is left high. This case is more complicated. It is required to move two levels to the node w that is the root of the left subtree of x to find the new root. This process is called a double rotation because the transformation can be obtained in two steps (see diagram below). First, x is rotated to the right (so that w becomes its root) and then the set with root r is rotated to the left (moving w up to become the new root).
The code for balanceRight (and balanceLeft) should now be carefully considered with the above diagrams in mind.
Case3: Equal Height[edit]
It would appear that a third case must be considered. The case where the two subtrees of x have equal heights, but this case can never happen. To see why, recall that a new node has just been inserted into the subtree rooted at x and this subtree has height 2 more than the left subtree of the root. The new node was placed into either the left or right subtree of x. Its placement only increased the height of one subtree of x. If those subtrees had equal heights after the insertion then the height of the full subtree rooted at x was not changed by the insertion - contrary to the hypothesis. While the case of equal height does not occur for insertions, it does occur for deletions, hence it has been coded in the algorithms.
Set Enumerators[edit]
Because sets will be defined to be enumerable, it is required to define a set enumerator. That definition is shown below.
import java.util.Iterator;
@SuppressWarnings("unchecked")
public class SetEntry<T> implements Iterator<T>
{
public SetEntry(Node n) { _Node = n; }
public T value()
{
return ((SetNode<T>)_Node).Data;
}
public Boolean isHeader() { return _Node.isHeader(); }
public boolean equals(SetEntry<T> 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<T>)_Node).Data;
}
public T previous()
{
_Node = Utility.previousNode(_Node);
return ((SetNode<T>)_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;
}
Set Operations[edit]
Several set operations will be defined. These are enumerated as follows.
public enum SetOperation
{
Union,
Intersection,
SymmetricDifference,
Difference
}
Exceptions[edit]
The following three exception classes need to be defined in separate files.
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.");
}
}
Cloning, Default Comparator[edit]
The Cloneable and Cloner interfaces are defined as well as the class DefaultCloner. Each of these goes in a separate file. The DefaultComparator class is also defined.
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;
}
}
The Set Class[edit]
After all the machinery is in place, the class Set can now be defined.
import java.util.Iterator;
import java.util.Comparator;
import java.io.*;
@SuppressWarnings("unchecked")
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;
}
}
}
}
The code for balancing the set upon removal is also in place. There are separate diagrams for the removals available in.[4]
Comparison to other structures[edit]
Both AVL trees and red–black trees are self-balancing binary search trees and they are very similar mathematically.[5] The operations to balance the trees are different, but both occur on the average in O(1) with maximum in O(log n). The real difference between the two is the limiting height.
For a tree of size n ≥ 1
- an AVL tree’s height is at most
- where the golden ratio, and .
- a red–black tree’s height is at most
AVL trees are more rigidly balanced than red–black trees, leading to faster retrieval. They are similar on insertion and deletion.
See also[edit]
External links[edit]
- AVL tree demonstration (requires Flash)
- See I# in Java for the project already made up - supports NetBeans, IntelliJ and Eclipse. The online reference is at I# for Java.
References[edit]
- ↑ Georgy Adelson-Velsky, G.; Evgenii Landis (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences (in русский). 146: 263–266. English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.
- ↑ More precisely: if the AVL balance information is kept in the child nodes – with meaning "when going upward there is an additional increment in height", this can be done with one bit. Nevertheless, the modifying operations can be programmed more efficiently if the balance information can be checked with one test.
- ↑ Knuth, Donald E. (2000). Sorting and searching (2. ed., 6. printing, newly updated and rev. ed.). Boston [u.a.]: Addison-Wesley. p. 460. ISBN 0-201-89685-0. Search this book on
- ↑ Robert L. Kruse, Data Structures and Program Design, Prentice-Hally, 1987, ISBN 0-13-197146-8, page 353, chapter 9: Binary Trees.
- ↑ In fact, every AVL tree can be colored red–black.
- ↑ Red–black tree#Proof of asymptotic bounds
This article "AVL Trees in Java" is from Wikipedia. The list of its authors can be seen in its historical. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
