
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
April 19th, 2015, 12:43 PM  #1 
Member Joined: Mar 2015 From: USA Posts: 30 Thanks: 0  Binary search tree problem
hope this is the right section to put this. the problem: Let it be X set of integers. describe a data structure with linear size, based on Binary search tree, which supports the following methods: 1. insertion(a)  insert new integer a to X. 2. search(k)  return the k largest size element in X (the element which exactly k1 integers are bigger than it). for each method you can use at most o(h) memory, when h is the height of the tree. so, I know how to solve this only with more than o(h) memory for the second method. I think i need to add here two fields for each node at the tree that contains the number fo subtrees that are bigger/smaller than it, but i dont know how to proceed from here. Can you show me the way? 

Tags 
binary, problem, search, tree 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Trig  tree problem  mdocka1  Trigonometry  6  November 2nd, 2014 01:40 AM 
random variable binary tree problem  frenchiehey  Algebra  1  November 21st, 2013 06:00 PM 
Average search cost of an unsuccessful search in a BST?  flexdec  Applied Math  0  July 16th, 2013 05:25 AM 
Problem with binary tree  tatausi  Algebra  1  December 5th, 2012 12:22 AM 
how to solve this tree diagram problem  limengxi  Advanced Statistics  1  March 9th, 2011 12:49 AM 