Talk:Van Emde Boas tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.

van or Van?[edit]

Is this structure really known as the vEB tree, with a lowercase v? In Dutch last names written separately, initial prepositions or articles are capitalized, thus:

  • Peter van Emde Boas
  • Van Emde Boas, Peter
  • meneer Van Emde Boas (mister VEB)

Qwertyus 01:16, 21 July 2006 (UTC)

They are popularly called vEB trees in many other sources that I've seen, which I'm pretty sure predate this article.[1][2][3] This may not be technically correct, but it seems to be conventional. I don't know whether the lowercase v is used when the name is spelled out in full. Deco 01:48, 21 July 2006 (UTC)

In many sources that I have noticed when the name is spelled out in full it is written as "Van Emde Boas Queue". But when written in the abbreviated form it is written as vEB queue. 12:28, 1 November 2007 (UTC)

I've changed it to Van Emde Boas tree since that seems common enough.. With a lowercase initial letter, it just looks too strange. Qwertyus (talk) 12:19, 22 June 2012 (UTC)

.max is never returned by findNext[edit]

findNext returns always only ".min" values, never ".max"... What if the value we are searching for is stored in some .max field? (E.g. the tree contains values 34 and 47 and none between them, 47 is stored in some .max field, and "findNext(38)" is called.) —Preceding unsigned comment added by (talk) 22:01, 7 October 2009 (UTC)

I implemented the algorithms as described here, and found they are full of mistakes (such as the one you mentioned - the last line for FindNext is completely wrong) or unclear (M as the keysize depends on the level of the subtree, but here it looks as if it's the same for all trees). I suggest removing the current code altogether until someone provides a correct sample implementation. Greetings, IP. (talk) 13:27, 23 July 2011 (UTC)

I looked up the algorithm in the textbook CLRS. I only looked at it for a few minutes, but I found at least the fix for one of the problems mentioned above: T.min should not be stored recursively, but T.max SHOULD. — Preceding unsigned comment added by (talk) 02:22, 5 March 2013 (UTC)

could be changed to to make it more clear that M is a function specific to T. Dhirallin (talk) 06:33, 4 March 2014 (UTC)

Note also, the FindNext function is broken. the <= operators need to be replaced with <, and the > operator needs to be replaced with >=.

This is for 2 reasons: Firstly, a successor function should find the next item AFTER x, and should not return x. Otherwise you will be unable to iterate over items in the tree using FindNext(). Secondly if x falls into bucket i, but x >= T.children[i].max then T.children[FindNext(T.aux, i)] == T.children[i] which is not correct. So it should look like this:

function FindNext(T, x)
    if x < T.min then
        return T.min
    if x ≥ T.max then // no next element
        return M
    i = floor(x/)
    lo = x % 
    hi = x - lo
    if lo < T.children[i].max then
        return hi + FindNext(T.children[i], lo)
    return hi + T.children[FindNext(T.aux, i)].min

Dhirallin (talk) 00:51, 6 March 2014 (UTC)

How to pronounce?[edit]

I cannot find anywhere on the net about how to pronounce Van Emde Boas. Can someone add the IPA into the article? -- (talk) 03:46, 12 July 2010 (UTC)

I added my best shot. QVVERTYVS (hm?) 15:27, 7 March 2014 (UTC)

Change letter[edit]

I think, it would be easier to read, if the letter m was changed to w, which is the conventional letter for "word length". Gabriel (talk) 15:26, 13 May 2011 (UTC)

Bug in insert function[edit]

There's a bug in insert function when T.min<T.max<x The T.max won't be updated Please fixTheme (talk) 03:13, 13 March 2013 (UTC)

Ok I think someone made an attempt to fix that last bug, however, now if you look at the following code:

   if T.min == T.max then
       if x < T.min then
           T.min = x
       if x > T.max then
           T.max = x

The return statement above is surely an error, because if x < T.min, then the old T.min needs to be added to a sub-tree. In fact that whole block seems unnecessary to me and the Insert function could look like this:

function Insert(T, x)
   if T.min > T.max then // T is empty
       T.min = T.max = x;
   if x < T.min then
       swap(x, T.min)
   else if x > T.max then
       T.max = x
   i = floor(x / )
   Insert(T.children[i], x % )
   if T.children[i].min == T.children[i].max then
       Insert(T.aux, i)

Correct me if I'm wrong? Dhirallin (talk) 05:34, 4 March 2014 (UTC)

Initial values[edit]

I can't find anything that talks about the initial values of T.min and T.max Theme (talk) 03:13, 13 March 2013 (UTC)

unreachable code in delete function[edit]

       if T.aux is empty then
           T.min = T.max
       if T.aux is empty then
           T.max = T.min

This fragment of code is unreachable because if T.aux is empty, the only element in the tree is min, so min=max and is caught in the first ifTheme (talk) 03:13, 13 March 2013 (UTC)

Bug in delete function[edit]

When the only data in the tree are T.min and T.max, and x==T.max, T.children[T.aux.max].max will be T.max, so T.max=T.children[T.aux.max].max is incorrectTheme (talk) 03:20, 13 March 2013 (UTC)

Indeed, I agree with the two bugs above. Also the following statements are generally incorrect:

T.min = T.children[T.aux.min].min 
T.max = T.children[T.aux.max].max

i.e. remember these values were stored in the sub-tree as x % sqrt(M) and need to be re-combined with the high part of the number. e.g.

i = T.aux.max
T.max = i *  + T.children[i].min

The code would look like:

function Delete(T, x)
   if T.min == T.max == x then
       T.min = M
       T.max = -1
   if x == T.min then
       i = T.aux.min
       x = i *  + T.children[i].min
       T.min = x
   i = floor(x / )
   Delete(T.children[i], x % )
   if T.children[i] is empty then
       Delete(T.aux, i)

   if x == T.max then
       if T.aux is empty then
           T.max = T.min
           i = T.aux.max
           T.max = i *  + T.children[i].max

Dhirallin (talk) 06:13, 4 March 2014 (UTC)

Practical applications[edit]

It would be nice to read something about practical applications of the tree. Maybe some software that uses it? — Preceding unsigned comment added by Michael.lill (talkcontribs) 11:32, 1 June 2017 (UTC)