Online Dictionary Structures:Discussion
Discussion
On average the triebst approach requires less space to represent the d-tuples than our structures. However; multidimensional balanced binary search trees have simple procedures take only O(d+log n) time, and only a constant number of rotations are required after each insert and delete operations. Furthermore, operations like find the (lexicographically) smallest or largest d-tuple (O(log n) time), print in lexicographic order (O(dn) time), concatenation (O(d + log n) time), and split (O(d + log n) time) can also be performed efficiently in this new structure. This approach can also be used in other balanced binary search trees, like AVL, weight balanced, etc.
Comments
Post a Comment