My Math Forum Binary search tree problem

 Computer Science Computer Science Forum

 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 k-1 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 sub-trees 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mdocka1 Trigonometry 6 November 2nd, 2014 01:40 AM frenchiehey Algebra 1 November 21st, 2013 06:00 PM flexdec Applied Math 0 July 16th, 2013 05:25 AM tatausi Algebra 1 December 5th, 2012 12:22 AM limengxi Advanced Statistics 1 March 9th, 2011 12:49 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top