Online Dictionary Structures:Additional Operations
Additional Operations
With respect to other operations, one can easily find the smallest or largest d-tuple in O(log n) time by just taking all the leftchild or rightchild pointers. By traversing the tree in inorder one can print all the d-tuples in increasing in O(dn) time. An O(d + log n) time algorithm to concatenate two sets represented by the structure can be easily obtained by using standard procedures provided that all the d-tuples in one set are in lexicographic order smaller than the ones in the other set. The kth smallest or largest d-tuple can be found in O(log n) time after adding to each node in the tree the number of nodes in its left subtree.
The split operation is given a d-tuple q and a set represented by a multidimensional balanced binary search tree t, split t into two multidimensional balanced binary search trees, one containing all the d-tuples in lexicographic order smaller than or equal to q, and the other one containing the remaining elements. At first glance, it seems that the split operation cannot be implemented within the O(d+log n) time complexity bound. The main reason is that there could be Ω(log n) rotations and each rotation takes time proportional to d. However, the analysis in [5] for the rotation operation which is shown in Section 24.4 can be improved and one can show that it can be easily implemented to take constant time. The reason for this is that for a simple rotation, see Figure 24.2, the lj or the hj value need to be updated for the node labeled b, and we know the lptr and hptr pointers. This value can be computed from previous values before the rotation, i.e., the lj and hj values for node b and the fact that the rptr value for b is node d before the rotation. The other value to be updated is the lj value for node d after the rotation, but this is simply the rj value for node d before the rotation.
The efficient implementation of the rotation operation allows us to use the technique in [5] on many other binary search trees, like AVL, weight balanced, etc., since having O(log n) rotations does not limit the applicability of the techniques in [5]. These observations were first made in [6] where they present a similar approach, but in a more general setting.
Comments
Post a Comment