AVL Tree in CSharp

AVL tree
Type	tree
Invented	1962
Invented by	Georgy Adelson-Velsky and Evgenii Landis
Time complexity in big O notation
Algorithm Average Worst case Space O(n) O(n) Search O(log n) O(log n) Insert O(log n) O(log n) Delete O(log n) O(log n)

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".

AVL Tree Rotations

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

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

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

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.

The height h of an AVL tree with n nodes lies in the interval:

log₂(n+1) ≤ h < c log₂(n+2)+b

with the golden ratio φ := (1+√5) ⁄₂ ≈ 1.618, c := ¹⁄ log₂ φ ≈ 1.44,  and  b := ^c⁄₂ log₂ 5 – 2 ≈ –0.328. This is because an AVL tree of height h contains at least F_h+2 – 1 nodes where {F_h} is the Fibonacci sequence with the seed values F₁ = 1, F₂ = 1.

Direction

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

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 bool IsHeader
    { get { return Balance == State.Header; } }
}

Then set nodes are defined to inherit from the base class node, as shown below.

public class SetNode<T> : Node
{
    public T Data;
 
    public SetNode() { }
 
    public SetNode(T dataType, Node Parent) : base(Parent)
    {
        Data = dataType;
    }
 
    public override int GetHashCode()
    {
        return Data.GetHashCode();
    }
}

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

Once these definitions are in place, a Utility class using the base node class only can be defined as follows.

class Utility // Nongeneric Tree Balancing
{
    static void RotateLeft(ref 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;
    }
 
    static void RotateRight(ref 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;
    }
 
    static void BalanceLeft(ref Node Root)
    {
        Node Left = Root.Left;
 
        switch (Left.Balance)
        {
            case State.LeftHigh:
                Root.Balance = State.Balanced;
                Left.Balance = State.Balanced;
                RotateRight(ref Root);
                break;
 
            case State.RightHigh:
                {
                    Node subRight = Left.Right;
                    switch (subRight.Balance)
                    {
                        case State.Balanced:
                            Root.Balance = State.Balanced;
                            Left.Balance = State.Balanced;
                            break;
 
                        case State.RightHigh:
                            Root.Balance = State.Balanced;
                            Left.Balance = State.LeftHigh;
                            break;
 
                        case State.LeftHigh:
                            Root.Balance = State.RightHigh;
                            Left.Balance = State.Balanced;
                            break;
                    }
                    subRight.Balance = State.Balanced;
                    RotateLeft(ref Left);
                    Root.Left = Left;
                    RotateRight(ref Root);
                }
                break;
 
            case State.Balanced:
                Root.Balance = State.LeftHigh;
                Left.Balance = State.RightHigh;
                RotateRight(ref Root);
                break;
        }
    }
 
    static void BalanceRight(ref Node Root)
    {
        Node Right = Root.Right;
 
        switch (Right.Balance)
        {
            case State.RightHigh:
                Root.Balance = State.Balanced;
                Right.Balance = State.Balanced;
                RotateLeft(ref Root);
                break;
 
            case State.LeftHigh:
                {
                    Node subLeft = Right.Left; // Left Subtree of Right
                    switch (subLeft.Balance)
                    {
                        case State.Balanced:
                            Root.Balance = State.Balanced;
                            Right.Balance = State.Balanced;
                            break;
 
                        case State.LeftHigh:
                            Root.Balance = State.Balanced;
                            Right.Balance = State.RightHigh;
                            break;
 
                        case State.RightHigh:
                            Root.Balance = State.LeftHigh;
                            Right.Balance = State.Balanced;
                            break;
                    }
                    subLeft.Balance = State.Balanced;
                    RotateRight(ref Right);
                    Root.Right = Right;
                    RotateLeft(ref Root);
                }
                break;
 
            case State.Balanced:
                Root.Balance = State.RightHigh;
                Right.Balance = State.LeftHigh;
                RotateLeft(ref Root);
                break;
        }
    }
 
    public static void BalanceSet(Node Root, Direction From)
    {
        bool 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 State.LeftHigh:
                        if (Parent.IsHeader)
                            BalanceLeft(ref Parent.Parent);
                        else if (Parent.Left == Root)
                            BalanceLeft(ref Parent.Left);
                        else
                            BalanceLeft(ref Parent.Right);
                        Taller = false;
                        break;
 
                    case State.Balanced:
                        Root.Balance = State.LeftHigh;
                        Taller = true;
                        break;
 
                    case State.RightHigh:
                        Root.Balance = State.Balanced;
                        Taller = false;
                        break;
                }
            }
            else
            {
                switch (Root.Balance)
                {
                    case State.LeftHigh:
                        Root.Balance = State.Balanced;
                        Taller = false;
                        break;
 
                    case State.Balanced:
                        Root.Balance = State.RightHigh;
                        Taller = true;
                        break;
 
                    case State.RightHigh:
                        if (Parent.IsHeader)
                            BalanceRight(ref Parent.Parent);
                        else if (Parent.Left == Root)
                            BalanceRight(ref Parent.Left);
                        else
                            BalanceRight(ref Parent.Right);
                        Taller = false;
                        break;
                }
            }
 
            if (Taller) // skip up a level
            {
                if (Parent.IsHeader)
                    Taller = false;
                else
                {
                    Root = Parent;
                    From = NextFrom;
                }
            }
        }
    }
 
    public static void BalanceSetRemove(Node Root, Direction From)
    {
        if (Root.IsHeader) return;
 
        bool 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 State.LeftHigh:
                        Root.Balance = State.Balanced;
                        Shorter = true;
                        break;
 
                    case State.Balanced:
                        Root.Balance = State.RightHigh;
                        Shorter = false;
                        break;
 
                    case State.RightHigh:
                        if (Root.Right.Balance == State.Balanced)
                            Shorter = false;
                        else
                            Shorter = true;
                        if (Parent.IsHeader)
                            BalanceRight(ref Parent.Parent);
                        else if (Parent.Left == Root)
                            BalanceRight(ref Parent.Left);
                        else
                            BalanceRight(ref Parent.Right);
                        break;
                }
            }
            else
            {
                switch (Root.Balance)
                {
                    case State.RightHigh:
                        Root.Balance = State.Balanced;
                        Shorter = true;
                        break;
 
                    case State.Balanced:
                        Root.Balance = State.LeftHigh;
                        Shorter = false;
                        break;
 
                    case State.LeftHigh:
                        if (Root.Left.Balance == State.Balanced)
                            Shorter = false;
                        else
                            Shorter = true;
                        if (Parent.IsHeader)
                            BalanceLeft(ref Parent.Parent);
                        else if (Parent.Left == Root)
                            BalanceLeft(ref Parent.Left);
                        else
                            BalanceLeft(ref Parent.Right);
                        break;
                }
            }
 
            if (Shorter)
            {
                if (Parent.IsHeader)
                    Shorter = false;
                else
                {
                    From = NextFrom;
                    Root = Parent;
                }
            }
        }
    }
 
    public static Node PreviousItem(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;
    }
 
    public static Node NextItem(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 static ulong Depth(Node Root)
    {
        if (Root != null)
        {
            ulong Left = Root.Left != null ? Depth(Root.Left) : 0;
            ulong Right = Root.Right != null ? Depth(Root.Right) : 0;
            return Left < Right ? Right + 1 : Left + 1;
        }
        else
            return 0;
    }
 
    static void SwapNodeReference(ref Node First,
                                  ref Node Second)
    { Node Temporary = First; First = Second; Second = Temporary; }
 
    public 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;
 
            SwapNodeReference(ref A.Right, ref B.Right);
        }
        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;
 
            SwapNodeReference(ref A.Left, ref B.Left);
        }
        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;
 
            SwapNodeReference(ref A.Right, ref B.Right);
        }
        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;
 
            SwapNodeReference(ref A.Left, ref B.Left);
        }
        else
        {
            if (A.Parent == B.Parent)
                SwapNodeReference(ref A.Parent.Left, ref A.Parent.Right);
            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;
 
            SwapNodeReference(ref A.Left, ref B.Left);
            SwapNodeReference(ref A.Right, ref B.Right);
            SwapNodeReference(ref A.Parent, ref B.Parent);
        }
 
        State Balance = A.Balance;
        A.Balance = B.Balance;
        B.Balance = Balance;
    }
}

Explanation of Balancing

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

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

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

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

Because sets will be defined to be enumerable, it is required to define a set enumerator. That definition is shown below.

public struct SetEntry<T> : IEnumerator<T>
{
    public SetEntry(Node N) { _Node = N; }
 
    public T Value
    {
        get
        {
            return ((SetNode<T>)_Node).Data;
        }
    }
 
    public bool IsEnd { get { return _Node.IsHeader; } }
 
    public bool MoveNext()
    {
        _Node = Utility.NextItem(_Node);
        return _Node.IsHeader ? false : true;
    }
 
    public bool MovePrevious()
    {
        _Node = Utility.PreviousItem(_Node);
        return _Node.IsHeader ? false : true;
    }
 
    public static SetEntry<T> operator ++(SetEntry<T> entry)
    {
        entry._Node = Utility.NextItem(entry._Node);
        return entry;
    }
 
    public static SetEntry<T> operator --(SetEntry<T> entry)
    {
        entry._Node = Utility.PreviousItem(entry._Node);
        return entry;
    }
 
    public void Reset()
    {
        while (!MoveNext()) ;
    }
 
    object System.Collections.IEnumerator.Current
    { get { return ((SetNode<T>)_Node).Data; } }
 
    T IEnumerator<T>.Current
    { get { return ((SetNode<T>)_Node).Data; } }
 
    public static bool operator ==(SetEntry<T> x, SetEntry<T> y) { return x._Node == y._Node; }
    public static bool operator !=(SetEntry<T> x, SetEntry<T> y) { return x._Node != y._Node; }
 
    public override bool Equals(object o) { return _Node == ((SetEntry<T>)o)._Node; }
 
    public override int GetHashCode() { return _Node.GetHashCode(); }
 
    public static SetEntry<T> operator +(SetEntry<T> C, ulong Increment)
    {
        SetEntry<T> Result = new SetEntry<T>(C._Node);
        for (ulong i = 0; i < Increment; i++) ++Result;
        return Result;
    }
 
    public static SetEntry<T> operator +(ulong Increment, SetEntry<T> C)
    {
        SetEntry<T> Result = new SetEntry<T>(C._Node);
        for (ulong i = 0; i < Increment; i++) ++Result;
        return Result;
    }
 
    public static SetEntry<T> operator -(SetEntry<T> C, ulong Decrement)
    {
        SetEntry<T> Result = new SetEntry<T>(C._Node);
        for (ulong i = 0; i < Decrement; i++) --Result;
        return Result;
    }
 
    public override string ToString()
    {
        return Value.ToString();
    }
 
    public void Dispose() { }
 
    public Node _Node;
}

Set Operations

Several set operations will be defined. These are enumerated as follows.

public enum SetOperation
{
    Union,
    Intersection,
    SymmetricDifference,
    Difference,
    Equality,
    Inequality,
    Subset,
    Superset
}

Exceptions

The following exception classes need to be defined.

public class EntryNotFoundException : Exception
{
    static String message = "The requested entry could not be located in the specified collection.";
 
    public EntryNotFoundException() : base(message) { }
}
 
public class EntryAlreadyExistsException : Exception
{
    static String message = "The requested entry already resides in the collection.";
 
    public EntryAlreadyExistsException() : base(message) { }
}
 
public class InvalidEndItemException : Exception
{
    static String message = "The validation routines detected that the end item of a tree is invalid.";
 
    public InvalidEndItemException() : base(message) { }
}
 
public class InvalidEmptyTreeException : Exception
{
    static String message = "The validation routines detected that an empty tree is invalid.";
 
    public InvalidEmptyTreeException() : base(message) { }
}
 
public class OutOfKeyOrderException : Exception
{
    static String message = "A trees was found to be out of key order.";
 
    public OutOfKeyOrderException() : base(message) { }
}
 
public class TreeInvalidParentException : Exception
{
    static String message = "The validation routines detected that the Parent structure of a tree is invalid.";
 
    public TreeInvalidParentException() : base(message) { }
}
 
public class TreeOutOfBalanceException : Exception
{
    static String message = "The validation routines detected that the tree is out of State.";
 
    public TreeOutOfBalanceException() : base(message) { }
}
 
public class InvalidSetOperationException : Exception
{
    static String message = "An invalid set operation was requested.";
 
    public InvalidSetOperationException() : base(message) { }
}

The Set Class

After all the machinery is in place, the class Set can now be defined.

class Set<T> : IEnumerable<T>
{
    IComparer<T> Comparer;
    Node Header;
    ulong Nodes;
 
    //*** Constructors ***
 
    public Set()
    {
        Comparer = Comparer<T>.Default;
        Header = new Node();
        Nodes = 0;
    }
 
    public Set(IComparer<T> c)
    {
        Comparer = c;
        Header = new Node();
        Nodes = 0;
    }
 
    //*** Properties ***
 
    SetNode<T> Root
    {
        get { return (SetNode<T>)Header.Parent; }
        set { Header.Parent = value; }
    }
 
    Node LeftMost
    {
        get { return Header.Left; }
        set { Header.Left = value; }
    }
 
    Node RightMost
    {
        get { return Header.Right; }
        set { Header.Right = value; }
    }
 
    public SetEntry<T> Begin
    { get { return new SetEntry<T>(Header.Left); } }
 
    public SetEntry<T> End
    { get { return new SetEntry<T>(Header); } }
 
    public ulong Length { get { return Nodes; } }
 
    public ulong Depth { get { return Utility.Depth(Root); } }
 
    //*** Operators ***
 
    public bool this[T key] { get { return Search(key); } }
 
    public static Set<T> operator +(Set<T> set, T t)
    {
        set.Add(t); return set;
    }
 
    public static Set<T> operator -(Set<T> set, T t)
    {
        set.Remove(t); return set;
    }
 
    public static Set<T> operator |(Set<T> A, Set<T> B)
    {
        Set<T> U = new Set<T>(A.Comparer);
        CombineSets(A, B, U, SetOperation.Union);
        return U;
    }
 
    public static Set<T> operator &(Set<T> A, Set<T> B)
    {
        Set<T> I = new Set<T>(A.Comparer);
        CombineSets(A, B, I, SetOperation.Intersection);
        return I;
    }
 
    public static Set<T> operator ^(Set<T> A, Set<T> B)
    {
        Set<T> S = new Set<T>(A.Comparer);
        CombineSets(A, B, S, SetOperation.SymmetricDifference);
        return S;
    }
 
    public static Set<T> operator -(Set<T> A, Set<T> B)
    {
        Set<T> S = new Set<T>(A.Comparer);
        CombineSets(A, B, S, SetOperation.Difference);
        return S;
    }
 
    public static bool operator ==(Set<T> A, Set<T> B)
    {
        return CheckSets(A, B, SetOperation.Equality);
    }
 
    public static bool operator !=(Set<T> A, Set<T> B)
    {
        return CheckSets(A, B, SetOperation.Inequality);
    }
 
    public override bool Equals(object o)
    {
        return CheckSets(this, (Set<T>)o, SetOperation.Equality);
    }
 
 
    //*** Methods ***
 
    public void Add(T key)
    {
        if (Root == null)
        {
            Root = new SetNode<T>(key, Header);
            LeftMost = RightMost = Root;
        }
        else
        {
            SetNode<T> Search = Root;
            for (; ; )
            {
                int Compare = Comparer.Compare(key, Search.Data);
 
                if (Compare == 0) // Item Exists
                    throw new EntryAlreadyExistsException();
 
                else if (Compare < 0)
                {
                    if (Search.Left != null)
                        Search = (SetNode<T>)Search.Left;
                    else
                    {
                        Search.Left = new SetNode<T>(key, Search);
                        if (LeftMost == Search) LeftMost = (SetNode<T>)Search.Left;
                        Utility.BalanceSet(Search, Direction.FromLeft);
                        Nodes++;
                    }
                }
 
                else
                {
                    if (Search.Right != null)
                        Search = (SetNode<T>)Search.Right;
                    else
                    {
                        Search.Right = new SetNode<T>(key, Search);
                        if (RightMost == Search) RightMost = (SetNode<T>)Search.Right;
                        Utility.BalanceSet(Search, Direction.FromRight);
                        Nodes++;
                        break;
                    }
                }
            }
        }
    }
 
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    { return new SetEntry<T>(Header); }
 
    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    { return new SetEntry<T>(Header); }
 
    public override int GetHashCode()
    {
        return GetHashCode((SetNode<T>)Header.Parent);
    }
 
    int GetHashCode(SetNode<T> Root)
    {
        if (Root != null)
        {
            int HashCode = Root.GetHashCode();
 
            if (Root.Left != null)
                HashCode += GetHashCode((SetNode<T>)Root.Left);
 
            if (Root.Right != null)
                HashCode += GetHashCode((SetNode<T>)Root.Right);
 
            return HashCode;
        }
 
        return 0;
    }
 
 
    public void Remove(T key)
    {
        SetNode<T> root = Root;
 
        for (; ; )
        {
            if (root == null)
                throw new EntryNotFoundException();
 
            int Compare = Comparer.Compare(key, 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)
                {
                    SetNode<T> replace = (SetNode<T>)root.Left;
                    while (replace.Right != null) replace = (SetNode<T>)replace.Right;
                    Utility.SwapNodes(root, replace);
                }
 
                SetNode<T> Parent = (SetNode<T>)root.Parent;
 
                Direction From = (Parent.Left == root) ? Direction.FromLeft : Direction.FromRight;
 
                if (LeftMost == root)
                {
                    SetEntry<T> e = new SetEntry<T>(root); e.MoveNext();
 
                    if (e._Node.IsHeader)
                    { LeftMost = Header; RightMost = Header; }
                    else
                        LeftMost = e._Node;
                }
                else if (RightMost == root)
                {
                    SetEntry<T> e = new SetEntry<T>(root); e.MovePrevious();
 
                    if (e._Node.IsHeader)
                    { LeftMost = Header; RightMost = Header; }
                    else
                        RightMost = e._Node;
                }
 
                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.BalanceSetRemove(Parent, From);
                Nodes--;
                break;
            }
        }
    }
 
    public bool Search(T key)
    {
        if (Root == null)
            return false;
        else
        {
            SetNode<T> Search = Root;
 
            do
            {
                int Result = Comparer.Compare(key, Search.Data);
 
                if (Result < 0) Search = (SetNode<T>)Search.Left;
 
                else if (Result > 0) Search = (SetNode<T>)Search.Right;
 
                else break;
 
            } while (Search != null);
 
            if (Search == null)
                return false;
            else
                return true;
        }
    }
 
    public override string ToString()
    {
        string StringOut = "{";
 
        SetEntry<T> start = Begin;
        SetEntry<T> end = End;
        SetEntry<T> last = End - 1;
 
        while (start != end)
        {
            string new_StringOut = start.Value.ToString();
            if (start != last) new_StringOut = new_StringOut + ",";
            StringOut = StringOut + new_StringOut;
            ++start;
        }
 
        StringOut = StringOut + "}";
        return StringOut;
    }
 
    public void Validate()
    {
        if (Nodes == 0 || Root == null)
        {
            if (Nodes != 0) { throw new InvalidEmptyTreeException(); }
            if (Root != null) { throw new InvalidEmptyTreeException(); }
            if (LeftMost != Header) { throw new InvalidEndItemException(); }
            if (RightMost != Header) { throw new InvalidEndItemException(); }
        }
 
        Validate(Root);
 
        if (Root != null)
        {
            SetNode<T> x = Root;
            while (x.Left != null) x = (SetNode<T>)x.Left;
 
            if (LeftMost != x) throw new InvalidEndItemException();
 
            SetNode<T> y = Root;
            while (y.Right != null) y = (SetNode<T>)y.Right;
 
            if (RightMost != y) throw new InvalidEndItemException();
        }
    }
 
    void Validate(SetNode<T> root)
    {
        if (root == null) return;
 
        if (root.Left != null)
        {
            SetNode<T> Left = (SetNode<T>)root.Left;
 
            if (Comparer.Compare(Left.Data, root.Data) >= 0)
                throw new OutOfKeyOrderException();
 
            if (Left.Parent != root)
                throw new TreeInvalidParentException();
 
            Validate((SetNode<T>)root.Left);
        }
 
        if (root.Right != null)
        {
            SetNode<T> Right = (SetNode<T>)root.Right;
 
            if (Comparer.Compare(Right.Data, root.Data) <= 0)
                throw new OutOfKeyOrderException();
 
            if (Right.Parent != root)
                throw new TreeInvalidParentException();
 
            Validate((SetNode<T>)root.Right);
        }
 
        ulong depth_Left = root.Left != null ? Utility.Depth(root.Left) : 0;
        ulong depth_Right = root.Right != null ? Utility.Depth(root.Right) : 0;
 
        if (depth_Left > depth_Right && depth_Left - depth_Right > 2)
            throw new TreeOutOfBalanceException();
 
        if (depth_Left < depth_Right && depth_Right - depth_Left > 2)
            throw new TreeOutOfBalanceException();
    }
 
    public static void CombineSets(Set<T> A,
                                   Set<T> B,
                                   Set<T> R,
                                   SetOperation operation)
    {
        IComparer<T> TComparer = R.Comparer;
        SetEntry<T> First1 = A.Begin;
        SetEntry<T> Last1 = A.End;
        SetEntry<T> First2 = B.Begin;
        SetEntry<T> Last2 = B.End;
 
        switch (operation)
        {
            case SetOperation.Union:
                while (First1 != Last1 && First2 != Last2)
                {
                    int Order = TComparer.Compare(First1.Value, First2.Value);
 
                    if (Order < 0)
                    {
                        R.Add(First1.Value);
                        First1.MoveNext();
                    }
 
                    else if (Order > 0)
                    {
                        R.Add(First2.Value);
                        First2.MoveNext();
                    }
 
                    else
                    {
                        R.Add(First1.Value);
                        First1.MoveNext();
                        First2.MoveNext();
                    }
                }
                while (First1 != Last1)
                {
                    R.Add(First1.Value);
                    First1.MoveNext();
                }
                while (First2 != Last2)
                {
                    R.Add(First2.Value);
                    First2.MoveNext();
                }
                return;
 
            case SetOperation.Intersection:
                while (First1 != Last1 && First2 != Last2)
                {
                    int Order = TComparer.Compare(First1.Value, First2.Value);
 
                    if (Order < 0)
                        First1.MoveNext();
 
                    else if (Order > 0)
                        First2.MoveNext();
 
                    else
                    {
                        R.Add(First1.Value);
                        First1.MoveNext();
                        First2.MoveNext();
                    }
                }
                return;
 
            case SetOperation.SymmetricDifference:
                while (First1 != Last1 && First2 != Last2)
                {
                    int Order = TComparer.Compare(First1.Value, First2.Value);
 
                    if (Order < 0)
                    {
                        R.Add(First1.Value);
                        First1.MoveNext();
                    }
 
                    else if (Order > 0)
                    {
                        R.Add(First2.Value);
                        First2.MoveNext();
                    }
 
                    else
                    { First1.MoveNext(); First2.MoveNext(); }
                }
 
                while (First1 != Last1)
                {
                    R.Add(First1.Value);
                    First1.MoveNext();
                }
 
                while (First2 != Last2)
                {
                    R.Add(First2.Value);
                    First2.MoveNext();
                }
                return;
 
            case SetOperation.Difference:
                while (First1 != Last1 && First2 != Last2)
                {
                    int Order = TComparer.Compare(First1.Value, First2.Value);
 
                    if (Order < 0)
                    {
                        R.Add(First1.Value);
                        First1.MoveNext();
                    }
 
                    else if (Order > 0)
                    {
                        R.Add(First1.Value);
                        First1.MoveNext();
                        First2.MoveNext();
                    }
 
                    else
                    { First1.MoveNext(); First2.MoveNext(); }
                }
 
                while (First1 != Last1)
                {
                    R.Add(First1.Value);
                    First1.MoveNext();
                }
                return;
        }
 
        throw new InvalidSetOperationException();
    }
 
    public static bool CheckSets(Set<T> A,
                                 Set<T> B,
                                 SetOperation operation)
    {
        IComparer<T> TComparer = A.Comparer;
        SetEntry<T> First1 = A.Begin;
        SetEntry<T> Last1 = A.End;
        SetEntry<T> First2 = B.Begin;
        SetEntry<T> Last2 = B.End;
 
        switch (operation)
        {
            case SetOperation.Equality:
            case SetOperation.Inequality:
                {
                    bool Equals = true;
 
                    while (First1 != Last1 && First2 != Last2)
                    {
                        if (TComparer.Compare(First1.Value, First2.Value) == 0)
                        { First1.MoveNext(); First2.MoveNext(); }
                        else
                        { Equals = false; break; }
                    }
 
                    if (Equals)
                    {
                        if (First1 != Last1) Equals = false;
                        if (First2 != Last2) Equals = false;
                    }
 
                    if (operation == SetOperation.Equality)
                        return Equals;
                    else
                        return !Equals;
                }
 
            case SetOperation.Subset:
            case SetOperation.Superset:
                {
                    bool Subset = true;
 
                    while (First1 != Last1 && First2 != Last2)
                    {
                        int Order = TComparer.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 != Last1) Subset = false;
 
                    if (operation == SetOperation.Subset)
                        return Subset;
                    else
                        return !Subset;
                }
        }
 
        throw new InvalidSetOperationException();
    }
}

The code for balancing the set upon removal is also in place. There are separate diagrams for the removals available in.

Comparison to other structures

Both AVL trees and red–black trees are self-balancing binary search trees and they are very similar mathematically. 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

  ${\begin{array}{ll}h&\leqq \;c\log _{2}(n+d)+b\\&<\;c\log _{2}(n+2)+b\end{array}}$

where $\varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618$  the golden ratio, $c:={\tfrac {1}{\log _{2}\varphi }}\approx 1.44,$   $b:={\tfrac {c}{2}}\log _{2}5-2\approx \;-0.328,$ and  $d:=1+{\tfrac {1}{\varphi ^{4}{\sqrt {5}}}}\approx 1.07$.

• a red–black tree’s height is at most

  ${\begin{array}{ll}h&\leqq \;2\log _{2}(n+1)\end{array}}$

AVL trees are more rigidly balanced than red–black trees, leading to faster retrieval. They are similar on insertion and deletion.

See also

• Trees
• Tree rotation
• Red–black tree
• Splay tree
• Scapegoat tree
• B-tree
• T-tree
• List of data structures

External links

• AVL tree demonstration (requires Flash)
• See I# in C# for the project already made up - supports Visual Studio. The online reference is at I# for C#.

References

This article "AVL Tree in CSharp" 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.

📰 Article(s) of the same category(ies)

• AVL Trees in C++
• AVL Trees in Managed C++
• Deep column station
• Hydro-slotted perforation
• AVL Trees in Java

---