ADTTree

AVL tree (Adelson-Velsky and Landis) is a self-balancing binary search tree.

AVL trees keep the order of nodes on insertion/delete and allow for fast find operations (average and worst case O(log n)).

If life time handling of allocated elements is needed the callback procedures duplicate and dispose can be used.

By default the tree only takes references of elements and the caller is responsible for keeping elements alive.

TODO : Find safe way to free all nodes.

Procedures

Tree.Init

Initialize

PROCEDURE (VAR this : Tree) Init*;

Tree.Dispose

Removes all elements from the tree.

PROCEDURE (VAR this: Tree) Dispose*;

Tree.Size

Returns the size of the tree.

PROCEDURE (VAR this-: Tree) Size* (): LENGTH;

Tree.FindNode

Find node equal to element argument. Return NIL if no node is found.

PROCEDURE (VAR this-: Tree) FindNode*(element-: Element) : Node;

Tree.HasElement

Return TRUE if tree has element equal to given element

PROCEDURE (VAR this- : Tree) HasElement*(element- : Element): BOOLEAN;

Tree.First

Forward iterator for the tree.

PROCEDURE (VAR this-: Tree) First* (VAR iterator: Iterator);

Tree.Last

Reverse iterator for the tree.

PROCEDURE (VAR this-: Tree) Last* (VAR iterator: Iterator);

Tree.FindForward

Forward iterator where element is found.

PROCEDURE (VAR this-: Tree) FindForward* (VAR iterator: Iterator; element- : Element);

Tree.FindReverse

Reverse iterator where element is found.

PROCEDURE (VAR this-: Tree) FindReverse* (VAR iterator: Iterator; element- : Element);

Iterator.Next

Advance iterator. Return FALSE if end is reached. Note this may be duplicate the element and the caller would be responsible for the lifetime of the element.

PROCEDURE (VAR this: Iterator) Next* (VAR element: Element): BOOLEAN;

Tree.Insert

Insert or replace element

PROCEDURE (VAR this: Tree) Insert*(element-: Element);

Tree.Remove

Remove node from tree if found. Return TRUE if item present and was removed

PROCEDURE (VAR this : Tree) Remove*(element- : Element): BOOLEAN;