Interesting problem involving binary trees

[rotovegasBoy]

Before I start I will point out that rather than some programming problem from a course this is something I've run into at my job and any solution posted might get put into an actual product. Hopefully I'll be sufficiently vague to avoid any intelectual property issues. Here we go.

There is a bar frequented by engineers that has a finite amount of space. Engineers have 2 attributes 1. how much beer they can drink and 2. the time they entered the bar. At any time the bar manager wants to know whos been in the bar the longest or who has been there for a specific amount of time. As the bar fills up to its capacity the bar manager decides to kick out the engineers who can drink the least beer. Assume the attibutes of each engineer is unique.

For speeds sake we'd implement this using a binary tree based on the entry time as this is the most frequent request from the bar manager. We assume that the time between requests from the bar manager is much greater than the time between engineers arriving at the bar. So we can safely reorganise the root of the tree on entry of each engineer with little overhead.

How can we remove the engineer that can drink the least beer given that the engineers are arranged by their entry time attribute.
Pictorally[tt]
engineer = 13.33(entry time)
6 (beers)

12.00
3
/ 11.30 12.30
6 2
/ \ / 11.15 11.45 12.15 12.45
10 1 4 9
[/tt]
We want to remove the engineer that arrived at 11.45 to make room for a new engineer.

Anybody know of an algorithm that can find the engineer that can drink the least beer. My first solution was a recursive function that searched each subtree but this seemed inefficient anybody got a better idea. Try to avoid using straight c code to keep away from any intellectual property/copyright issues. "There are no stupid questions, just lots of inquisitive idiots" - anon

 

[PieterWinter]

Hi

If the overhead in maintaining the tree is really as low as you say, you could duplicate the tree, using the "drinking capacity" as the key.

You would need to maintain both trees, using the "change" result on the one tree to update the other (depending on which tree you use to start any update with).

Also, you would need a way to determine that 2 nodes in the different trees refer to the same "information".

HTH.
Pieter

 

[isaisa]

Hi...
In my opinion , instead of forming plain binary tree threaded binary tree formation would be better option. That will avoid recursion meaning optimizing in terms of memory as well as time. This will reduce the tree traversal in turn the searching.The time will expand exponentially as the tree grows.

Still you can optimize on the searching technique as height balance binary tree or weight balance binary tree as applicable.

Please revert back if i am correct in approach.

Sanjay

 

[rotovegasBoy]

Turns out my problem is the same as what happens in a cpus cache where lookups have to be done on code address but entries need to be selected for removal occasionally, anybody got any useful algorithms/implementations for this purpose. "There are no stupid questions, just lots of inquisitive idiots" - anon

 

[Nosferatu]

Well... I'm sure you don't want to implement a solution to the beer problem but something different so I'm not sure if this idea would fit you.
Since we're talking of fixed amounts of beer - no one can drink 200 beers in one stand, but even if they do... - why not, instead of using a binary tree, you use a simple vector with multiple entries (vector of vectors) whose indexing would mean just the amount of beer a guy/girl can have.
In this vector you'd insert at position X (which again, is a vector or a list) the engineer that can drink X beers. Each search would start therefore with the engineers which can drink less and you know them at any time.

However, this holds of course only for this case - limited, fixed integers as a key.

Please knock me down if I'm wrong with anything... [red]Nosferatu[/red]
We are what we eat...
There's no such thing as free meal...
once stated: methane@personal.ro

 

[Tarwn]

In this case is it not also an issue concerning how many beers the hypothetical engineers have already had? Say we want to knock out the engineer with the least to drink:
As they enter:
A 1pm 10b 1b/hr 10 left
B 2pm 6b 1b/hr 6 left
C 3pm 5b 1b/hr 5 left
D 4pm 6b 2b/hr 6 left
E 5pm 3b 1b/hr 3 left

At 6pm the bartender surveys his flock and decides to kick out the lightweight:
A 1pm 10b 1b/hr 5 left
B 2pm 6b 1b/hr 2 left
C 3pm 5b 1b/hr 1 left
D 4pm 6b 2b/hr 2 left
E 5pm 3b 1b/hr 2 left

Now, should he kick out engineer C for only having one beer left to drink or should he kick out Engineer E for having the lowest overall capacity?

The problem I see with the binary tree is that it will work brilliantly for capacities, but will require full searching for 'amount left'. What you could consider doing instead of making the tree dependant on capacity is make it dependant on estimated time to finish. This may be more difficult with less than exact numbers, but will allow you to kick out only the left most engineer who will be the closest to full.
Tree(assume 1b/hr for all):

                       A
                     11pm
                    /
                   B
                  8PM
                 /                   C     D
               7PM   8PM
                                              E
                      8PM

We assume that >= values go to the right, thus when there is a time for estimated times of departure, we kick out the guy that arrived soonest and move any right dependants into his position (there won't be any left dependants). Regular scans of the tree will allow us to remove people when there time is up by simply following the path for the current time checking the node time:
While(node != null)
if node.time <= time checking for
remove node
right node assumes place
back up one level
endif
Loop

Hope I haven't confused the issue
-Tarwn ------------ My Little Dictionary ---------
Reverse Engineering - The expensive solution to not paying for proper documentation