Browse Prior Art Database

Extended AVL - Tree

IP.com Disclosure Number: IPCOM000122291D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 65K

Publishing Venue

IBM

Related People

Rezmann, F: AUTHOR [+2]

Abstract

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.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 53% of the total text.

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.

      The AVL-tree is one of the most well-known concepts of balanced
trees, which allows access via a key.

      The problem 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.

      This 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 operations:
      -    Access via a key.
           This access method is not affected by the new information
stored.
      -    ONR-access.
           Here the new count can be used to get the nth object with
binary search.
           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...