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

The tag has no usage guidance.

6 questions
Filter by
Sorted by
Tagged with
30 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 ...
58 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$. ...
16 views

### Alternate Range in Van Emde Boas Tree

DISCLAIMER: I initially asked this question of Stack Overflow but that seems like the wrong place in hindsight so I want to ask here as well since this site is more meant for students and their ...
210 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 ...
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)$ ...