Questions tagged [van-emde-boas-trees]
The van-emde-boas-trees tag has no usage guidance.
5 questions
1
vote
0
answers
93
views
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 ...
- 858
1
vote
1
answer
173
views
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
2
answers
271
views
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 ...
- 353
1
vote
1
answer
360
views
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)$ ...
- 172
3
votes
1
answer
950
views
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 ...
- 713