van Emde Boas Trees and Hash Tables

van Emde Boas Trees - Dynamic Predecessors Uri Zwick Tel Aviv University

Dictionaries Binary Search Trees ?(log?) time Insert Delete Find Hash Tables ? 1 time vEB Trees ?(log?) time Successor / Predecessor Find-min / Find-max ? word size Typically log ? < log?

Splitting a word ? bits ?? ??? ?/2 bits ?/2 bits ?? = ? >> (?/2) ??? = ? & ((1 << (?/2)) 1) ?(1) time

Definitions ? the set of keys in the dictionary ???? ?,? = min ? ? ? > ? } ??? ? = ?? ? | ? ? ??? ?,? = ??? ? | ? ? ?? ? = ?

van Emde Boas Trees A vEB tree representing ? consists of: ? word size ??? the minimal key in ? ??? the maximal key in ? ??? a vEB tree for ??? (? ???,??? ) ??? a hash table, giving for every ? ??? (? ???,??? ), a pointer to a vEB tree for ???(? ???,??? ,?)

van Emde Boas Trees Are ???,??? better names than ??? ,????

van Emde Boas Trees If ? = then ??? = 1 and ??? = 0 If ? = {?} then ??? = ? and ??? = ? If ? 2 then ??? = min? < ??? = max? (Can add a ???? field) If ? 2 then ??? = ???? and ??? = If ? > 2 then ??? ???? and ??? Keeping at least one of ??? and ??? is essential for the efficiency of the data structure

van Emde Boas Trees For compactness, we use array inspired notation for manipulating hash tables. ??? ? ???.??? ????(?) ??? ? ? ???.??? ?????? ?,? ??? ? ???? ???.??? ?????? ? van Emde Boas actually used arrays and not hash tables in his original data structure. Hash tables introduced later by [Mehlhorn-N her (1990)]

?.??????(?) The boring part: If ??? > ??? (? = ) then ???,??? ? ; return If ? = ??? or ? = ??? then return If ? < ??? = ??? then ??? ? ; return If ??? = ??? < ? then ??? ? ; return Of some interest: If ? < ??? then ? If ? > ??? then ? ??? ??? The interesting part: Insert ? given that ??? < ? < ???

?.??????(?) Insert ? given that ??? < ? < ??? Split ? into ( ?? ,???) If ? already contains a middle item beginning with ?? , recursively insert ??? into ???[ ?? ] Otherwise, allocate a new vEB tree containing ?/2-bit keys and insert ??? into it. And, recursively insert ?? to the vEB tree ??? . (Initialize ??? if not initialized yet.) Important: Only one recursive call at each level

?.??????(?) Insert ? given that ??? < ? < ??? ( ?? ,???) ?????(?,?) if ??? ?? ???? then: ???[ ?? ].??????(???) else: ??? ?? ??? ?/2,??? if ??? = ???? then: ??? ???(?/2, ?? ) else: ??? .??????( ?? )

?.??????(?) The boring part: If ??? > ??? (? is empty) then return If ? < ??? or ? > ??? then return If ? = ??? = ??? and then ??? 1 ; ??? 0 ; return The interesting parts: Delete ? given that ? = ??? < ??? Delete ? given that ??? < ??? = ? Delete ? given that ??? < ? < ???

?.??????(?) Delete ? given that ? = ??? < ??? If ? = 2 (??? is ????) then ??? ??? ; return Otherwise, find and set the new min of ?: ?? of new min is ??? .??? ??? of new min is ??? ?? .??? Delete ( ?? ,???) from ? The case ??? < ??? = ? is analogous

?.??????(?) Delete ? given that ? = ??? < ??? if ??? = ???? then: ??? ??? return else: # Set the new minimum ?? ??? .??? ??? ???[ ?? ].??? ??? ???????( ?? ,???) Delete ( ?? ,???) from ?

?.??????(?) Delete ? given ??? < ? < ??? Split ? into ( ?? ,???). Recursively delete ??? from ???[ ?? ]. If ???[ ?? ] is now empty then: Destroy ??? ?? . Delete ?? from ???. Recursively delete ?? from ??? . If ??? is empty, destroy it. Important: Only one recursive call at each level is a real non-trivial recursive call.

?.?????????(?) If ? < ??? then return ??? If ? ??? then return 0 (no successor) Split ? into ( ?? ,???) If ?? ??? and ??? < ???[ ?? ].??? then recursively compute the successor ???1 of ??? in ??? ?? and return ( ?? ,???1) If ??? ???? then recursively compute the successor ?? 1 of ?? in ??? . If ?? 1 exists, return ( ?? 1,???[ ?? 1].???) If ??? = ???? or ?? 1 does not exist, return ???

?.?????????(?) if ??? ?? ???? and ??? < ???[ ?? ].??? then: return ???????( ?? ,???[ ?? ].?????????(???)) else: if ??? = ???? then: return ??? else: ?? 1 ??? .?????????( ?? ) if ?? 1 = 0 then: return ??? else: return ???????( ?? 1,???[ ?? 1].min)

Time complexity We assume that each hash table operation takes ?(1) time, which holds in expectation. We sometimes need to double the size of the hash table, or cut it by a factor of 4. This can be taken care of by amortization or background rebuilding. Each operation on a vEB tree with ?-bit keys spends ?(1) time and then performs at most one non-trivial recursive call on a vEB tree with (?/2)-bit keys.

Time complexity ? 2 ? ? = ? 1 + ? ? 1 = ? 1 ? ? = ? log?

Exercise: (Trivial) Add a ????operation to a vEB tree. How much time does it take? Augment the data structure to support ???? in ?(1) time. Exercise: Design a variant of vEB trees that does not explicitly maintains the ??? and ??? items. What are the times required by the different operations? Exercise: Design a variant of vEB trees that maintains ??? but not ??? items. Implement efficiently an operation that finds either the successor or the predecessor. Show how the data structure can be augmented to return successors and predecessors.

Space complexity Where are items actually stored? In ??? and ??? fields. Total space used is proportional to number of vEB structures, which is proportional to total number of ??? s and ??? s. A hash table containing ? items has size ?(?) and it points to ? vEB structures. Thus, the size of the table can be charged to the ??? and ??? items in these ? structures. Important: We do not keep empty vEB structures.

Space complexity To be continued On the blackboard.