AVL tree
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.
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) |
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#
See AVL_tree/C_sharp.
C
See AVL tree/C
C++
<lang cpp> // AVL in Managed C++
using namespace System; using namespace System; using namespace System::Collections; using namespace System::Collections::Generic; using namespace System::Threading; using namespace System::Runtime::Serialization;
namespace ISharp {
public enum class State {
Header, LeftHigh, Balanced, RightHigh
};
public enum class Direction { FromLeft, FromRight };
public ref struct Node {
Node^ Left; Node^ Right; Node^ Parent; State Balance;
Node() { Left = this; Right = this; Parent = nullptr; Balance = State::Header; }
Node(Node^ p) { Left = nullptr; Right = nullptr; Parent = p; Balance = State::Balanced; }
property Boolean IsHeader { Boolean get() { return Balance == State::Header; } }
};
generic <typename T> public delegate void TypeFound(Object^ O, T type);
generic <typename T> public delegate void TypeAdded(Object^ O, T type);
generic <typename T> public delegate void TypeRemoved(Object^ O, T type);
generic <typename T> public delegate void TypeUpdated(Object^ O, T before, T after);
generic<typename T> public interface struct IHasher {
int GetHashCode(T t);
};
generic<typename T> [Serializable] public ref class Hasher abstract : IHasher<T> {
public:
static property Hasher<T>^ Default { Hasher<T>^ get(); }
virtual int GetHashCode(T t) = 0;
};
generic<typename T> [Serializable] public ref class DefaultHasher : Hasher<T> {
public:
virtual int GetHashCode(T t) override { return t->GetHashCode(); }
};
generic<typename T> Hasher<T>^ Hasher<T>::Default::get() { return gcnew DefaultHasher<T>(); }
generic<typename T>
public interface struct ICloneable { T Clone(); };
generic<typename T> public interface class ICloner { T Clone(T t); };
generic<typename T> [Serializable]
public ref struct Cloner abstract : ICloner<T>
{
static property Cloner<T>^ Default { Cloner<T>^ get(); }
static property Cloner<T>^ Invisible { Cloner<T>^ get(); }
virtual T Clone(T t) = 0;
};
generic<typename T> [Serializable] public ref struct DefaultCloner1 : Cloner<T> {
virtual T Clone(T t) override { ICloneable<T>^ copier = (ICloneable<T>^)t; return copier->Clone(); }
};
generic<typename T> [Serializable] public ref struct DefaultCloner2 : Cloner<T> {
virtual T Clone(T t) override { ICloneable<T>^ copier = (ICloneable<T>^)t; return (T)copier->Clone(); }
};
generic<typename T> [Serializable] public ref struct DefaultNoCloner : Cloner<T> {
virtual T Clone(T t) override { return t; }
};
generic<typename T> Cloner<T>^ Cloner<T>::Default::get() {
Type^ TypeT = T::typeid; Type^ TypeIC1 = ICloneable<T>::typeid; Type^ TypeIC2 = ICloneable::typeid; if (TypeIC1->IsAssignableFrom(TypeT)) return gcnew DefaultCloner1<T>(); else if (TypeIC2->IsAssignableFrom(TypeT)) return gcnew DefaultCloner2<T>(); else return gcnew DefaultNoCloner<T>();
}
generic<typename T> Cloner<T>^ Cloner<T>::Invisible::get() { return gcnew DefaultNoCloner<T>(); } public ref struct OutOfKeyOrderException : public Exception { static String^ message = gcnew String("A tree was found to be out of key order.");
OutOfKeyOrderException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("StandardGenericLibrary Collections Subsystem"); } };
public ref struct TreeInvalidParentException : public Exception { static String^ message = gcnew String("The validation routines detected that the parent structure of a tree is invalid.");
TreeInvalidParentException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("StandardGenericLibrary Collections Subsystem"); } };
public ref struct TreeOutOfBalanceException : public Exception { static String^ message = gcnew String("The validation routines detected that the tree is out of balance.");
TreeOutOfBalanceException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("StandardGenericLibrary Collections Subsystem"); } };
public ref struct InvalidEmptyTreeException : public Exception { static String^ message = gcnew String("The validation routines detected that an empty tree is invalid.");
InvalidEmptyTreeException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("StandardGenericLibrary Collections Subsystem"); } };
public ref struct InvalidEndItemException : public Exception { static String^ message = gcnew String("The validation routines detected that the end item of a tree is invalid.");
InvalidEndItemException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("StandardGenericLibrary Collections Subsystem"); } };
public ref struct EntryAlreadyExistsException : public Exception { static String^ message = gcnew String("An entry already exists in the collection.");
EntryAlreadyExistsException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("StandardGenericLibrary Collections Subsystem"); } };
public ref struct DifferentKeysException : public Exception { static String^ message = gcnew String("The specified items have different keys.");
DifferentKeysException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("StandardGenericLibrary Collections Subsystem"); } };
public ref struct AddSubTreeFailedException : public Exception { static String^ message = gcnew String("Subtree creation failed.");
AddSubTreeFailedException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("StandardGenericLibrary Collections Subsystem"); } };
public ref struct IsEndItemException : public Exception { static String^ message = gcnew String("The requested action cannot be performed on an end item.");
IsEndItemException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("ISharp Collections Subsystem"); } };
public ref struct EntryNotFoundException : public Exception { static String^ message = gcnew String("The requested entry could not be located in the specified collection.");
EntryNotFoundException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("StandardGenericLibrary Collections Subsystem"); } };
public ref struct InvalidSetOperationException : public Exception { static String^ message = gcnew String("An invalid set operation was specified.");
InvalidSetOperationException() : Exception(message) { HelpLink = gcnew String("mail@BenedictBede.com"); Source = gcnew String("StandardGenericLibrary Collections Subsystem"); } };
Node^ PreviousItem(Node^ node) {
if (node->IsHeader) {return node->Right;}
else if (node->Left != nullptr) { Node^ y = node->Left; while (y->Right != nullptr) y = y->Right; node = y; } else { Node^ y = node->Parent; if (y->IsHeader) return y; while (node == y->Left) {node = y; y = y->Parent;} node = y; } return node;
}
Node^ NextItem(Node^ node) {
if (node->IsHeader) return node->Left;
if (node->Right != nullptr) { node = node->Right; while (node->Left != nullptr) 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;
}
void SwapNodeReference(Node^% first, Node^% second) {Node^ temporary = first; first = second; second = temporary;}
void LeftNodeSwap(Node^ Root, Node^ Replace) {
if (Replace->Left) Replace->Left->Parent = Root; if (Replace->Right) Replace->Right->Parent = Root;
if (Root->Right) Root->Right->Parent = Replace;
if (Replace == Root->Left) { Replace->Parent = Root->Parent; Root->Parent = Replace;
Root->Left = Replace->Left; Replace->Left = Root; } else { Root->Left->Parent = Replace;
if (Replace->Parent->Left == Replace) Replace->Parent->Left = Root; else Replace->Parent->Right = Root;
SwapNodeReference(Root->Left,Replace->Left); SwapNodeReference(Root->Parent,Replace->Parent); }
SwapNodeReference(Root->Right,Replace->Right);
State Balance = Root->Balance; Root->Balance = Replace->Balance; Replace->Balance=Balance;
}
void SwapNodes(Node^ A, Node^ B) {
if (B == A->Left) { if (B->Left) B->Left->Parent = A; if (B->Right) B->Right->Parent = A;
if (A->Right) 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(A->Right,B->Right); } else if (B == A->Right) { if (B->Right) B->Right->Parent = A; if (B->Left) B->Left->Parent = A;
if (A->Left) 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(A->Left,B->Left); } else if (A == B->Left) { if (A->Left) A->Left->Parent = B; if (A->Right) A->Right->Parent = B;
if (B->Right) 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(A->Right,B->Right); } else if (A == B->Right) { if (A->Right) A->Right->Parent = B; if (A->Left) A->Left->Parent = B;
if (B->Left) 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(A->Left,B->Left); } else { if (A->Parent == B->Parent) SwapNodeReference(A->Parent->Left,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) B->Left->Parent = A; if (B->Right) B->Right->Parent = A;
if (A->Left) A->Left->Parent = B; if (A->Right) A->Right->Parent = B;
SwapNodeReference(A->Left,B->Left); SwapNodeReference(A->Right,B->Right); SwapNodeReference(A->Parent,B->Parent); }
State Balance = A->Balance; A->Balance = B->Balance; B->Balance=Balance;
}
void RotateLeft(Node^% Root) {
Node^ Parent = Root->Parent; Node^ x = Root->Right;
Root->Parent = x; x->Parent = Parent; if (x->Left) x->Left->Parent = Root;
Root->Right = x->Left; x->Left = Root; Root = x;
}
void RotateRight(Node^% Root) {
Node^ Parent = Root->Parent; Node^ x = Root->Left;
Root->Parent = x; x->Parent = Parent; if (x->Right) x->Right->Parent = Root;
Root->Left = x->Right; x->Right = Root; Root = x;
}
void BalanceLeft(Node^% Root) {
Node^ Left = Root->Left; // Left Subtree of Root Node
switch (Left->Balance) { case State::LeftHigh: Root->Balance = State::Balanced;
Left->Balance = State::Balanced;
RotateRight(Root); break; case State::RightHigh: { Node^ subRight = Left->Right; // Right subtree of Left 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(Left); Root->Left = Left; RotateRight(Root); } break;
case State::Balanced: Root->Balance = State::LeftHigh;
Left->Balance = State::RightHigh;
RotateRight(Root); break; }
}
void BalanceRight(Node^% Root) {
Node^ Right = Root->Right; // Right Subtree of Root Node
switch (Right->Balance) { case State::RightHigh: Root ->Balance = State::Balanced;
Right->Balance = State::Balanced;
RotateLeft(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(Right); Root->Right = Right; RotateLeft(Root); } break;
case State::Balanced: Root ->Balance = State::RightHigh;
Right->Balance = State::LeftHigh;
RotateLeft(Root); break; }
}
void BalanceTree(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(Parent->Parent); else if (Parent->Left == Root) BalanceLeft(Parent->Left); else BalanceLeft(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(Parent->Parent); else if (Parent->Left == Root) BalanceRight(Parent->Left); else BalanceRight(Parent->Right); Taller = false; break; } }
if (Taller) // skip up a level { if (Parent->IsHeader) Taller = false; else { Root = Parent; From = NextFrom; } } } }
void BalanceTreeRemove(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(Parent->Parent); else if (Parent->Left == Root) BalanceRight(Parent->Left); else BalanceRight(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(Parent->Parent); else if (Parent->Left == Root) BalanceLeft(Parent->Left); else BalanceLeft(Parent->Right); break; } }
if (Shorter) { if (Parent->IsHeader) Shorter = false; else { From = NextFrom; Root = Parent; } } }
}
Node^ Minimum(Node^ node) {
while (node->Left) node=node->Left; return node;
}
Node^ Maximum(Node^ node) {
while (node->Right) node=node->Right; return node;
}
void AdjustAdd(Node^ Root) {
Node^ Header = Root->Parent; while (!Header->IsHeader) Header=Header->Parent;
if (Root->Parent->Left == Root) { BalanceTree(Root->Parent,Direction::FromLeft); if (Header->Left == Root->Parent) Header->Left = Root; } else { BalanceTree(Root->Parent,Direction::FromRight); if (Header->Right == Root->Parent) Header->Right = Root; }
}
void AdjustRemove(Node^ Parent, Direction Direction) {
BalanceTreeRemove(Parent,Direction); Node^ Header = Parent; while (!Header->IsHeader) Header=Header->Parent;
if (Header->Parent == nullptr) { Header->Left = Header; Header->Right = Header; } else { Header->Left = Minimum(Header->Parent); Header->Right = Maximum(Header->Parent); }
}
unsigned long long Depth(Node^ Root) {
if (Root) { unsigned long long Left = Root->Left ? Depth(Root->Left) : 0; unsigned long long Right = Root->Right ? Depth(Root->Right) : 0; return Left < Right ? Right+1 : Left+1; } else return 0;
}
unsigned long long Count(Node^ Root) {
if (Root) { unsigned long long left = Root->Left ? Count(Root->Left) : 0; unsigned long long right = Root->Right ? Count(Root->Right) : 0; return left + right + 1; } else return 0;
}
public enum class SetOperation { Union, Intersection, SymmetricDifference, Difference, Equality, Inequality, Subset, Superset };
generic<typename T> public ref class SetNode : Node {
public:
T Data;
SetNode(T dataType, Node^ Parent) : Node(Parent) {Data = dataType; }
};
generic<typename T> public value struct SetEntry : System::Collections::Generic::IEnumerator<T> {
public:
SetEntry(Node^ n) { _Node = n; }
property T Value { T get() { if (_Node->Balance == State::Header) throw gcnew IsEndItemException(); return ((SetNode<T>^)_Node)->Data; } void set(T Value) { if (_Node->Balance == State::Header) throw gcnew IsEndItemException(); ((SetNode<T>^)_Node)->Data = Value; } }
property Boolean IsHeader { Boolean get() { return _Node->IsHeader; } }
virtual Boolean MoveNext() { _Node = NextItem(_Node); return _Node->IsHeader ? false : true; }
Boolean MovePrevious() { _Node = PreviousItem(_Node); return _Node->IsHeader ? false : true; }
static SetEntry<T> operator ++(SetEntry<T> entry) { entry._Node = NextItem(entry._Node); return entry; }
static SetEntry<T> operator --(SetEntry<T> entry) { entry._Node = PreviousItem(entry._Node); return entry; }
static SetEntry<T> operator +(SetEntry<T> C, unsigned long long Increment) { SetEntry<T> Result = SetEntry<T>(C._Node); for (unsigned long long i = 0; i < Increment; i++) ++Result; return Result; }
static SetEntry<T> operator +(unsigned long long Increment, SetEntry<T> C) { SetEntry<T> Result = SetEntry<T>(C._Node); for (unsigned long long i = 0; i < Increment; i++) ++Result; return Result; }
static SetEntry<T> operator -(SetEntry<T> C, unsigned long long Decrement) { SetEntry<T> Result = SetEntry<T>(C._Node); for (unsigned long long i = 0; i < Decrement; i++) --Result; return Result; }
virtual void Reset() { while (!_Node->IsHeader) _Node = NextItem(_Node); }
virtual property Object^ InterfaceCurrentA { Object^ get() = System::Collections::IEnumerator::Current::get { if (_Node->Balance == State::Header) throw gcnew IsEndItemException(); return ((SetNode<T>^)_Node)->Data; } }
virtual property T InterfaceCurrentB { T get() = System::Collections::Generic::IEnumerator<T>::Current::get { if (_Node->Balance == State::Header) throw gcnew IsEndItemException(); return ((SetNode<T>^)_Node)->Data; } }
static Boolean operator ==(SetEntry<T> x, SetEntry<T> y) { return x._Node == y._Node; } static Boolean operator !=(SetEntry<T> x, SetEntry<T> y) { return x._Node != y._Node; }
static long long operator -(SetEntry<T> This, SetEntry<T> iter) { long long Result = 0; while (This._Node != iter._Node) { iter.MoveNext(); Result++; } return Result; }
virtual String^ ToString() override { if (_Node->Balance == State::Header) throw gcnew IsEndItemException(); return Value->ToString(); }
Node^ _Node;
};
generic<typename T>
[Serializable]
public ref class Set : public System::Collections::Generic::ICollection<T>,
public System::ICloneable, public ISerializable, public IComparable<Set<T>^>, public IEquatable<Set<T>^>
{
public: event TypeAdded<T>^ Added; event TypeRemoved<T>^ Removed; event TypeUpdated<T>^ Updated;
protected: Node^ Header; System::Collections::Generic::IComparer<T>^ TComparer; ICloner<T>^ TCloner; IHasher<T>^ THasher; unsigned long long Nodes;
property Node^ Root { Node^ get() { return Header->Parent; } void set(Node^ Value) { Header->Parent = Value; } }
//*** Constructors ***
public:
Set() { Nodes=0; Header = gcnew Node();
TComparer = System::Collections::Generic::Comparer<T>::Default; TCloner = ISharp::Cloner<T>::Default; THasher = ISharp::Hasher<T>::Default;
}
Set(System::Collections::Generic::IComparer<T>^ TCompare) { Nodes=0; Header = gcnew Node(); TComparer = TCompare; TCloner = ISharp::Cloner<T>::Default; THasher = ISharp::Hasher<T>::Default; }
Set(Set<T>^ SetToCopy) { Nodes=0; Header = gcnew Node(); TComparer = SetToCopy->TComparer; TCloner = SetToCopy->TCloner; THasher = SetToCopy->THasher; Copy((SetNode<T>^)SetToCopy->Root); }
Set(System::Collections::Generic::IEnumerable<T>^ Collection) { Nodes=0; Header = gcnew Node(); TComparer = System::Collections::Generic::Comparer<T>::Default; TCloner = ISharp::Cloner<T>::Default; THasher = ISharp::Hasher<T>::Default;
for each (T t in Collection) Add(TCloner->Clone(t)); }
Set(... array<T>^ Collection) { Nodes=0; Header = gcnew Node(); TComparer = System::Collections::Generic::Comparer<T>::Default; TCloner = ISharp::Cloner<T>::Default; THasher = ISharp::Hasher<T>::Default;
for each (T t in Collection) Add(TCloner->Clone(t)); }
Set(System::Collections::Generic::IEnumerable<T>^ Collection, System::Collections::Generic::IComparer<T>^ TCompare) { Nodes=0; Header = gcnew Node(); TComparer = TCompare; TCloner = ISharp::Cloner<T>::Default; THasher = ISharp::Hasher<T>::Default; for each (T t in Collection) Add(TCloner->Clone(t)); }
Set(Set<T>^ A, Set<T>^ B, SetOperation operation) { Nodes=0; Header = gcnew Node(); TComparer = A->TComparer; TCloner = A->TCloner; THasher = A->THasher; CombineSets(A, B, this, operation); }
Set(SerializationInfo^ si, StreamingContext sc) { Nodes=0; System::Collections::Generic::IComparer<T>^ TCompare = (System::Collections::Generic::IComparer<T>^)si->GetValue("TComparer", System::Collections::Generic::IComparer<T>::typeid); ISharp::ICloner<T>^ TClone = (ISharp::ICloner<T>^)si->GetValue("TCloner", ICloner<T>::typeid); ISharp::IHasher<T>^ THasher = (ISharp::IHasher<T>^)si->GetValue("THasher", IHasher<T>::typeid);
Header = gcnew Node(); TComparer = TCompare; TCloner = TClone;
Type^ type = T::typeid;
unsigned long long LoadCount = si->GetUInt64("Count");
for (unsigned long long i = 0; i < LoadCount; i++) { Object^ obj = si->GetValue(i.ToString(), type); Add((T)obj, false); } }
//*** Operators ***
static Set<T>^ operator |(Set<T>^ A, Set<T>^ B) { Set<T>^ U = gcnew Set<T>(A->TComparer); U->TCloner = A->TCloner; U->THasher = A->THasher; CombineSets(A, B, U, SetOperation::Union); return U; }
static Set<T>^ operator &(Set<T>^ A, Set<T>^ B) { Set<T>^ I = gcnew Set<T>(A->TComparer); I->TCloner = A->TCloner; I->THasher = A->THasher; CombineSets(A, B, I, SetOperation::Intersection); return I; }
static Set<T>^ operator ^(Set<T>^ A, Set<T>^ B) { Set<T>^ S = gcnew Set<T>(A->TComparer); S->TCloner = A->TCloner; S->THasher = A->THasher; CombineSets(A, B, S, SetOperation::SymmetricDifference); return S; }
static Set<T>^ operator -(Set<T>^ A, Set<T>^ B) { Set<T>^ S = gcnew Set<T>(A->TComparer); S->TCloner = A->TCloner; S->THasher = A->THasher; CombineSets(A, B, S, SetOperation::Difference); return S; }
static Boolean operator ==(Set<T>^ A, Set<T>^ B) { return CheckSets(A, B, SetOperation::Equality); }
static Boolean operator !=(Set<T>^ A, Set<T>^ B) { return CheckSets(A, B, SetOperation::Inequality); }
static Boolean operator <(Set<T>^ A, Set<T>^ B) { return CheckSets(A, B, SetOperation::Subset); }
static Boolean operator >(Set<T>^ A, Set<T>^ B) { return CheckSets(A, B, SetOperation::Superset); }
property Boolean default [T] { Boolean get(T key) { if (Root == nullptr) return false; else { Node^ search = Root;
do { int Result = TComparer->Compare(key, static_cast<SetNode<T>^>(search)->Data);
if (Result < 0) search = search->Left;
else if (Result > 0) search = search->Right;
else break;
} while (search != nullptr);
return search != nullptr; } } }
static Set<T>^ operator +(Set<T>^ set, T t) { set->Add(t, false); return set; }
static Set<T>^ operator -(Set<T>^ set, T t) { set->Remove(t); return set; }
//*** Properties ***
property SetEntry<T> Begin { SetEntry<T> get() { return SetEntry<T>(Header->Left); } }
property ICloner<T>^ TypeCloner { ICloner<T>^ get() { return TCloner; } void set(ICloner<T>^ Value) { TCloner = Value; } } property System::Collections::Generic::IComparer<T>^ Comparer {System::Collections::Generic::IComparer<T>^ get() { return TComparer; } }
virtual property int Count { int get() { return (int)Length; } }
property SetEntry<T> End { SetEntry<T> get() { return SetEntry<T>(Header); } }
property T First { T get() { return ((SetNode<T>^)LeftMost)->Data; } }
property int Hash { int get() { return GetHashCode(); } }
property IHasher<T>^ Hasher { IHasher<T>^ get() { return THasher; } void set(IHasher<T>^ Value) { THasher = Value; } }
virtual property Boolean IsReadOnly { Boolean get() { return false; } }
virtual property Boolean IsSynchronized { Boolean get() { return true; } }
property T Last { T get() { return ((SetNode<T>^)RightMost)->Data; } }
property Node^ LeftMost { Node^ get() { return Header->Left; } void set(Node^ Value) { Header->Left = Value; } }
property unsigned long long Length { unsigned long long get() { return Count;} }
property Node^ RightMost { Node^ get() { return Header->Right; } void set(Node^ Value) { Header->Right = Value; } } property Object^ SyncRoot { Object^ get() { return this; } }
//*** Public Methods ***
SetEntry<T> After(T Value, Boolean equals) { return SetEntry<T>(equals ? AfterEquals(Value) : After(Value)); }
virtual void Add(T t) { Add(t, false); }
void Add(SetEntry<T> cse) { Add(TCloner->Clone(cse.Value), false); }
unsigned long long Add(System::Collections::Generic::IEnumerable<T>^ copy) { unsigned long long count = 0;
for each(T t in copy) { Add(TCloner->Clone(t), false); count++; }
return count; }
SetEntry<T> Before(T value, bool equals) { return SetEntry<T>(equals ? BeforeEquals(value) : Before(value)); }
virtual void Clear() { Remove(); }
void CallRemoved(T data) { Removed(this, data); }
virtual Object^ Clone() { Set<T>^ setOut = gcnew Set<T>(TComparer); setOut->TCloner = TCloner; setOut->THasher = THasher; setOut->Copy((SetNode<T>^)Root); return setOut; }
virtual int CompareTo(Set<T>^ B) { return CompareSets(this, B); }
virtual bool Contains(T t) { Node^ found = Search(t); return found != nullptr ? true : false; }
virtual Boolean Contains(Set<T>^ ss) { for each (T t in ss) if (Search(t) == nullptr) return false;
return true; }
virtual void CopyTo(array<T>^ arr, int i) { SetEntry<T> begin = SetEntry<T>((SetNode<T>^)Header->Left); SetEntry<T> end = SetEntry<T>(Header);
while (begin != end) { arr->SetValue(TCloner->Clone(((SetNode<T>^)begin._Node)->Data), i); i++; begin.MoveNext(); } }
virtual void CopyTo(System::Array^ arr, int i) { SetEntry<T> begin = SetEntry<T>((SetNode<T>^)Header->Left); SetEntry<T> end = SetEntry<T>(Header);
while (begin != end) { arr->SetValue(TCloner->Clone(((SetNode<T>^)begin._Node)->Data), i); i++; begin.MoveNext(); } }
virtual Boolean Equals(Set<T>^ compare) { SetEntry<T> first1 = Begin; SetEntry<T> last1 = End; SetEntry<T> first2 = compare->Begin; SetEntry<T> last2 = compare->End;
Boolean 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; }
return equals; }
T Find(T value) { Node^ _Node = Search(value); if (_Node == nullptr) throw gcnew EntryNotFoundException(); return ((SetNode<T>^)_Node)->Data; }
virtual System::Collections::IEnumerator^ InterfaceGetEnumeratorSimple() sealed = System::Collections::IEnumerable::GetEnumerator { return gcnew SetEntry<T>(Header); }
virtual System::Collections::Generic::IEnumerator<T>^ InterfaceGetEnumerator() sealed = System::Collections::Generic::IEnumerable<T>::GetEnumerator { return gcnew SetEntry<T>(Header); }
virtual Int32 GetHashCode() override { Int32 HashCode = 0; for each (T t in this) HashCode += THasher->GetHashCode(t); return HashCode; }
virtual void GetObjectData(SerializationInfo^ si, StreamingContext sc) { si->SetType(ISharp::Set<T>::typeid);
Type^ type = T::typeid;
unsigned long long index = 0; for each (T e in *this) { si->AddValue(index.ToString(), e, type); index++; }
si->AddValue("Count", index); si->AddValue("TComparer", TComparer, TComparer->GetType()); si->AddValue("TCloner", TCloner, TCloner->GetType()); si->AddValue("THasher", THasher, THasher->GetType()); }
SetEntry<T> Insert(T t) { return SetEntry<T>(Add(t, false)); }
SetEntry<T> Locate(T value) { Node^ _Node = Search(value); if (_Node == nullptr) throw gcnew EntryNotFoundException(); return SetEntry<T>(_Node); }
void Notify() { Notify((SetNode<T>^)Root); }
unsigned long long Remove() { for each (T t in this) Removed(this, t); unsigned long long count = Nodes; Root = nullptr; LeftMost = Header; RightMost = Header; Nodes = 0; return count; }
virtual bool Remove(T data) { Node^ root = Root;
for (; ; ) { if (root == nullptr) throw gcnew EntryNotFoundException();
int compare = TComparer->Compare(data, ((SetNode<T>^)root)->Data);
if (compare < 0) root = root->Left;
else if (compare > 0)
root = root->Right;
else // Item is found { if (root->Left != nullptr && root->Right != nullptr) { Node^ replace = root->Left; while (replace->Right != nullptr) replace = replace->Right; SwapNodes(root, replace); }
Node^ Parent = root->Parent;
Direction From = (Parent->Left == root) ? Direction::FromLeft : Direction::FromRight;
if (LeftMost == root) { Node^ n = NextItem(root);
if (n->IsHeader) { LeftMost = Header; RightMost = Header; } else LeftMost = n; } else if (RightMost == root) { Node^ p = PreviousItem(root);
if (p->IsHeader) { LeftMost = Header; RightMost = Header; } else RightMost = p; }
if (root->Left == nullptr)
{ if (Parent == Header) Header->Parent = root->Right; else if (Parent->Left == root) Parent->Left = root->Right; else Parent->Right = root->Right;
if (root->Right != nullptr) 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 != nullptr) root->Left->Parent = Parent;
}
AdjustRemove(Parent, From); Nodes--; Removed(this, ((SetNode<T>^)root)->Data); break; } } return true; }
void Remove(SetEntry<T> i) { Remove(i._Node); }
Node^ Search(T data) { if (Root == nullptr) return nullptr; else { Node^ search = Root;
do { int Result = TComparer->Compare(data, ((SetNode<T>^)search)->Data);
if (Result < 0) search = search->Left;
else if (Result > 0) search = search->Right;
else break;
} while (search != nullptr);
return search; } }
virtual String^ ToString() override { String^ StringOut = gcnew String("{");
SetEntry<T> start = Begin; SetEntry<T> end = End; SetEntry<T> last = End - 1;
while (start != end) { String^ NewStringOut = start.Value->ToString(); if (start != last) NewStringOut = NewStringOut + gcnew String(","); StringOut = StringOut + NewStringOut; ++start; }
StringOut = StringOut + gcnew String("}"); return StringOut; }
void Update(T value) { if (Root == nullptr) throw gcnew EntryNotFoundException(); else { Node^ search = Root;
do { int Result = TComparer->Compare(value, ((SetNode<T>^)search)->Data);
if (Result < 0) search = search->Left;
else if (Result > 0) search = search->Right;
else break;
} while (search != nullptr);
if (search == nullptr) throw gcnew EntryNotFoundException();
T saved = ((SetNode<T>^)search)->Data; ((SetNode<T>^)search)->Data = value; Updated(this, saved, value); } }
void Update(SetEntry<T>^ entry, T after) { Update((SetNode<T>^)entry->_Node, after); }
void Validate() { if (Nodes == 0 || Root == nullptr) { if (Nodes != 0) { throw gcnew InvalidEmptyTreeException(); } if (Root != nullptr) { throw gcnew InvalidEmptyTreeException(); } if (LeftMost != Header) { throw gcnew InvalidEndItemException(); } if (RightMost != Header) { throw gcnew InvalidEndItemException(); } }
Validate((SetNode<T>^)Root);
if (Root != nullptr) { Node^ x = Root; while (x->Left != nullptr) x = x->Left;
if (LeftMost != x) throw gcnew InvalidEndItemException();
Node^ y = Root; while (y->Right != nullptr) y = y->Right;
if (RightMost != y) throw gcnew InvalidEndItemException(); } }
//*** Private Methods ***
protected:
Node^ After(T data) { Node^ y = Header; Node^ x = Root;
while (x != nullptr) if (TComparer->Compare(data, ((SetNode<T>^)x)->Data) < 0) { y = x; x = x->Left; } else x = x->Right;
return y; }
Node^ AfterEquals(T data) { Node^ y = Header; Node^ x = Root;
while (x != nullptr) { int c = TComparer->Compare(data, ((SetNode<T>^)x)->Data); if (c == 0) { y = x; break; } else if (c < 0) { y = x; x = x->Left; } else x = x->Right; }
return y; }
SetNode<T>^ Add(T data, bool exist) { Node^ root = Root;
if (root == nullptr) { Root = gcnew SetNode<T>(data, Header); Nodes++; LeftMost = Root; RightMost = Root; Added(this, ((SetNode<T>^)Root)->Data); return (SetNode<T>^)Root; } else { for (; ; ) { int compare = TComparer->Compare(data, static_cast<SetNode<T>^>(root)->Data);
if (compare == 0) // Item Exists { if (exist) { T saved = ((SetNode<T>^)root)->Data; ((SetNode<T>^)root)->Data = data; Updated(this, saved, data); return (SetNode<T>^)root; } else throw gcnew EntryAlreadyExistsException(); }
else if (compare < 0) { if (root->Left != nullptr) root = root->Left; else { SetNode<T>^ NewNode = gcnew SetNode<T>(data, root); Nodes++; root->Left = NewNode; AdjustAdd(NewNode); Added(this, NewNode->Data); return NewNode; } }
else { if (root->Right != nullptr) root = root->Right; else { SetNode<T>^ NewNode = gcnew SetNode<T>(data, root); Nodes++; root->Right = NewNode; AdjustAdd(NewNode); Added(this, NewNode->Data); return NewNode; } } } } }
unsigned long long Add(Node^ begin, Node^ end) { bool success = true; unsigned long long count = 0;
SetEntry<T> i(begin);
while (success && i._Node != end) { if (!i._Node->IsHeader) { try { Add(TCloner->Clone(i.Value), false); count++; i.MoveNext(); } catch (Exception^) { success = false; } } else i.MoveNext(); } if (!success) { if (count != 0) { i.MovePrevious(); SetEntry<T> start(begin); start.MovePrevious();
while (i != start) { SetEntry<T> j(i._Node); j.MovePrevious(); if (!i._Node->IsHeader) Remove(i.Value); i = j; } } throw gcnew AddSubTreeFailedException(); } return Count; }
Node^ Before(T data) { Node^ y = Header; Node^ x = Root;
while (x != nullptr) if (TComparer->Compare(data, ((SetNode<T>^)x)->Data) <= 0) x = x->Left; else { y = x; x = x->Right; }
return y; }
Node^ BeforeEquals(T data) { Node^ y = Header; Node^ x = Root;
while (x != nullptr) { int c = TComparer->Compare(data, ((SetNode<T>^)x)->Data); if (c == 0) { y = x; break; } else if (c < 0) x = x->Left; else { y = x; x = x->Right; } }
return y; }
void Bounds() { LeftMost = GetFirst(); RightMost = GetLast(); }
void Copy(SetNode<T>^ CopyRoot) { if (Root != nullptr) Remove(); if (CopyRoot != nullptr) { Copy(Header->Parent, CopyRoot, Header); LeftMost = GetFirst(); RightMost = GetLast(); } }
void Copy(Node^% root, SetNode<T>^ CopyRoot, Node^ Parent) { root = gcnew SetNode<T>(TCloner->Clone(CopyRoot->Data), Parent); Nodes++;
root->Balance = CopyRoot->Balance;
if (CopyRoot->Left != nullptr) Copy(root->Left, (SetNode<T>^)CopyRoot->Left, (SetNode<T>^)root);
if (CopyRoot->Right != nullptr) Copy(root->Right, (SetNode<T>^)CopyRoot->Right, (SetNode<T>^)root);
Added(this, ((SetNode<T>^)root)->Data); }
Node^ GetFirst() { if (Root == nullptr) return Header;
else { Node^ search = Root; while (search->Left != nullptr) search = search->Left; return search; } }
Node^ GetLast() { if (Root == nullptr) return Header;
else { Node^ search = Root; while (search->Right != nullptr) search = search->Right; return search; } }
void Import(SetNode<T>^ n) { if (n != nullptr) ImportTree(n); }
void ImportTree(SetNode<T>^ n) { if (n->Left != nullptr) ImportTree((SetNode<T>^)n->Left); Add(n->Data, false); if (n->Right != nullptr) ImportTree((SetNode<T>^)n->Right); }
void Notify(SetNode<T>^ root) { if (root != nullptr) { if (root->Left != nullptr) Notify((SetNode<T>^)root->Left);
Added(this, root->Data);
if (root->Right != nullptr) Notify((SetNode<T>^)root->Right); } }
void Remove(Node^ root) { if (root->Left != nullptr && root->Right != nullptr) { Node^ replace = root->Left; while (replace->Right != nullptr) replace = replace->Right; SwapNodes(root, replace); }
Node^ Parent = root->Parent;
Direction From = (Parent->Left == root) ? Direction::FromLeft : Direction::FromRight;
if (LeftMost == root) { Node^ n = NextItem(root);
if (n->IsHeader) { LeftMost = Header; RightMost = Header; } else LeftMost = n; } else if (RightMost == root) { Node^ p = PreviousItem(root);
if (p->IsHeader) { LeftMost = Header; RightMost = Header; } else RightMost = p; }
if (root->Left == nullptr) { if (Parent == Header) Header->Parent = root->Right; else if (Parent->Left == root) Parent->Left = root->Right; else Parent->Right = root->Right;
if (root->Right != nullptr) 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 != nullptr) root->Left->Parent = Parent; }
AdjustRemove(Parent, From); Nodes--; Removed(this, ((SetNode<T>^)root)->Data); }
unsigned long long Remove(Node^ i, Node^ j) { if (i == LeftMost && j == Header) return Remove(); else { unsigned long long count = 0; while (i != j) { SetEntry<T> iter(i); iter.MoveNext(); if (i != Header) { Remove(i); count++; } i = iter._Node; }
return count; } }
void Update(SetNode<T>^ Node, T value) { if (TComparer->Compare(Node->Data, value) != 0) throw gcnew DifferentKeysException(); T saved = Node->Data; Node->Data = value; Updated(this, saved, value); }
void Validate(SetNode<T>^ root) { if (root == nullptr) return;
if (root->Left != nullptr) { SetNode<T>^ Left = (SetNode<T>^)root->Left;
if (TComparer->Compare(Left->Data, root->Data) >= 0) throw gcnew OutOfKeyOrderException();
if (Left->Parent != root) throw gcnew TreeInvalidParentException();
Validate((SetNode<T>^)root->Left); }
if (root->Right != nullptr) { SetNode<T>^ Right = (SetNode<T>^)root->Right;
if (TComparer->Compare(Right->Data, root->Data) <= 0) throw gcnew OutOfKeyOrderException();
if (Right->Parent != root) throw gcnew TreeInvalidParentException();
Validate((SetNode<T>^)root->Right); }
unsigned long long DepthLeft = root->Left != nullptr ? Depth(root->Left) : 0; unsigned long long DepthRight = root->Right != nullptr ? Depth(root->Right) : 0;
if (DepthLeft > DepthRight && DepthLeft - DepthRight > 2) throw gcnew TreeOutOfBalanceException();
if (DepthLeft < DepthRight && DepthRight - DepthLeft > 2) throw gcnew TreeOutOfBalanceException(); }
//*** Static Methods
static void CombineSets(Set<T>^ A, Set<T>^ B, Set<T>^ R, SetOperation operation)
{
System::Collections::Generic::IComparer<T>^ TComparer = R->TComparer; ISharp::ICloner<T>^ TCloner = R->TCloner;
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(TCloner->Clone(first1.Value)); first1.MoveNext(); }
else if (order > 0) { R->Add(TCloner->Clone(first2.Value)); first2.MoveNext(); }
else { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); first2.MoveNext(); } } while (first1 != last1) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); } while (first2 != last2) { R->Add(TCloner->Clone(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(TCloner->Clone(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(TCloner->Clone(first1.Value)); first1.MoveNext(); }
else if (order > 0) { R->Add(TCloner->Clone(first2.Value)); first2.MoveNext(); }
else { first1.MoveNext(); first2.MoveNext(); } }
while (first1 != last1) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); }
while (first2 != last2) { R->Add(TCloner->Clone(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(TCloner->Clone(first1.Value)); first1.MoveNext(); }
else if (order > 0) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); first2.MoveNext(); }
else { first1.MoveNext(); first2.MoveNext(); } }
while (first1 != last1) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); } return; }
throw gcnew InvalidSetOperationException(); }
static Boolean CheckSets(Set<T>^ A, Set<T>^ B, SetOperation operation) { System::Collections::Generic::IComparer<T>^ TComparer = A->TComparer;
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 gcnew InvalidSetOperationException(); }
static int CompareSets(Set<T>^ A, Set<T>^ B) { System::Collections::Generic::IComparer<T>^ TComparer = A->TComparer;
SetEntry<T> first1 = A->Begin; SetEntry<T> last1 = A->End; SetEntry<T> first2 = B->Begin; SetEntry<T> last2 = B->End;
int Result = 0;
while (first1 != last1 && first2 != last2) { Result = TComparer->Compare(first1.Value, first2.Value); if (Result == 0) { first1.MoveNext(); first2.MoveNext(); } else return Result; }
if (first1 != last1) return 1; if (first2 != last2) return -1;
return 0; } };
}
using namespace ISharp;
int main(array<System::String ^> ^args) { Set<int> S = gcnew Set<int>(1, 3, 5 , 6, 7, 9);
Console::WriteLine(S.ToString()); return 0;
} </lang>
- Output:
Inserting integer values 1 to 10 Printing balance: 0 0 0 1 0 0 0 0 1 0
More elaborate version
See AVL_tree/C++
D
<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
<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
<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 = map, but would rather use either an array variable or a dictionary value (which are internally implemented using a high-performance hash table engine).
<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
- 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)}]] }
- Print it out
tree print
- 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]
}
- 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=>''''