Talk:Order statistic tree

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Rank algorithm should be checked

Anonymous user 178.4.21.216 broke the Select algorithm by making it one-indexed (in contradiction to the comment), then added a Rank algorithm as follows:

function Rank(T, x)
    // Returns the position of x in the linear sorted list of elements of the tree T
    r ← size[left[x]] + 1
    y ← x
    while y ≠ T.root
         if y = right[y.p]
              r ← r + size[left[y.p]] + 1
         y ← y.p
    return r

I'm not sure what y.p is supposed to be, a parent pointer? Also, this probably uses a one-indexed convention. QVVERTYVS (hm?) 14:37, 29 June 2014 (UTC)[reply]

Rope

Would the tree used by Rope (data structure) be considered a variant of an order statistic tree?

The rope's value/weight system seems like a very similar concept, just allowing a node to have a value other than 1.

Soronel~enwiki (talk) 07:23, 7 March 2016 (UTC)[reply]