Questions tagged [van-emde-boas-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer

Proving van Emde Boas recurrence

I have tried to solve the following question: van Emde Boas Bounds Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. Hint: consider the binary representation of $u$. ...
1 vote
0 answers

efficient DELETE in proto-Van Emde Boas Tree?

TLDR: CLRS is claiming that a certain "pseudo" or "proto" tree structure does not have fast deletion, but I seem to have an algorithm that is efficient, and I would like to know ...
1 vote
2 answers

Why do min/max operations in van Emde Boas trees run in $\mathcal{O}(1)$?

I have read in the book "Introduction to Algorithms", 3ed by Cormen, Leiserson, Rivest, and Stein (Chapter 20) that Emde Boas trees run min/max operations in $\mathcal{O}(1)$ time since the ...
1 vote
1 answer

Number of nodes in Van-Emde-Boas tree of universe size u?

The universe size $u$ in vEB trees is square rooted at each level until $u = 2$. So, unlike search trees, the branching factor is different at each level. The height of the tree is $h = \lg \lg(u)$ ...
3 votes
1 answer

How to read off the set represented by a van-Emde-Boas tree?

I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...