AVL tree

AVL tree
You are encouraged to solve this task according to the task description, using any language you may know.

This page uses content from Wikipedia. The original article was at AVL tree. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

In computer science, an AVL tree is a self-balancing binary search tree. 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.

AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications. Similar to red-black trees, AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced; that is, sibling nodes can have hugely differing numbers of descendants.

Task: Implement an AVL tree in the language of choice and provide at least basic operations.

Agda

This implementation uses the type system to enforce the height invariants, though not the BST invariants <lang agda> module Avl where

-- The Peano naturals data Nat : Set where

z : Nat
s : Nat -> Nat

-- An AVL tree's type is indexed by a natural. -- Avl N is the type of AVL trees of depth N. There arj 3 different -- node constructors: -- Left: The left subtree is one level deeper than the right -- Balanced: The subtrees have the same depth -- Right: The right Subtree is one level deeper than the left -- Since the AVL invariant is that the depths of a node's subtrees -- always differ by at most 1, this perfectly encodes the AVL depth invariant. data Avl : Nat -> Set where

 Empty : Avl z
 Left : {X : Nat} -> Nat -> Avl (s X) -> Avl X -> Avl (s (s X))
 Balanced : {X : Nat} -> Nat -> Avl X -> Avl X -> Avl (s X)
 Right : {X : Nat} -> Nat -> Avl X -> Avl (s X) -> Avl (s (s X))

-- A wrapper type that hides the AVL tree invariant. This is the interface -- exposed to the user. data Tree : Set where

 avl : {N : Nat} -> Avl N -> Tree

-- Comparison result data Ord : Set where

 Less : Ord
 Equal : Ord
 Greater : Ord

-- Comparison function cmp : Nat -> Nat -> Ord cmp z (s X) = Less cmp z z = Equal cmp (s X) z = Greater cmp (s X) (s Y) = cmp X Y

-- Insertions can either leave the depth the same or -- increase it by one. Encode this in the type. data InsertResult : Nat -> Set where

 Same : {X : Nat} -> Avl X -> InsertResult X
 Bigger : {X : Nat} -> Avl (s X) -> InsertResult X

-- If the left subtree is 2 levels deeper than the right, rotate to the right. -- balance-left X L R means X is the root, L is the left subtree and R is the right. balance-left : {N : Nat} -> Nat -> Avl (s (s N)) -> Avl N -> InsertResult (s (s N)) balance-left X (Right Y A (Balanced Z B C)) D = Same (Balanced Z (Balanced X A B) (Balanced Y C D)) balance-left X (Right Y A (Left Z B C)) D = Same (Balanced Z (Balanced X A B) (Right Y C D)) balance-left X (Right Y A (Right Z B C)) D = Same (Balanced Z (Left X A B) (Balanced Y C D)) balance-left X (Left Y (Balanced Z A B) C) D = Same (Balanced Z (Balanced X A B) (Balanced Y C D)) balance-left X (Left Y (Left Z A B) C) D = Same (Balanced Z (Left X A B) (Balanced Y C D)) balance-left X (Left Y (Right Z A B) C) D = Same (Balanced Z (Right X A B) (Balanced Y C D)) balance-left X (Balanced Y (Balanced Z A B) C) D = Bigger (Right Z (Balanced X A B) (Left Y C D)) balance-left X (Balanced Y (Left Z A B) C) D = Bigger (Right Z (Left X A B) (Left Y C D)) balance-left X (Balanced Y (Right Z A B) C) D = Bigger (Right Z (Right X A B) (Left Y C D))

-- Symmetric with balance-left balance-right : {N : Nat} -> Nat -> Avl N -> Avl (s (s N)) -> InsertResult (s (s N)) balance-right X A (Left Y (Left Z B C) D) = Same (Balanced Z (Balanced X A B) (Right Y C D)) balance-right X A (Left Y (Balanced Z B C) D) = Same(Balanced Z (Balanced X A B) (Balanced Y C D)) balance-right X A (Left Y (Right Z B C) D) = Same(Balanced Z (Left X A B) (Balanced Y C D)) balance-right X A (Balanced Z B (Left Y C D)) = Bigger(Left Z (Right X A B) (Left Y C D)) balance-right X A (Balanced Z B (Balanced Y C D)) = Bigger (Left Z (Right X A B) (Balanced Y C D)) balance-right X A (Balanced Z B (Right Y C D)) = Bigger (Left Z (Right X A B) (Right Y C D)) balance-right X A (Right Z B (Left Y C D)) = Same (Balanced Z (Balanced X A B) (Left Y C D)) balance-right X A (Right Z B (Balanced Y C D)) = Same (Balanced Z (Balanced X A B) (Balanced Y C D)) balance-right X A (Right Z B (Right Y C D)) = Same (Balanced Z (Balanced X A B) (Right Y C D))

-- insert' T N does all the work of inserting the element N into the tree T. insert' : {N : Nat} -> Avl N -> Nat -> InsertResult N insert' Empty N = Bigger (Balanced N Empty Empty) insert' (Left Y L R) X with cmp X Y insert' (Left Y L R) X | Less with insert' L X insert' (Left Y L R) X | Less | Same L' = Same (Left Y L' R) insert' (Left Y L R) X | Less | Bigger L' = balance-left Y L' R insert' (Left Y L R) X | Equal = Same (Left Y L R) insert' (Left Y L R) X | Greater with insert' R X insert' (Left Y L R) X | Greater | Same R' = Same (Left Y L R') insert' (Left Y L R) X | Greater | Bigger R' = Same (Balanced Y L R') insert' (Balanced Y L R) X with cmp X Y insert' (Balanced Y L R) X | Less with insert' L X insert' (Balanced Y L R) X | Less | Same L' = Same (Balanced Y L' R) insert' (Balanced Y L R) X | Less | Bigger L' = Bigger (Left Y L' R) insert' (Balanced Y L R) X | Equal = Same (Balanced Y L R) insert' (Balanced Y L R) X | Greater with insert' R X insert' (Balanced Y L R) X | Greater | Same R' = Same (Balanced Y L R') insert' (Balanced Y L R) X | Greater | Bigger R' = Bigger (Right Y L R') insert' (Right Y L R) X with cmp X Y insert' (Right Y L R) X | Less with insert' L X insert' (Right Y L R) X | Less | Same L' = Same (Right Y L' R) insert' (Right Y L R) X | Less | Bigger L' = Same (Balanced Y L' R) insert' (Right Y L R) X | Equal = Same (Right Y L R) insert' (Right Y L R) X | Greater with insert' R X insert' (Right Y L R) X | Greater | Same R' = Same (Right Y L R') insert' (Right Y L R) X | Greater | Bigger R' = balance-right Y L R'

-- Wrapper around insert' to use the depth-agnostic type Tree. insert : Tree -> Nat -> Tree insert (avl T) X with insert' T X ... | Same T' = avl T' ... | Bigger T' = avl T' </lang>

C#

This code in C# has non-generic AVL Tree Balancing

<lang csharp> // Finite Ordered Sets - 4State - Balanced

using System; using System.Collections.Generic;

public enum Direction { FromLeft, FromRight };

public enum State { Header, LeftHigh, Balanced, RightHigh };

public enum SetOperation {

   Union,
   Intersection,
   SymmetricDifference,
   Difference,
   Equality,
   Inequality,
   Subset,
   Superset

}

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; } }

}

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();
   }

}

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;
   }

}

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;

}

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();
   }

}

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) { }

}

class Program {

   static void Main()
   {
       Set<string> s = new Set<string>() {"S0","S1","S2","S3","S4",
                                          "S5","S6","S7","S8","S9"};

       Console.WriteLine("Depth = {0}", s.Depth);

       s.Validate();

       for (int i = 0; i < 10; i += 2)
           s.Remove("S" + i.ToString());

       Console.WriteLine("Depth = {0}", s.Depth);

       s.Validate();

       Console.WriteLine("{0}", s);

       Set<int> A = new Set<int>() { 1, 3, 5, 7 };
       Set<int> B = new Set<int>() { 2, 4, 6, 8 };

       Set<int> U = A | B;

       Console.WriteLine("{0} | {1} == {2}", A, B, U);
   }

} </lang>

C

See AVL tree/C

C++

Translation of: D

<lang cpp>

1. include <algorithm>
2. include <iostream>

/* AVL node */ template <class T> class AVLnode { public:

   T key;
   int balance;
   AVLnode *left, *right, *parent;

   AVLnode(T k, AVLnode *p) : key(k), balance(0), parent(p),
                       left(NULL), right(NULL) {}

   ~AVLnode() {
       delete left;
       delete right;
   }

};

/* AVL tree */ template <class T> class AVLtree { public:

   AVLtree(void);
   ~AVLtree(void);
   bool insert(T key);
   void deleteKey(const T key);
   void printBalance();

private:

   AVLnode<T> *root;

   AVLnode<T>* rotateLeft          ( AVLnode<T> *a );
   AVLnode<T>* rotateRight         ( AVLnode<T> *a );
   AVLnode<T>* rotateLeftThenRight ( AVLnode<T> *n );
   AVLnode<T>* rotateRightThenLeft ( AVLnode<T> *n );
   void rebalance                  ( AVLnode<T> *n );
   int height                      ( AVLnode<T> *n );
   void setBalance                 ( AVLnode<T> *n );
   void printBalance               ( AVLnode<T> *n );
   void clearNode                  ( AVLnode<T> *n );

};

/* AVL class definition */ template <class T> void AVLtree<T>::rebalance(AVLnode<T> *n) {

   setBalance(n);

   if (n->balance == -2) {
       if (height(n->left->left) >= height(n->left->right))
           n = rotateRight(n);
       else
           n = rotateLeftThenRight(n);
   }
   else if (n->balance == 2) {
       if (height(n->right->right) >= height(n->right->left))
           n = rotateLeft(n);
       else
           n = rotateRightThenLeft(n);
   }

   if (n->parent != NULL) {
       rebalance(n->parent);
   }
   else {
       root = n;
   }

}

template <class T> AVLnode<T>* AVLtree<T>::rotateLeft(AVLnode<T> *a) {

   AVLnode<T> *b = a->right;
   b->parent = a->parent;
   a->right = b->left;

   if (a->right != NULL)
       a->right->parent = a;

   b->left = a;
   a->parent = b;

   if (b->parent != NULL) {
       if (b->parent->right == a) {
           b->parent->right = b;
       }
       else {
           b->parent->left = b;
       }
   }

   setBalance(a);
   setBalance(b);
   return b;

}

template <class T> AVLnode<T>* AVLtree<T>::rotateRight(AVLnode<T> *a) {

   AVLnode<T> *b = a->left;
   b->parent = a->parent;
   a->left = b->right;

   if (a->left != NULL)
       a->left->parent = a;

   b->right = a;
   a->parent = b;

   if (b->parent != NULL) {
       if (b->parent->right == a) {
           b->parent->right = b;
       }
       else {
           b->parent->left = b;
       }
   }

   setBalance(a);
   setBalance(b);
   return b;

}

template <class T> AVLnode<T>* AVLtree<T>::rotateLeftThenRight(AVLnode<T> *n) {

   n->left = rotateLeft(n->left);
   return rotateRight(n);

}

template <class T> AVLnode<T>* AVLtree<T>::rotateRightThenLeft(AVLnode<T> *n) {

   n->right = rotateRight(n->right);
   return rotateLeft(n);

}

template <class T> int AVLtree<T>::height(AVLnode<T> *n) {

   if (n == NULL)
       return -1;
   return 1 + std::max(height(n->left), height(n->right));

}

template <class T> void AVLtree<T>::setBalance(AVLnode<T> *n) {

   n->balance = height(n->right) - height(n->left);

}

template <class T> void AVLtree<T>::printBalance(AVLnode<T> *n) {

   if (n != NULL) {
       printBalance(n->left);
       std::cout << n->balance << " ";
       printBalance(n->right);
   }

}

template <class T> AVLtree<T>::AVLtree(void) : root(NULL) {}

template <class T> AVLtree<T>::~AVLtree(void) {

   delete root;

}

template <class T> bool AVLtree<T>::insert(T key) {

   if (root == NULL) {
       root = new AVLnode<T>(key, NULL);
   }
   else {
       AVLnode<T>
           *n = root,
           *parent;

       while (true) {
           if (n->key == key)
               return false;

           parent = n;

           bool goLeft = n->key > key;
           n = goLeft ? n->left : n->right;

           if (n == NULL) {
               if (goLeft) {
                   parent->left = new AVLnode<T>(key, parent);
               }
               else {
                   parent->right = new AVLnode<T>(key, parent);
               }

               rebalance(parent);
               break;
           }
       }
   }

   return true;

}

template <class T> void AVLtree<T>::deleteKey(const T delKey) {

   if (root == NULL)
       return;

   AVLnode<T>
       *n       = root,
       *parent  = root,
       *delNode = NULL,
       *child   = root;

   while (child != NULL) {
       parent = n;
       n = child;
       child = delKey >= n->key ? n->right : n->left;
       if (delKey == n->key)
           delNode = n;
   }

   if (delNode != NULL) {
       delNode->key = n->key;

       child = n->left != NULL ? n->left : n->right;

       if (root->key == delKey) {
           root = child;
       }
       else {
           if (parent->left == n) {
               parent->left = child;
           }
           else {
               parent->right = child;
           }

           rebalance(parent);
       }
   }

}

template <class T> void AVLtree<T>::printBalance() {

   printBalance(root);
   std::cout << std::endl;

}

int main(void) {

   AVLtree<int> t;

   std::cout << "Inserting integer values 1 to 10" << std::endl;
   for (int i = 1; i <= 10; ++i)
       t.insert(i);

   std::cout << "Printing balance: ";
   t.printBalance();

} </lang>

Output:

Inserting integer values 1 to 10
Printing balance: 0 0 0 1 0 0 0 0 1 0 

D

Translation of: Java

<lang d>import std.stdio, std.algorithm;

class AVLtree {

   private Node* root;

   private static struct Node {
       private int key, balance;
       private Node* left, right, parent;

       this(in int k, Node* p) pure nothrow @safe @nogc {
           key = k;
           parent = p;
       }
   }

   public bool insert(in int key) pure nothrow @safe {
       if (root is null)
           root = new Node(key, null);
       else {
           Node* n = root;
           Node* parent;
           while (true) {
               if (n.key == key)
                   return false;

               parent = n;

               bool goLeft = n.key > key;
               n = goLeft ? n.left : n.right;

               if (n is null) {
                   if (goLeft) {
                       parent.left = new Node(key, parent);
                   } else {
                       parent.right = new Node(key, parent);
                   }
                   rebalance(parent);
                   break;
               }
           }
       }
       return true;
   }

   public void deleteKey(in int delKey) pure nothrow @safe @nogc {
       if (root is null)
           return;
       Node* n = root;
       Node* parent = root;
       Node* delNode = null;
       Node* child = root;

       while (child !is null) {
           parent = n;
           n = child;
           child = delKey >= n.key ? n.right : n.left;
           if (delKey == n.key)
               delNode = n;
       }

       if (delNode !is null) {
           delNode.key = n.key;

           child = n.left !is null ? n.left : n.right;

           if (root.key == delKey) {
               root = child;
           } else {
               if (parent.left is n) {
                   parent.left = child;
               } else {
                   parent.right = child;
               }
               rebalance(parent);
           }
       }
   }

   private void rebalance(Node* n) pure nothrow @safe @nogc {
       setBalance(n);

       if (n.balance == -2) {
           if (height(n.left.left) >= height(n.left.right))
               n = rotateRight(n);
           else
               n = rotateLeftThenRight(n);

       } else if (n.balance == 2) {
           if (height(n.right.right) >= height(n.right.left))
               n = rotateLeft(n);
           else
               n = rotateRightThenLeft(n);
       }

       if (n.parent !is null) {
           rebalance(n.parent);
       } else {
           root = n;
       }
   }

   private Node* rotateLeft(Node* a) pure nothrow @safe @nogc {
       Node* b = a.right;
       b.parent = a.parent;

       a.right = b.left;

       if (a.right !is null)
           a.right.parent = a;

       b.left = a;
       a.parent = b;

       if (b.parent !is null) {
           if (b.parent.right is a) {
               b.parent.right = b;
           } else {
               b.parent.left = b;
           }
       }

       setBalance(a, b);

       return b;
   }

   private Node* rotateRight(Node* a) pure nothrow @safe @nogc {
       Node* b = a.left;
       b.parent = a.parent;

       a.left = b.right;

       if (a.left !is null)
           a.left.parent = a;

       b.right = a;
       a.parent = b;

       if (b.parent !is null) {
           if (b.parent.right is a) {
               b.parent.right = b;
           } else {
               b.parent.left = b;
           }
       }

       setBalance(a, b);

       return b;
   }

   private Node* rotateLeftThenRight(Node* n) pure nothrow @safe @nogc {
       n.left = rotateLeft(n.left);
       return rotateRight(n);
   }

   private Node* rotateRightThenLeft(Node* n) pure nothrow @safe @nogc {
       n.right = rotateRight(n.right);
       return rotateLeft(n);
   }

   private int height(in Node* n) const pure nothrow @safe @nogc {
       if (n is null)
           return -1;
       return 1 + max(height(n.left), height(n.right));
   }

   private void setBalance(Node*[] nodes...) pure nothrow @safe @nogc {
       foreach (n; nodes)
           n.balance = height(n.right) - height(n.left);
   }

   public void printBalance() const @safe {
       printBalance(root);
   }

   private void printBalance(in Node* n) const @safe {
       if (n !is null) {
           printBalance(n.left);
           write(n.balance, ' ');
           printBalance(n.right);
       }
   }

}

void main() @safe {

   auto tree = new AVLtree();

   writeln("Inserting values 1 to 10");
   foreach (immutable i; 1 .. 11)
       tree.insert(i);

   write("Printing balance: ");
   tree.printBalance;

}</lang>

Output:

Inserting values 1 to 10
Printing balance: 0 0 0 1 0 0 0 0 1 0 

Go

A package: <lang go>package avl

// AVL tree adapted from Julienne Walker's presentation at // http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx. // This port uses similar indentifier names.

// The Key interface must be supported by data stored in the AVL tree. type Key interface {

   Less(Key) bool
   Eq(Key) bool

}

// Node is a node in an AVL tree. type Node struct {

   Data    Key      // anything comparable with Less and Eq.
   Balance int      // balance factor
   Link    [2]*Node // children, indexed by "direction", 0 or 1.

}

// A little readability function for returning the opposite of a direction, // where a direction is 0 or 1. Go inlines this. // Where JW writes !dir, this code has opp(dir). func opp(dir int) int {

   return 1 - dir

}

// single rotation func single(root *Node, dir int) *Node {

   save := root.Link[opp(dir)]
   root.Link[opp(dir)] = save.Link[dir]
   save.Link[dir] = root
   return save

}

// double rotation func double(root *Node, dir int) *Node {

   save := root.Link[opp(dir)].Link[dir]

   root.Link[opp(dir)].Link[dir] = save.Link[opp(dir)]
   save.Link[opp(dir)] = root.Link[opp(dir)]
   root.Link[opp(dir)] = save

   save = root.Link[opp(dir)]
   root.Link[opp(dir)] = save.Link[dir]
   save.Link[dir] = root
   return save

}

// adjust valance factors after double rotation func adjustBalance(root *Node, dir, bal int) {

   n := root.Link[dir]
   nn := n.Link[opp(dir)]
   switch nn.Balance {
   case 0:
       root.Balance = 0
       n.Balance = 0
   case bal:
       root.Balance = -bal
       n.Balance = 0
   default:
       root.Balance = 0
       n.Balance = bal
   }
   nn.Balance = 0

}

func insertBalance(root *Node, dir int) *Node {

   n := root.Link[dir]
   bal := 2*dir - 1
   if n.Balance == bal {
       root.Balance = 0
       n.Balance = 0
       return single(root, opp(dir))
   }
   adjustBalance(root, dir, bal)
   return double(root, opp(dir))

}

func insertR(root *Node, data Key) (*Node, bool) {

   if root == nil {
       return &Node{Data: data}, false
   }
   dir := 0
   if root.Data.Less(data) {
       dir = 1
   }
   var done bool
   root.Link[dir], done = insertR(root.Link[dir], data)
   if done {
       return root, true
   }
   root.Balance += 2*dir - 1
   switch root.Balance {
   case 0:
       return root, true
   case 1, -1:
       return root, false
   }
   return insertBalance(root, dir), true

}

// Insert a node into the AVL tree. // Data is inserted even if other data with the same key already exists. func Insert(tree **Node, data Key) {

   *tree, _ = insertR(*tree, data)

}

func removeBalance(root *Node, dir int) (*Node, bool) {

   n := root.Link[opp(dir)]
   bal := 2*dir - 1
   switch n.Balance {
   case -bal:
       root.Balance = 0
       n.Balance = 0
       return single(root, dir), false
   case bal:
       adjustBalance(root, opp(dir), -bal)
       return double(root, dir), false
   }
   root.Balance = -bal
   n.Balance = bal
   return single(root, dir), true

}

func removeR(root *Node, data Key) (*Node, bool) {

   if root == nil {
       return nil, false
   }
   if root.Data.Eq(data) {
       switch {
       case root.Link[0] == nil:
           return root.Link[1], false
       case root.Link[1] == nil:
           return root.Link[0], false
       }
       heir := root.Link[0]
       for heir.Link[1] != nil {
           heir = heir.Link[1]
       }
       root.Data = heir.Data
       data = heir.Data
   }
   dir := 0
   if root.Data.Less(data) {
       dir = 1
   }
   var done bool
   root.Link[dir], done = removeR(root.Link[dir], data)
   if done {
       return root, true
   }
   root.Balance += 1 - 2*dir
   switch root.Balance {
   case 1, -1:
       return root, true
   case 0:
       return root, false
   }
   return removeBalance(root, dir)

}

// Remove a single item from an AVL tree. // If key does not exist, function has no effect. func Remove(tree **Node, data Key) {

   *tree, _ = removeR(*tree, data)

}</lang> A demonstration program: <lang go>package main

import (

   "encoding/json"
   "fmt"
   "log"

   "avl"

)

type intKey int

// satisfy avl.Key func (k intKey) Less(k2 avl.Key) bool { return k < k2.(intKey) } func (k intKey) Eq(k2 avl.Key) bool { return k == k2.(intKey) }

// use json for cheap tree visualization func dump(tree *avl.Node) {

   b, err := json.MarshalIndent(tree, "", "   ")
   if err != nil {
       log.Fatal(err)
   }
   fmt.Println(string(b))

}

func main() {

   var tree *avl.Node
   fmt.Println("Empty tree:")
   dump(tree)

   fmt.Println("\nInsert test:")
   avl.Insert(&tree, intKey(3))
   avl.Insert(&tree, intKey(1))
   avl.Insert(&tree, intKey(4))
   avl.Insert(&tree, intKey(1))
   avl.Insert(&tree, intKey(5))
   dump(tree)

   fmt.Println("\nRemove test:")
   avl.Remove(&tree, intKey(3))
   avl.Remove(&tree, intKey(1))
   dump(tree)

}</lang>

Output:

Empty tree:
null

Insert test:
{
   "Data": 3,
   "Balance": 0,
   "Link": [
      {
         "Data": 1,
         "Balance": -1,
         "Link": [
            {
               "Data": 1,
               "Balance": 0,
               "Link": [
                  null,
                  null
               ]
            },
            null
         ]
      },
      {
         "Data": 4,
         "Balance": 1,
         "Link": [
            null,
            {
               "Data": 5,
               "Balance": 0,
               "Link": [
                  null,
                  null
               ]
            }
         ]
      }
   ]
}

Remove test:
{
   "Data": 4,
   "Balance": 0,
   "Link": [
      {
         "Data": 1,
         "Balance": 0,
         "Link": [
            null,
            null
         ]
      },
      {
         "Data": 5,
         "Balance": 0,
         "Link": [
            null,
            null
         ]
      }
   ]
}

Haskell

Solution of homework #4 from course http://www.seas.upenn.edu/~cis194/spring13/lectures.html. <lang haskell>data Tree a = Leaf | Node Int (Tree a) a (Tree a)

 deriving (Show, Eq)

foldTree :: Ord a => [a] -> Tree a foldTree = foldr insert Leaf

height Leaf = -1 height (Node h _ _ _) = h

depth a b = 1 + (height a `max` height b)

insert :: Ord a => a -> Tree a -> Tree a insert v Leaf = Node 1 Leaf v Leaf insert v t@(Node n left v' right)

   | v' < v = rotate $ Node n left v' (insert v right)
   | v' > v = rotate $ Node n (insert v left) v' right
   | otherwise = t

max' :: Ord a => Tree a -> Maybe a max' Leaf = Nothing max' (Node _ _ v right) = case right of

                              Leaf -> Just v
                              _    -> max' right

delete :: Ord a => a -> Tree a -> Tree a delete _ Leaf = Leaf delete x (Node h left v right)

   | x == v = maybe left (\m -> rotate $ Node h left m (delete m right)) (max' right)
   | x > v  = rotate $ Node h left v (delete x right)
   | x < v  = rotate $ Node h (delete x left) v right 

rotate :: Tree a -> Tree a rotate Leaf = Leaf -- left left case rotate (Node h (Node lh ll lv lr) v r)

   | lh - height r > 1 && height ll - height lr > 0 = 
     Node lh ll lv (Node (depth r lr) lr v r)

-- right right case rotate (Node h l v (Node rh rl rv rr))

   | rh - height l > 1 && height rr - height rl > 0 =
     Node rh (Node (depth l rl) l v rl) rv rr

-- left right case rotate (Node h (Node lh ll lv (Node rh rl rv rr)) v r)

   | lh - height r > 1 = Node h (Node (rh+1) (Node (lh-1) ll lv rl) rv rr) v r

-- right left case rotate (Node h l v (Node rh (Node lh ll lv lr) rv rr))

   | rh - height l > 1 = Node h l v (Node (lh+1) ll lv (Node (rh-1) lr rv rr))

-- re-weighting rotate (Node h l v r) = let (l', r') = (rotate l, rotate r)

                       in Node (depth l' r') l' v r'

draw :: Show a => Tree a -> String draw t = "\n" ++ draw' t 0 ++ "\n"

 where
   draw' Leaf _ = []
   draw' (Node h l v r) d = draw' r (d+1) ++ node ++ draw' l (d+1)
     where
       node = padding d ++ show (v, h) ++ "\n"
       padding n = replicate (n*4) ' '</lang>

*Main> putStr $ draw $ foldTree [1..15]

            (15,0)
        (14,1)
            (13,0)
    (12,2)
            (11,0)
        (10,1)
            (9,0)
(8,3)
            (7,0)
        (6,1)
            (5,0)
    (4,2)
            (3,0)
        (2,1)
            (1,0)

Java

This code has been cobbled together from various online examples. It's not easy to find a clear and complete explanation of AVL trees. Textbooks tend to concentrate on red-black trees because of their better efficiency. (AVL trees need to make 2 passes through the tree when inserting and deleting: one down to find the node to operate upon and one up to rebalance the tree.) <lang java>public class AVLtree {

   private Node root;

   private class Node {
       private int key;
       private int balance;
       private Node left, right, parent;

       Node(int k, Node p) {
           key = k;
           parent = p;
       }
   }

   public boolean insert(int key) {
       if (root == null)
           root = new Node(key, null);
       else {
           Node n = root;
           Node parent;
           while (true) {
               if (n.key == key)
                   return false;

               parent = n;

               boolean goLeft = n.key > key;
               n = goLeft ? n.left : n.right;

               if (n == null) {
                   if (goLeft) {
                       parent.left = new Node(key, parent);
                   } else {
                       parent.right = new Node(key, parent);
                   }
                   rebalance(parent);
                   break;
               }
           }
       }
       return true;
   }

   public void delete(int delKey) {
       if (root == null)
           return;
       Node n = root;
       Node parent = root;
       Node delNode = null;
       Node child = root;

       while (child != null) {
           parent = n;
           n = child;
           child = delKey >= n.key ? n.right : n.left;
           if (delKey == n.key)
               delNode = n;
       }

       if (delNode != null) {
           delNode.key = n.key;

           child = n.left != null ? n.left : n.right;

           if (root.key == delKey) {
               root = child;
           } else {
               if (parent.left == n) {
                   parent.left = child;
               } else {
                   parent.right = child;
               }
               rebalance(parent);
           }
       }
   }

   private void rebalance(Node n) {
       setBalance(n);

       if (n.balance == -2) {
           if (height(n.left.left) >= height(n.left.right))
               n = rotateRight(n);
           else
               n = rotateLeftThenRight(n);

       } else if (n.balance == 2) {
           if (height(n.right.right) >= height(n.right.left))
               n = rotateLeft(n);
           else
               n = rotateRightThenLeft(n);
       }

       if (n.parent != null) {
           rebalance(n.parent);
       } else {
           root = n;
       }
   }

   private Node rotateLeft(Node a) {

       Node b = a.right;
       b.parent = a.parent;

       a.right = b.left;

       if (a.right != null)
           a.right.parent = a;

       b.left = a;
       a.parent = b;

       if (b.parent != null) {
           if (b.parent.right == a) {
               b.parent.right = b;
           } else {
               b.parent.left = b;
           }
       }

       setBalance(a, b);

       return b;
   }

   private Node rotateRight(Node a) {

       Node b = a.left;
       b.parent = a.parent;

       a.left = b.right;

       if (a.left != null)
           a.left.parent = a;

       b.right = a;
       a.parent = b;

       if (b.parent != null) {
           if (b.parent.right == a) {
               b.parent.right = b;
           } else {
               b.parent.left = b;
           }
       }

       setBalance(a, b);

       return b;
   }

   private Node rotateLeftThenRight(Node n) {
       n.left = rotateLeft(n.left);
       return rotateRight(n);
   }

   private Node rotateRightThenLeft(Node n) {
       n.right = rotateRight(n.right);
       return rotateLeft(n);
   }

   private int height(Node n) {
       if (n == null)
           return -1;
       return 1 + Math.max(height(n.left), height(n.right));
   }

   private void setBalance(Node... nodes) {
       for (Node n : nodes)
           n.balance = height(n.right) - height(n.left);
   }

   public void printBalance() {
       printBalance(root);
   }

   private void printBalance(Node n) {
       if (n != null) {
           printBalance(n.left);
           System.out.printf("%s ", n.balance);
           printBalance(n.right);
       }
   }

   public static void main(String[] args) {
       AVLtree tree = new AVLtree();

       System.out.println("Inserting values 1 to 10");
       for (int i = 1; i < 10; i++)
           tree.insert(i);

       System.out.print("Printing balance: ");
       tree.printBalance();
   }

}</lang>

Inserting values 1 to 10
Printing balance: 0 0 0 1 0 1 0 0 0

More elaborate version

See AVL_tree/Java

Objective-C

Translation of: Java

<lang Objective-C> @implementation AVLTree

-(BOOL)insertWithKey:(NSInteger)key {

   if (self.root == nil) {
       self.root = [[AVLTreeNode alloc]initWithKey:key andParent:nil];
   } else {
       
       AVLTreeNode *n = self.root;
       AVLTreeNode *parent;
       
       while (true) {
           
           if (n.key == key) {
               return false;
           }
           
           parent = n;
           
           BOOL goLeft = n.key > key;
           n = goLeft ? n.left : n.right;
           
           if (n == nil) {
               
               if (goLeft) {
                   parent.left = [[AVLTreeNode alloc]initWithKey:key andParent:parent];
               } else {
                   parent.right = [[AVLTreeNode alloc]initWithKey:key andParent:parent];
               }
               [self rebalanceStartingAtNode:parent];
               break;
           }
       }
   }
   
   return true;

}

-(void)rebalanceStartingAtNode:(AVLTreeNode*)n {

   [self setBalance:@[n]];
   
   if (n.balance == -2) {
       if ([self height:(n.left.left)] >= [self height:n.left.right]) {
           n = [self rotateRight:n];
       } else {
           n = [self rotateLeftThenRight:n];
       }
   } else if (n.balance == 2) {
       if ([self height:n.right.right] >= [self height:n.right.left]) {
           n = [self rotateLeft:n];
       } else {
           n = [self rotateRightThenLeft:n];
       }
   }
   
   if (n.parent != nil) {
       [self rebalanceStartingAtNode:n.parent];
   } else {
       self.root = n;
   }

}

-(AVLTreeNode*)rotateRight:(AVLTreeNode*)a {

   AVLTreeNode *b = a.left;
   b.parent = a.parent;
   
   a.left = b.right;
   
   if (a.left != nil) {
       a.left.parent = a;
   }
   
   b.right = a;
   a.parent = b;
   
   if (b.parent != nil) {
       if (b.parent.right == a) {
           b.parent.right = b;
       } else {
           b.parent.left = b;
       }
   }
   
   [self setBalance:@[a,b]];
   return b;
   

}

-(AVLTreeNode*)rotateLeftThenRight:(AVLTreeNode*)n {

   n.left = [self rotateLeft:n.left];
   return [self rotateRight:n];
   

}

-(AVLTreeNode*)rotateRightThenLeft:(AVLTreeNode*)n {

   n.right = [self rotateRight:n.right];
   return [self rotateLeft:n];

}

-(AVLTreeNode*)rotateLeft:(AVLTreeNode*)a {

   //set a's right node as b
   AVLTreeNode* b = a.right;
   //set b's parent as a's parent (which could be nil)
   b.parent = a.parent;
   //in case b had a left child transfer it to a
   a.right = b.left;
   
   // after changing a's reference to the right child, make sure the parent is set too
   if (a.right != nil) {
       a.right.parent = a;
   }
   
   // switch a over to the left to be b's left child
   b.left = a;
   a.parent = b;
   
   if (b.parent != nil) {
       if (b.parent.right == a) {
           b.parent.right = b;
       } else {
           b.parent.right = b;
       }
   }
   
   [self setBalance:@[a,b]];
   
   return b;
   

}

-(void) setBalance:(NSArray*)nodesArray {

   for (AVLTreeNode* n in nodesArray) {
       
       n.balance = [self height:n.right] - [self height:n.left];
   }
   

}

-(int)height:(AVLTreeNode*)n {

   if (n == nil) {
       return -1;
   }
   
   return 1 + MAX([self height:n.left], [self height:n.right]);

}

-(void)printKey:(AVLTreeNode*)n {

   if (n != nil) {
       [self printKey:n.left];
       NSLog(@"%ld", n.key);
       [self printKey:n.right];
   }

}

-(void)printBalance:(AVLTreeNode*)n {

   if (n != nil) {
       [self printBalance:n.left];
       NSLog(@"%ld", n.balance);
       [self printBalance:n.right];
   }

} @end -- test

int main(int argc, const char * argv[]) {

   @autoreleasepool {

       AVLTree *tree = [AVLTree new];
       NSLog(@"inserting values 1 to 6");
       [tree insertWithKey:1];
       [tree insertWithKey:2];
       [tree insertWithKey:3];
       [tree insertWithKey:4];
       [tree insertWithKey:5];
       [tree insertWithKey:6];
       
       NSLog(@"printing balance: ");
       [tree printBalance:tree.root];
       
       NSLog(@"printing key: ");
       [tree printKey:tree.root];
   }
   return 0;

}

</lang>

Output:

inserting values 1 to 6
printing balance:
0
0
0
0
1
0

printing key:
1
2
3
4
5
6

Phix

Translated from the C version at http://www.geeksforgeeks.org/avl-tree-set-2-deletion
The standard distribution includes demo\rosetta\AVL_tree.exw, which contains a slightly longer but perhaps more readable version, with a command line equivalent of https://www.cs.usfca.edu/~galles/visualization/AVLtree.html as well as a simple tree structure display routine and additional verification code (both modelled on the C version found on this page) <lang Phix>enum KEY = 0,

    LEFT,
    HEIGHT,    -- (NB +/-1 gives LEFT or RIGHT)
    RIGHT

sequence tree = {} integer freelist = 0

function newNode(object key) integer node

   if freelist=0 then
       node = length(tree)+1
       tree &= {key,NULL,1,NULL}
   else
       node = freelist
       freelist = tree[freelist]
       tree[node+KEY..node+RIGHT] = {key,NULL,1,NULL}
   end if
   return node

end function

function height(integer node)

   return iff(node=NULL?0:tree[node+HEIGHT])

end function

procedure setHeight(integer node)

   tree[node+HEIGHT] = max(height(tree[node+LEFT]), height(tree[node+RIGHT]))+1

end procedure

function rotate(integer node, integer direction) integer idirection = LEFT+RIGHT-direction integer pivot = tree[node+idirection]

   {tree[pivot+direction],tree[node+idirection]} = {node,tree[pivot+direction]}
   setHeight(node)
   setHeight(pivot)
   return pivot

end function

function getBalance(integer N)

   return iff(N==NULL ? 0 : height(tree[N+LEFT])-height(tree[N+RIGHT]))

end function

function insertNode(integer node, object key)

   if node==NULL then
       return newNode(key)
   end if
   integer c = compare(key,tree[node+KEY])
   if c!=0 then
       integer direction = HEIGHT+c    -- LEFT or RIGHT
       tree[node+direction] = insertNode(tree[node+direction], key)
       setHeight(node)
       integer balance = trunc(getBalance(node)/2) -- +/-1 (or 0)
       if balance then
           direction = HEIGHT-balance  -- LEFT or RIGHT
           c = compare(key,tree[tree[node+direction]+KEY])
           if c=balance then
               tree[node+direction] = rotate(tree[node+direction],direction)
           end if
           if c!=0 then
               node = rotate(node,LEFT+RIGHT-direction)
           end if
       end if
   end if
   return node

end function

function minValueNode(integer node)

   while 1 do
       integer next = tree[node+LEFT]
       if next=NULL then exit end if
       node = next
   end while
   return node

end function

function deleteNode(integer root, object key) integer c

   if root=NULL then return root end if
   c = compare(key,tree[root+KEY])
   if c=-1 then
       tree[root+LEFT] = deleteNode(tree[root+LEFT], key)
   elsif c=+1 then
       tree[root+RIGHT] = deleteNode(tree[root+RIGHT], key)
   elsif tree[root+LEFT]==NULL
      or tree[root+RIGHT]==NULL then
       integer temp = iff(tree[root+LEFT] ? tree[root+LEFT] : tree[root+RIGHT])
       if temp==NULL then  -- No child case
           {temp,root} = {root,NULL}
       else                -- One child case
           tree[root+KEY..root+RIGHT] = tree[temp+KEY..temp+RIGHT]
       end if
       tree[temp+KEY] = freelist
       freelist = temp
   else                    -- Two child case
       integer temp = minValueNode(tree[root+RIGHT])
       tree[root+KEY] = tree[temp+KEY]
       tree[root+RIGHT] = deleteNode(tree[root+RIGHT], tree[temp+KEY])
   end if
   if root=NULL then return root end if
   setHeight(root)
   integer balance = trunc(getBalance(root)/2)
   if balance then
       integer direction = HEIGHT-balance
       c = compare(getBalance(tree[root+direction]),0)
       if c=-balance then
           tree[root+direction] = rotate(tree[root+direction],direction)
       end if
       root = rotate(root,LEFT+RIGHT-direction)
   end if
   return root

end function

procedure inOrder(integer node)

   if node!=NULL then
       inOrder(tree[node+LEFT])
       printf(1, "%d ", tree[node+KEY])
       inOrder(tree[node+RIGHT])
   end if

end procedure

integer root = NULL sequence test = shuffle(tagset(50003))

   for i=1 to length(test) do
       root = insertNode(root,test[i])
   end for
   test = shuffle(tagset(50000))
   for i=1 to length(test) do
       root = deleteNode(root,test[i])
   end for
   inOrder(root)</lang>

Output:

50001 50002 50003

Lua

<lang Lua>AVL={balance=0} AVL.__mt={__index = AVL}

function AVL:new(list)

 local o={}  
 setmetatable(o, AVL.__mt)
 for _,v in ipairs(list or {}) do
   o=o:insert(v)
 end
 return o

end

function AVL:rebalance()

 local rotated=false
 if self.balance>1 then
   if self.right.balance<0 then
     self.right, self.right.left.right, self.right.left = self.right.left, self.right, self.right.left.right
     self.right.right.balance=self.right.balance>-1 and 0 or 1
     self.right.balance=self.right.balance>0 and 2 or 1
   end
   self, self.right.left, self.right = self.right, self, self.right.left
   self.left.balance=1-self.balance
   self.balance=self.balance==0 and -1 or 0
   rotated=true
 elseif self.balance<-1 then
   if self.left.balance>0 then
     self.left, self.left.right.left, self.left.right = self.left.right, self.left, self.left.right.left
     self.left.left.balance=self.left.balance<1 and 0 or -1
     self.left.balance=self.left.balance<0 and -2 or -1
   end
   self, self.left.right, self.left = self.left, self, self.left.right
   self.right.balance=-1-self.balance
   self.balance=self.balance==0 and 1 or 0
   rotated=true
 end
 return self,rotated

end

function AVL:insert(v)

 if not self.value then 
   self.value=v
   self.balance=0
   return self,1
 end
 local grow
 if v==self.value then
   return self,0
 elseif v<self.value then
   if not self.left then self.left=self:new() end
   self.left,grow=self.left:insert(v)
   self.balance=self.balance-grow
 else
   if not self.right then self.right=self:new() end
   self.right,grow=self.right:insert(v)
   self.balance=self.balance+grow
 end
 self,rotated=self:rebalance()
 return self, (rotated or self.balance==0) and 0 or grow 

end

function AVL:delete_move(dir,other,mul)

 if self[dir] then
   local sb2,v
   self[dir], sb2, v=self[dir]:delete_move(dir,other,mul)
   self.balance=self.balance+sb2*mul
   self,sb2=self:rebalance()
   return self,(sb2 or self.balance==0) and -1 or 0,v
 else
   return self[other],-1,self.value
 end

end

function AVL:delete(v,isSubtree)

 local grow=0
 if v==self.value then
   local v
   if self.balance>0 then
     self.right,grow,v=self.right:delete_move("left","right",-1)
   elseif self.left then
     self.left,grow,v=self.left:delete_move("right","left",1)
     grow=-grow
   else
     return not isSubtree and AVL:new(),-1
   end
   self.value=v
   self.balance=self.balance+grow
 elseif v<self.value and self.left then
   self.left,grow=self.left:delete(v,true)
   self.balance=self.balance-grow
 elseif v>self.value and self.right then
   self.right,grow=self.right:delete(v,true)
   self.balance=self.balance+grow
 else
   return self,0
 end
 self,rotated=self:rebalance()
 return self, grow~=0 and (rotated or self.balance==0) and -1 or 0

end

-- output functions

function AVL:toList(list)

 if not self.value then return {} end
 list=list or {}
 if self.left then self.left:toList(list) end
 list[#list+1]=self.value
 if self.right then self.right:toList(list) end
 return list

end

function AVL:dump(depth)

 if not self.value then return end
 depth=depth or 0
 if self.right then self.right:dump(depth+1) end
 print(string.rep("    ",depth)..self.value.." ("..self.balance..")")
 if self.left then self.left:dump(depth+1) end

end

-- test

local test=AVL:new{1,10,5,15,20,3,5,14,7,13,2,8,3,4,5,10,9,8,7}

test:dump() print("\ninsert 17:") test=test:insert(17) test:dump() print("\ndelete 10:") test=test:delete(10) test:dump() print("\nlist:") print(unpack(test:toList())) </lang>

Output:

            20 (0)
        15 (1)
    14 (1)
        13 (0)
10 (-1)
            9 (0)
        8 (0)
            7 (0)
    5 (-1)
                4 (0)
            3 (1)
        2 (1)
            1 (0)

insert 17:
            20 (0)
        17 (0)
            15 (0)
    14 (1)
        13 (0)
10 (-1)
            9 (0)
        8 (0)
            7 (0)
    5 (-1)
                4 (0)
            3 (1)
        2 (1)
            1 (0)

delete 10:
            20 (0)
        17 (0)
            15 (0)
    14 (1)
        13 (0)
9 (-1)
        8 (-1)
            7 (0)
    5 (-1)
                4 (0)
            3 (1)
        2 (1)
            1 (0)

list:
1       2       3       4       5       7       8       9       13      14      15      17      20

Sidef

Translation of: D

<lang ruby>class AVLtree {

   has root = nil

   struct Node {
       Number key,
       Number balance = 0,
       Node left = nil,
       Node right = nil,
       Node parent = nil,
   }

   method insert(key) {
       if (root == nil) {
           root = Node(key)
           return true
       }

       var n = root
       var parent = nil

       loop {
           if (n.key == key) {
               return false
           }
           parent = n
           var goLeft = (n.key > key)
           n = (goLeft ? n.left : n.right)

           if (n == nil) {
               var tn = Node(key, parent: parent)
               if (goLeft) {
                   parent.left = tn
               }
               else {
                   parent.right = tn
               }
               self.rebalance(parent)
               break
           }
       }

       return true
   }

   method delete_key(delKey) {
       if (root == nil) { return }

       var n = root
       var parent = root
       var delNode = nil
       var child = root

       while (child != nil) {
           parent = n
           n = child
           child = (delKey >= n.key ? n.right : n.left)
           if (delKey == n.key) {
               delNode = n
           }
       }

       if (delNode != nil) {
           delNode.key = n.key
           child = (n.left != nil ? n.left : n.right)

           if (root.key == delKey) {
               root = child
           }
           else {
               if (parent.left == n) {
                   parent.left = child
               }
               else {
                   parent.right = child
               }
               self.rebalance(parent)
           }
       }
   }

   method rebalance(n) {
       if (n == nil) { return }
       self.setBalance(n)

       given (n.balance) {
           when (-2) {
               if (self.height(n.left.left) >= self.height(n.left.right)) {
                   n = self.rotate(n, :right)
               }
               else {
                   n = self.rotate_twice(n, :left, :right)
               }
           }
           when (2) {
               if (self.height(n.right.right) >= self.height(n.right.left)) {
                   n = self.rotate(n, :left)
               }
               else {
                   n = self.rotate_twice(n, :right, :left)
               }
           }
       }

       if (n.parent != nil) {
           self.rebalance(n.parent)
       }
       else {
           root = n
       }
   }

   method rotate(a, dir) {
       var b = (dir == :left ? a.right : a.left)
       b.parent = a.parent

       (dir == :left) ? (a.right = b.left)
                      : (a.left  = b.right)

       if (a.right != nil) {
           a.right.parent = a
       }

       b.$dir = a
       a.parent = b

       if (b.parent != nil) {
           if (b.parent.right == a) {
               b.parent.right = b
           }
           else {
               b.parent.left = b
           }
       }

       self.setBalance(a, b)
       return b
   }

   method rotate_twice(n, dir1, dir2) {
       n.left = self.rotate(n.left, dir1)
       self.rotate(n, dir2)
   }

   method height(n) {
       if (n == nil) { return -1 }
       1 + Math.max(self.height(n.left), self.height(n.right))
   }

   method setBalance(*nodes) {
       nodes.each { |n|
           n.balance = (self.height(n.right) - self.height(n.left))
       }
   }

   method printBalance {
       self.printBalance(root)
   }

   method printBalance(n) {
       if (n != nil) {
           self.printBalance(n.left)
           print(n.balance, ' ')
           self.printBalance(n.right)
       }
   }

}

var tree = AVLtree()

say "Inserting values 1 to 10" 10.times { |i| tree.insert(i) } print "Printing balance: " tree.printBalance</lang>

Output:

Inserting values 1 to 10
Printing balance: 0 0 0 1 0 0 0 0 1 0

Tcl

Note that in general, you would not normally write a tree directly in Tcl when writing code that required an $\alpha$⁼$\rightarrow \beta$ map, but would rather use either an array variable or a dictionary value (which are internally implemented using a high-performance hash table engine).

Works with: Tcl version 8.6

<lang tcl>package require TclOO

namespace eval AVL {

   # Class for the overall tree; manages real public API
   oo::class create Tree {

variable root nil class constructor Template:NodeClass AVL::Node { set class [oo::class create Node [list superclass $nodeClass]]

# Create a nil instance to act as a leaf sentinel set nil [my NewNode ""] set root [$nil ref]

# Make nil be special oo::objdefine $nil { method height {} {return 0} method key {} {error "no key possible"} method value {} {error "no value possible"} method destroy {} { # Do nothing (doesn't prohibit destruction entirely) } method print {indent increment} { # Do nothing } } }

# How to actually manufacture a new node method NewNode {key} { if {![info exists nil]} {set nil ""} $class new $key $nil [list [namespace current]::my NewNode] }

# Create a new node in the tree and return it method insert {key} { set node [my NewNode $key] if {$root eq $nil} { set root $node } else { $root insert $node } return $node }

# Find the node for a particular key method lookup {key} { for {set node $root} {$node ne $nil} {} { if {[$node key] == $key} { return $node } elseif {[$node key] > $key} { set node [$node left] } else { set node [$node right] } } error "no such node" }

# Print a tree out, one node per line method print {{indent 0} {increment 1}} { $root print $indent $increment return }

   }

   # Class of an individual node; may be subclassed
   oo::class create Node {

variable key value left right 0 refcount newNode constructor {n nil instanceFactory} { set newNode $instanceFactory set 0 [expr {$nil eq "" ? [self] : $nil}] set key $n set value {} set left [set right $0] set refcount 0 } method ref {} { incr refcount return [self] } method destroy {} { if {[incr refcount -1] < 1} next } method New {key value} { set n [{*}$newNode $key] $n setValue $value return $n }

# Getters method key {} {return $key} method value {} {return $value} method left {} {return $left} method right {args} {return $right}

# Setters method setValue {newValue} { set value $newValue } method setLeft {node} { # Non-trivial because of reference management $node ref $left destroy set left $node return } method setRight {node} { # Non-trivial because of reference management $node ref $right destroy set right $node return }

# Print a node and its descendents method print {indent increment} { puts [format "%s%s => %s" [string repeat " " $indent] $key $value] incr indent $increment $left print $indent $increment $right print $indent $increment }

method height {} { return [expr {max([$left height], [$right height]) + 1}] } method balanceFactor {} { expr {[$left height] - [$right height]} }

method insert {node} { # Simple insertion if {$key > [$node key]} { if {$left eq $0} { my setLeft $node } else { $left insert $node } } else { if {$right eq $0} { my setRight $node } else { $right insert $node } }

# Rebalance this node if {[my balanceFactor] > 1} { if {[$left balanceFactor] < 0} { $left rotateLeft } my rotateRight } elseif {[my balanceFactor] < -1} { if {[$right balanceFactor] > 0} { $right rotateRight } my rotateLeft } }

# AVL Rotations method rotateLeft {} { set new [my New $key $value] set key [$right key] set value [$right value] $new setLeft $left $new setRight [$right left] my setLeft $new my setRight [$right right] }

method rotateRight {} { set new [my New $key $value] set key [$left key] set value [$left value] $new setLeft [$left right] $new setRight $right my setLeft [$left left] my setRight $new }

   }

}</lang> Demonstrating: <lang tcl># Create an AVL tree AVL::Tree create tree

1. Populate it with some semi-random data

for {set i 33} {$i < 127} {incr i} {

   [tree insert $i] setValue \

[string repeat [format %c $i] [expr {1+int(rand()*5)}]] }

1. Print it out

tree print

1. Look up a few values in the tree

for {set i 0} {$i < 10} {incr i} {

   set k [expr {33+int((127-33)*rand())}]
   puts $k=>[[tree lookup $k] value]

}

1. Destroy the tree and all its nodes

tree destroy</lang>

Output:

64 => @@@
 48 => 000
  40 => (((((
   36 => $
    34 => """
     33 => !!
     35 => #####
    38 => &&&
     37 => %
     39 => ''''
   44 => ,
    42 => **
     41 => )))
     43 => +++++
    46 => .
     45 => --
     47 => ////
  56 => 888
   52 => 444
    50 => 22222
     49 => 1111
     51 => 333
    54 => 6
     53 => 555
     55 => 77
   60 => <<<<
    58 => ::::
     57 => 99999
     59 => ;
    62 => >>>
     61 => ===
     63 => ??
 96 => ``
  80 => PPPPP
   72 => HHHH
    68 => DDD
     66 => BBBB
      65 => A
      67 => CCC
     70 => FFF
      69 => EEEE
      71 => GGG
    76 => LL
     74 => JJ
      73 => III
      75 => KKKK
     78 => N
      77 => MMMMM
      79 => OOOOO
   88 => XXX
    84 => TTTT
     82 => R
      81 => QQQQ
      83 => SSSS
     86 => V
      85 => UUU
      87 => WWW
    92 => \\\
     90 => Z
      89 => YYYYY
      91 => [
     94 => ^^^^^
      93 => ]]]]
      95 => _____
  112 => pppp
   104 => hh
    100 => d
     98 => bb
      97 => aaa
      99 => cccc
     102 => ff
      101 => eeee
      103 => gggg
    108 => lll
     106 => j
      105 => iii
      107 => kkkkk
     110 => nn
      109 => m
      111 => o
   120 => x
    116 => ttt
     114 => rrrrr
      113 => qqqqq
      115 => s
     118 => vvv
      117 => uuuu
      119 => wwww
    124 => ||||
     122 => zzzz
      121 => y
      123 => {{{
     125 => }}}}
      126 => ~~~~
53=>555
55=>77
60=><<<<
100=>d
99=>cccc
93=>]]]]
57=>99999
56=>888
47=>////
39=>''''