| Static Dictionaries Supporting Rank (2001) | |||||||||||||||||
Abstract | |||||||||||||||||
| A static dictionary is a data structure for storing a subset S of a finite universe U so that membership queries can be answered efficiently. We explore space efficient structures to also find the rank of an element if found. We first give a representation of a static dictionary that takes n lg m + O(lg lg m) bits of space and supports membership and rank (of an element present in S) queries in constant time, where n = jSj and m = jU j. Using our structure we also give a representation of a m-ary cardinal tree with n nodes using ndlg me + 2n + o(n) bits of space that supports the tree navigational operations in O(1) time, when m is o(2 ). For arbitrary m, we give a structure that takes the same space and supports all the navigational operations, except finding the child labeled i (for any i), in O(1) time. Finding the child labeled i in this structure takes O(lg lg lg m) time. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||
Publications citing this publication (1) | |||||||||||||||||
| |||||||||||||||||