As of May 31, 2023, we have updated our Code of Conduct.

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

The tag has no usage guidance.

5 questions
Filter by
Sorted by
Tagged with
1 vote
66 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 ...
• 818
1 vote
146 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
240 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
278 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