Talk:Order statistic tree

Rank algorithm should be checked[edit]

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[edit]

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]