dreamplay's blog

Modifying/Inheriting a red-black tree a.k.a set.
By dreamplay, 10 years ago, In English

I need to perform following queries What data structure can i use or modify to.

1) Insert/delete an element(comparable) , say integer , in some order such that i.e. iteration from smallest to largest element at any time , takes O(number of elements) .

2) number of elements greater than ei is given in O(logn) .

...I thought of adding an attribute at each node of r-b tree which stores number of elemts in subtree rooted at that element but this seems incorrect too .

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think it's absolutely correct. In my opinion 2) can be done in a manner like this (pseudocode):

find_num_greater(tree, query):
  if tree == null:               # in an empty tree you cannot find anything
    return 0
  else if tree.value <= query:   # all the greater values are in the right subtree
    return find_num_greater(tree.right_son, query)
  else:                          # this node is greater and all right are greater
    result = 1 + (if tree.right_son != null then tree.right_son.size else 0)
    return result + find_num_greater(tree.left_son, query)

I hope you see the time complexity is per query.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks , yes i got that now .Seems obvious now.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you can use GNU-specific pbds namespace.

tutorial

my recent submission: 10490550

→ Reply