My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
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 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?
motant is offline  
 
Reply

  My Math Forum > Science Forums > Computer Science

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





Copyright © 2018 My Math Forum. All rights reserved.