(data structure)
Definition: A forest of ordered trees used to contain ordered lists. The root of each tree is unique. An ordered list is represented by a traversal from the root (first element of the list) to a leaf (last list element). Lists with common prefixes share nodes. The last node in common has one child for each list. This allows rapid searches for subset inclusion of sequences.
Aggregate child (... is a part of or used in me.)
heap property.
See also suffix array, universal B-tree.
Note: "UB-tree" refers to this definition or universal B-tree.
Since trees have heap property, any descent produces a list of elements in sorted order.
Nodes may have an unlimited number of children, so an unlimited number of sorted lists that all start with the same element can be represented in one tree.
Author: JP
Jörg Hoffmann and Jana Koehler, A New Method to Index and Query Sets, Proc. Sixteenth International Joint Conference on Artificial Intelligence, pages 462-467, 1999.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 4 June 2010.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
John Phillips, "unlimited branching tree", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 4 June 2010. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/unlimitedBranchingTree.html