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. 203.200.95.130 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 80.95.85.174 (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. 92.77.65.80 (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 128.238.245.59 (talk) 02:22, 5 March 2013 (UTC)

\sqrt{M} could be changed to \sqrt{T.M} 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/\sqrt{M})
    lo = x % \sqrt{M}
    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
end 

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? --112.118.153.103 (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
           return
       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;
       return
   if x < T.min then
       swap(x, T.min)
   else if x > T.max then
       T.max = x
   i = floor(x / \sqrt{M})
   Insert(T.children[i], x % \sqrt{M})
   if T.children[i].min == T.children[i].max then
       Insert(T.aux, i)
end

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
           return
       if T.aux is empty then
           T.max = T.min
           return

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 * \sqrt{M} + 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
       return
   if x == T.min then
       i = T.aux.min
       x = i * \sqrt{M} + T.children[i].min
       T.min = x
   
   i = floor(x / \sqrt{M})
   Delete(T.children[i], x % \sqrt{M})
   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
       else
           i = T.aux.max
           T.max = i * \sqrt{M} + T.children[i].max
end

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