# Questions tagged [van-emde-boas-trees]

The tag has no usage guidance.

5 questions
Filter by
Sorted by
Tagged with
1 vote
154 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
68 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 ...
1 vote
243 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 ...
1 vote
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)$ ...