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

Copyright (c) 1993 xTech Ltd, Russia. All Rights Reserved. Tenko : Modified for inclusion in library.

Types

TreeNode* = POINTER TO TreeNodeDesc;

TreeNodeDesc* = RECORD
        element-: ADT.Element;
        left, right, up: TreeNode;
        bal: LONGINT;
    END;

Tree * = POINTER TO TreeDesc;

TreeDesc* = RECORD (TreeNodeDesc)
        minimum: TreeNode;
        size: LONGINT;
    END;

TreeIterator* = POINTER TO TreeIteratorDesc;

TreeIteratorDesc* = RECORD
        tree : Tree;
        current : TreeNode;
        reverse : BOOLEAN;
    END;

Procedures

TreeNode.Next

PROCEDURE (this : TreeNode) Next*() : TreeNode;

TreeNode.Prev

Prev node or NIL if first

PROCEDURE (this : TreeNode) Prev*() : TreeNode;

Tree.Clear

Clear tree content

PROCEDURE (this : Tree) Clear*;

Tree.Init

Initialize

PROCEDURE (this : Tree) Init*;

Tree.IsEmpty

Return TRUE if tree is empty

PROCEDURE (this: Tree) IsEmpty*(): BOOLEAN;

Tree.Size

Return tree size

PROCEDURE (this: Tree) Size*(): LONGINT;

Tree.First

Return first node

PROCEDURE (this: Tree) First*(): TreeNode;

Tree.Last

Return last node

PROCEDURE (this: Tree) Last*(): TreeNode;

Tree.Iterator

Get tree iterator

PROCEDURE (this : Tree) Iterator*(reverse := FALSE : BOOLEAN): TreeIterator;

TreeIterator.Next

Advance iterator. Return FALSE if end is reached.

PROCEDURE (this : TreeIterator) Next*() : BOOLEAN;

TreeIterator.Element

Current element or NIL

PROCEDURE (this : TreeIterator) Element*() : ADT.Element;

TreeIterator.Reset

Reset iterator to start of tree.

PROCEDURE (this : TreeIterator) Reset*();

Tree.FindNode

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

PROCEDURE (this: Tree) FindNode*(element: ADT.Element) : TreeNode;

Tree.Find

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

PROCEDURE (this: Tree) Find*(element: ADT.Element) : ADT.Element;

Tree.Insert

Insert element

PROCEDURE (this: Tree) Insert*(e: ADT.Element);

Tree.Remove

Remove element from tree if found

PROCEDURE (this: Tree) Remove*(e: ADT.Element);