Hard
van Emde Boas insert with and without a separately stored minimum
A van Emde Boas tree over universe size u splits each key into a cluster index (high half of its bits) and an offset (low half), giving √u clusters, each a vEB tree of size √u, plus a summary vEB tree of size √u recording which clusters are nonempty. In the CLRS design each node stores its min separately and never inserts that min into any cluster, so inserting into an empty cluster just sets its min in O(1), and insert makes at most one recursive call that does real work. A simplified version drops this trick and stores every key inside its cluster, so inserting into an empty cluster needs a full recursive insert into the cluster and another into the summary. What is the insert complexity of each version?
38 of 46 in Data Structures & Algorithms