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

The tag has no usage guidance.

5 questions
Filter by
Sorted by
Tagged with
813 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 ...
• 703
1 vote
247 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 ...
• 343
1 vote
159 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
302 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
1 vote