algorithm - Cracking the Coding Interview 6th Edition: 10.10. Rank from Stream -

the problem statement follows:

imagine reading in stream of integers. periodically, wish able rank of number x (the number of values less or equal x). implement data structures , algorithms support these operations.that is, implement method track (in t x), called when each number generated, , method getrankofnumber(int x) , returns number of values less or equal x (not including x itself).

example: stream(in order of appearance): 5, 1, 4, 4, 5, 9, 7, 13, 3

getrankofnumber(1) = 0 getrankofnumber(3) = 1 getrankofnumber(4) = 3

the suggested solution uses modified binary search tree, each node stores stores number of nodes left of node. time complexity both methods is o(logn) balanced tree , o(n) unbalanced tree, n number of nodes.

but how can construct balanced bst stream of random integers? won't tree become unbalanced in due time if keep on adding same tree , root not median? shouldn't worst case complexity o(n) solution (in case hashmap o(1) , o(n) track() , getrankofnumber() respectively better)?

you need build avl or red-black tree have o(lg n) complexities desire.

about rank, kind of simple. let's call count(t) number of elements of tree root t.

• the rank of node n be:
  • firstly there count(n's left subtree) nodes before n (elements smaller n)
  • let = n's father. if n right son of a, there 1 + count(a's left subtree) nodes before n
  • if right son of b, there 1 + count(b's left subtree) nodes before n
  • recursively, run way until reach root or until node in isn't someone's right son.

as height of balanced tree @ lg(n), method take o(lg n) return someone's rank ( o(lg n) find + o(lg n) run , measure rank ), taking in consideration nodes store sizes of left , right subtrees.

hope helps :)