Efficient data structure to maintain a set of postal codes and mailbox numbers

Question

A 'person' is represented by a combination of postal code and mailbox number(both are natural numbers)

No two postal codes are alike, yet a postal code can contain many different mailboxes.

At any given postal code, all mailboxes have different numbers.

Display a data structure that supports the following methods in best complexity:

$Insert(z,p)$: insert a new person into the structure, who's postal code is $z$ and mailbox number is $p$.

$Delete(z,p)$: delete a person with postal code $z$ and mailbox number $p$ .

$Median(z)$: at postal code $z$, who has a mailbox that is the median? (half of people at postal code $z$ have mailbox with lower number)

$Max(z_1,z_2)$: out of the people living in the range $z_1 \rightarrow z_2$, who has the maximal mailbox number?

$HowMany(x)$: how many postal codes have exactly $x$ mailboxes?

The DS I've come up with was an AVL tree, where each key is a postal code and each node has a pointer to another AVL tree which represents the mailboxes in that postal code. That solves $insert/delete$ in

$O(max\{log$(amount of postal codes)$, log$(amount of mailboxes in postal code z)$\})$

which seems pretty efficient.

From this point forward I'm not sure how to continue, Median seems like $O(log$(amount of postal codes)$)$ to me since the mailboxes are in an AVL tree, so we can keep track of how many mailboxes we got, if number of mailboxes is uneven, the median is at the root, else we can find the heavier subtree and claim the median is the mean of the root and the root of said subtree, yet I'm not sure that works.

About $max$ and $howmany$, I still can't think of a solution that yields anything better than $O(n)$ where $n=$number of postal codes so far.

What would be some efficient data structure for my situation?

Answer 1

Your idea of using a tree of tree representation seems good. Let $n$ be the current number of postal codes and $m$ be the current maximum number of mailboxes in any postal code. Then the insert and delete implementation takes $O(\log n + \log m) = O(\log nm)$.

To implement median, you can make the mailbox tree of each postal code to be an order statistic tree. This will give you a bound of $O(\log nm)$ running-time.

To implement max, first augment each postal code node $z$, so it will store the current maximum mailbox number of its mailbox tree as $z.max$. Also, let $z.maxT$ be a pointer to the node that has the largest $max$ value in $z$'s subtree. Note that it's possible for $z.maxT$ be equal to $z$. The $maxT$ of each nodes must be updated accordingly after every insert and delete. Now, find $z_1$. As you do the search, check the $max$ attribute of all nodes $z$ in the search path such that $z_1 \le z \le z_2$ and remember the node $z_1'$ with the maximum $max$ attribute. Next, find $z_2$ similarly to also find $z'_2$. Finally, compare the $max$ attributes of $z_1'$, $z_1.right.maxT$, $z_2'$, and $z_2.left.maxT$ to find the overall maximum in the range $[z_1, z_2]$. The $left$ and $right$ attributes are pointers to the left and right child of a node. Since this procedure performs 2 searches in you postal code tree, it takes $O(\log n)$.

As for howmany, the only idea I have to prevent checking all postal codes is to create another AVL tree such that the key of each node is a number $m'$ representing the number of mailboxes and the value of the node is the number of postal codes with $m'$ mailboxes. Think of this as a reverse look-up map, such that given a number of mailboxes, it returns the number of postal codes that have such mailboxes. In the worst-case, each postal code will have different number mailboxes, so the size of this tree is $n$. Performing a howmany operation is just a search in the tree, which takes $O(\log n)$ time. However, an insert or delete operation will requires adding/deleting/updating of this tree, which also incurs an additional $O(\log n)$ time to insert and delete. But since its just an additive increase, it does not affect the overall asymptotic running-time of the two operations.