Extended AVL - Tree
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Rezmann, F: AUTHOR [+2]
A concept is disclosed that extends the known AVL-tree data structure (Adelson - Velskii - Landis 1962) in such a way that also access via an absolute order number (ONR-access in the following) is possible with binary search.
Extended AVL - Tree
A concept is
disclosed that extends the known AVL-tree
data structure (Adelson - Velskii - Landis 1962) in such a way that
also access via an absolute order number (ONR-access in the
following) is possible with binary search.
Balanced trees are data structures used to
give quick access to
large sets of objects with binary search; which means a complexity of
log N, where N is the number of objects.
is one of the most well-known concepts of balanced
trees, which allows access via a key.
is that beside the key-access many applications
need other forms of access with a similar and good performance. One
can divide three classes:
Access via a key. This means to get an object with a
specific and unique identifier.
Access via an absolute sequence number (ONR-access). This
means to get an object which is the nth in a defined sequence.
Access via a relative sequence number. This means to get
an object which is the nth in a defined sequence starting from a
specific object which is identified by its key.
invention expands the AVL-tree concept to allow access for
all three access-types from above with a similar performance. With
the normal AVL-tree an ONR-access can result in accessing all objects
in the tree in the worst case.
The change to
the normal AVL-tree is simply expanding the
information in an AVL-tree node with the count of objects in the left
subtree (including the node itself).
This has the following impact on AVL-tree
- Access via a key.
This access method is not affected by the new information
Here the new count can be used to get the nth object with
The following algorithm describes the request to get the
Nth object out of the tree. COUNT is the count of objects in the
left subtree which is stored in every node and ONR is the abs...