Hierarchical databases, such as binary search trees, are commonly used to provide storage and access to data records that are identifiable by a unique key, such as a string or numeric value. Each record of a binary search tree is associated with up to two other records, called child records, by a pair of pointers designated left and right link pointers. Assignment of a new record as a left or right child of an existing record depends upon the relationship of the key of the new record to the name of the parent record according to a predetermined ordering relation. As records are randomly added to a binary search tree, certain branches or search paths within the tree may become longer than other paths within the tree. Tree-balancing methods are known by which search paths within a binary tree may be made approximately equal in length thereby maintaining a shorter average length of time required to randomly access information stored in a binary tree than in an unbalanced tree or other data structures such as a linked list.
While binary trees may be periodically balanced to provide a low random access delay, another type of tree, a threaded binary tree, allows efficient sequential access to tree-structured data. Each entry in a threaded tree maintains a pointer to a previous entry, such as a parent entry, or to its child entries if any. Such pointers to previous entries are called threads. Sequential access to records within a threaded tree utilizes thread pointers as well as link pointers in order to locate successive entries during sequential traversal of a tree. It would be desirable in the operation of computing systems where the use of both random access and sequential access to tree-structured data is anticipated, to provide a single binary tree structure capable of providing the advantages of balanced binary trees with respect to random access and the advantages of threaded binary trees with respect to sequential access. It would further be desirable to provide methods for inserting and deleting entries within threaded binary trees while maintaining a balanced condition.