Oberon || Library || Module Index || Search Engine || Definition || Module

Ulm's Oberon Library:


AVLTrees - height-balanced-binary trees for data-storage and retrieval


CONST ascending = 0;
CONST descending = 1;
TYPE Order = Iterators.Mode (* ascending, descending *)

TYPE AVLTree = POINTER TO AVLTreeRec; TYPE AVLTree = RECORD (Services.ObjectRec) END; CONST keyUsed = 0 CONST noSuchKey = 1 CONST wrongKey = 2 CONST errorcodes = 3

TYPE ErrorCode = SHORTINT; TYPE ErrorEvent = POINTER TO ErrorEventRec; TYPE ErrorEventRec = RECORD (Events.EventRec) errorcode: ErrorCode; avlTree: AVLTree; object: Services.Object; key: Keys.Value; END;

VAR error: Events.EventType; VAR errormsg: ARRAY errorcodes OF Events.Message;

PROCEDURE Create(VAR new: AVLTree; key: Keys.Key); PROCEDURE GetKey(avlTree: AVLTree; VAR key: Keys.Key); PROCEDURE Add(avlTree: AVLTree; object: Services.Object) : BOOLEAN PROCEDURE Remove(avlTree: AVLTree; keyval: Keys.Value) : BOOLEAN; PROCEDURE Get(avlTree: AVLTree; keyval: Keys.Value; VAR object: Services.Object) : BOOLEAN; PROCEDURE Card(avlTree: AVLTree) : INTEGER; PROCEDURE GetEntries(avlTree: AVLTree; order: Order; from, to: Keys.Value; VAR it: Iterators.Iterator); PROCEDURE Exists(avlTree: AVLTree; keyValue: Keys.Value) : BOOLEAN;


AVLTrees implements AVL trees (named after Adelson-Velsky and Landis, the inventors). Every AVL tree has an associated key with a total-order relation (see Keys) and allows to store and retrieve objects that support that key. As AVL trees are sorted height-balanced binary trees, all operations have a worst cases time of log(N) where N is the number of objects stored in the AVL tree.

Create creates an empty AVL tree. All objects to be added to this AVL tree are expected to support key which defines the sorting order.

GetKey returns the key of the given AVL tree.

Add adds object to the AVL tree. This means, it can be retrieved by the key components as defined by the key of the given AVL tree. There must not be an object with the same value (of its key) in the AVL tree. Add returns TRUE if object has been added to avlTree, otherwise FALSE.

Remove removes an object from the AVL tree specified by the given key. A return value of TRUE indicates success.

Get returns the object with the given value (with respect to key), if the AVL tree contains such an object. Otherwise noSuchKey is raised. A return value of TRUE indicates success.

Card returns the number of objects in the AVL tree.

GetEntries returns an iterator of objects in AVL tree. Possible orders are ascending and descending. The range of objects to be iterated can be narrowed by from and to. If NIL is given for from (respectively to), iteration starts at the first (respectively stops at the last) object. Note, that iteration must not be carried on over changing operations on the AVL tree.

Exists returns TRUE, iff the AVL tree contains an object with the given value (with respect to key).


Errors lead to events raised by AVLTrees or an underlying implementation. Following errors may be raised by AVLTrees:
There is already an object with this value (with respect to key) in the AVL tree.
The AVL tree contains no object with this value (of its key).
A parameter does not support the needed key.


support of total-order relations


Sven Lutz
Edited by: borchert, last change: 2004/07/19, revision: 1.2, converted to HTML: 2004/07/19

Oberon || Library || Module Index || Search Engine || Definition || Module