Insomnia
Posted by Dan Byström on March 6, 2008
| To iterate is human, to recurse divine. | ||
|
L. Peter Deutsch |
| To iterate is boring, to recurse plesantly dizzying. | ||
|
Dan Byström |
Have you ever tried counting sheep when trying to sleep? For twenty years I’ve been utilizing a different method. I’ve been trying to solve the following problem:
How do you build a balanced binary search tree from a stream of sorted data of unknown size?
That is, given a stream of the letters: ABCDEFGHIJKLMNO, construct the following tree:
H / \ D L / \ / \ B F J N /
\ /
\ /
\ /
\ A C E G I K M O
directly by reading the characters one by one and place them DIRECTLY in the correct position WITHOUT using any intermediate storage.
I’m confident that this has been thoroughly researched at least half a century ago, but I have never wanted to look up any solution – what’s the fun in solving a crossword puzzle if you look at the solution first?
This sleeping strategy has been very successful, up until last week, when baby Ellen gave up a horrible cry in the middle of the night – and while trying to go to sleep again I remembered this old problem. Accidentally I solved it and now it’s useless as a sleeping pill!!! But since I have a history with this problem for twenty years now, I thought I had to write a little memorial over it before letting go.
This will also be a tribute to the most powerful solving method I know of: Divide and Conquer!
Background
Two decades ago, when I was a student (that was at a time when I could also be called both young and promising) taking a programming course I chose to write a record register application using Turbo Pascal 3.0. This was a time when CD players were just as common a Bly-ray players today (that is: most people were still waiting for the prices to drop). Vinyl was the name of the game. (Turbo Pascal 3.0, by the way, was an incredible piece of work; the whole environment consisted of one file with the whopping size of 38kb containing the full runtime system, the compiler and the source code editor! You read right: 38kb – not 38Mb!)
I wanted this application to be able to run smoothly with its data files residing on a floppy disc (and of course, memory consumption had to be low). I chose to use binary search trees to keep track of the albums, artists and song titles. This worked well and it was quite fun figuring out all the things that were not in the books, like: given an arbitrary node in a tree, how do you implement a “next” function that will bring you to the next node in sort order when the user hits the “next” button? Not completely obvious the first time you try to acquaintance yourself with the concept of trees. Adn then embarrasingly simples once you figured it out.
However, there was this one thing that I never bothered to figure out, but took an easy way out. That has nagged me ever since.
Prequisities
Let’s declare a simple binary tree node:
public class Node<T> where T : IComparable<T>
{
public readonly T Data;
public Node<T> Left;
public Node<T> Right;
public Node( T data )
{
Data = data;
}
}
Then let’s define a data pump that will read data/records/entities (or whatever we like to call them) from some kind of stream. The important thing here is that there is no look-ahead facility:
interface IStreamingDataPump<T> where T : IComparable<T>
{
T GetNextData();
boolEOF { get; }
}
Maybe it helps our thinking if we have a concrete example implementation of the interface as well:
public class TestCharPump : IStreamingDataPump<char>
{
string data = "ABCDEFGHIJKLMNO";
int index = 0;
public char GetNextData()
{
return data[index++];
}
public bool EOF
{
get { return index >= data.Length; }
}
}
Obviously, this data pump will deliver the sorted characters A to O (in order) to a consumer, throwing an error if trying read past the last character.
The problem with inserting already sorted data
The standard way of inserting data into a binary tree:
public static Node<T> Insert( Node<T> tree, T data )
{
while ( true )
switch ( Math.Sign( tree.Data.CompareTo( data ) ) )
{
case 1:
if ( tree.Left == null )
return tree.Left = new Node<T>( data );
tree = tree.Left;
break;
case -1:
if ( tree.Right == null )
return tree.Right = new Node<T>( data );
tree = tree.Right;
break;
case 0:
throw new Exception( "Duplicate keys!" );
}
}
If we read all the data from our stream containing sorted data and use the method above:
Node<T> tree = _pump.EOF ? null : new Node<T>( _pump.GetNextData() );
while( !_pump.EOF )
Node<T>.Insert( tree, _pump.GetNextData() );
…then we effectively end up with a linked list instead of a binary tree:
A B C D E F G H I J K L M N O
The standard(?) solution
So, what I’ve did in my record register application was something like this:
public Node<T> CreateTreeFromList( List<T> list, int left, int right )
{
if ( left > right )
return null;
int middle = (left + right) / 2;
Node<T> tree = new Node<T>( list[middle] );
tree.Left = CreateTreeFromList( list, left, middle - 1 );
tree.Right = CreateTreeFromList( list, middle + 1, right );
return tree;
}
And then made use of that function like this:
List<Song> list = new List<Song>();
while( !_pump.EOF )
list.Add( new Song( _pump ) );
Node<Song> tree = Node<Song>.CreateTreeFromList( list, 0, list.Count - 1 );
As you can see, I first read the whole stream into memory and then I construct the tree from there.
This will construct a perfectly balanced tree and the performance will be good. So what’s the problem? Well, actually there is no real problem, it is just that I feel that first storing the data in a vector, when it is a tree we want is an unnecessary step!!!
Another approach
So, given ABCDEFGHIJKLMNO, I want to read one character at a time and place it at the correct position in the balanced tree:
H / \ D L / \ / \ B F J N /
\ /
\ /
\ /
\ A C E G I K M O
And again, the number of nodes must not be known in advance!
So let’s think about it. Reading A into a node seems uncomplicated. Then we should read B and somehow realize that it must be placed in such a manner that it will become the new tree root and that the previous tree root should become the left node of the new root.
Reading C and placing it as the right node of the current tree root seems fair enough, and the next node D should be handled similar to the B node… but now it gets strange, the E node should be placed in a void because F hasn’t been seen yet… and what if there IS no F node? If E is the last element in the stream it should come directly under D but not if the F appears.
And thinking about what will happen after the G is read seems even stranger, although there clearly isa pattern here if you say “EFG” will be handled exactly like “ABC”, and in fact, B and F behaves similar… so… what makes A and E alike… aaaa….
This is were I used to fall asleep. 🙂
Up until a night last week, then my brain got bored of having to start all over again with this problem and thought that it was best to settle the thing once and for all. There was no quantum leap – just the most common tool we use every day: divide and conquer!
With the aid of first one and then two helper functions the solution was suddenly crystal clear.
Reasoning away…
Firstly, one thing that disturbs my thinking a great deal is that we always have the risk of running into EOF. We can reduce that problem somewhat by a tiny helper:
public Node<T> ReadNodeFromStream()
{
if( _pump.EOF )
return null;
return new Node<T>( _pump.GetNextData() );
}
Thinking about it, what we now have is a function that can create a zero or one element sized tree. Not bad really! 😉 Also note one other important fact: we are allowed to call this many times after reaching EOF – it will return null every time.Can we extend this into a three element sized tree (=height of two)?
public Node<T> thinkingOutLoud_1()
{
Node<T> left = ReadNodeFromStream();
Node<T> tree = ReadNodeFromStream();
Node<T> right = ReadNodeFromStream();
tree.Left = left;
tree.Right = right;
return tree;
}
Well, not quite… this will work if there are at least two elements in the stream, but otherwise it will crash. It can be fixed very easily though:
public Node<T> thinkingOutLoud_2()
{
Node<T> left = ReadNodeFromStream();
Node<T> tree = ReadNodeFromStream();
if ( tree == null )
return left;
Node<T> right = ReadNodeFromStream();
tree.Left = left;
tree.Right = right;
return tree;
}
Spot on! What about a next step… modifying the method to create a one or two level high tree?
public Node<T> thinkingOutLoud_3( int height )
{
if ( height == 1 )
return ReadNodeFromStream();
Node<T> left = ReadNodeFromStream();
Node<T> tree = ReadNodeFromStream();
if ( tree == null )
return left;
Node<T> right = ReadNodeFromStream();
tree.Left = left;
tree.Right = right;
return tree;
}
This method knows how to create two different sized trees, and it has no trouble at all dealing with EOF. But wait a minute… can’t we just as well write it this way, it wouldn’t change a thing if we call it with parameter of 1 or 2:
public Node<T> thinkingOutLoud_4( int height )
{
if ( height == 1 )
return ReadNodeFromStream();
Node<T> left = thinkingOutLoud_4( height-1 );
Node<T> tree = ReadNodeFromStream();
if ( tree == null )
return left;
Node<T> right = thinkingOutLoud_4( height-1 );
tree.Left = left;
tree.Right = right;
return tree;
}
But what if we call it with a desired height of three… or four…? Wow! I think that we safely can rename this method:
public Node<T> CreateTreeOfDesiredHeight( int height )
{
if ( height == 1 )
return ReadNodeFromStream();
Node<T> left = CreateTreeOfDesiredHeight( height-1 );
Node<T> tree = ReadNodeFromStream();
if ( tree == null )
return left;
Node<T> right = CreateTreeOfDesiredHeight( height-1 );
tree.Left = left;
tree.Right = right;
return tree;
}
AHHH! Recursion. (Said like Homer Simpson.)
If we knew the length of the stream we could create our tree like this:
Node<T> tree = createTreeOfDesiredHeight(
(int)Math.Ceiling( Math.Log( _pump.Length ) / Math.Log( 2 ) ) );
But we don’t. So exactly how does this help us anyway? It actually helps quite a lot – we’re almost done. We just have an iterative method left. And since iterative methods are boring, I won’t say much about it:
public Node<Data> CreateBalancedTree()
{
Node<Data> left = ReadNodeFromStream();
for ( int height = 1 ; ; height++ )
{
Node<Data> tree = ReadNodeFromStream();
if ( tree == null )
return left;
tree.Left = left;
tree.Right = CreateTreeOfDesiredHeight( height );
left = tree;
}
}
Well, maybe I should say something…
- Create a “left tree” of height one and then try to tuck on a root above it.
- If there are no more elements, then out left tree is the tree and we´re done.
- Otherwise create a right tree of the same height as our left tree
- Name our newly created tree the new “left tree” and repeat step two
Note that the key to this solution is step 3 – creating a subtree of a desired height. The part that made me pleasantly dizzy! 🙂
But… wait a minute… is this really it? Isn’t it strange that we now use completely different pieces of code to produce the left tree and the right tree??? Indeed it is! The CreateTreeOfDesiredHeight method is only a helper method I used to arrive at the solution!!! Since our CreateBalancedTree method is obviously fully capable of of creating the left tree and there is no difference between a left tree and a right tree:
The solution
public Node<Data> CreateBalancedTree( int maxHeight )
{
Node<Data> left = ReadNodeFromStream();
for ( int height = 1 ; height<maxHeight ; height++ )
{
Node<Data> tree = ReadNodeFromStream();
if ( tree == null )
return left;
tree.Left = left;
tree.Right = CreateBalancedTree( height );
left = tree;
}
return left;
}
Iteration begone! And since a caller doesn’t care about any maxHeight, we can create our final (overloaded) method as such:
public Node<Data> CreateBalancedTree()
{
return CreateBalancedTree( int.MaxValue );
}
Again, it is so embarrassingly simple once you figured it out! And this tiny piece of (almost) trivial code eluded me for so long!
OK, so now this was really really old news I guess. And there are things to criticize as well. First of all, what’s the point really? The method of loading the stream into a vector works faster AND produces a better tree, since my solution actually isn’t balanced (it is in our case where the number of elements is 2N-1) – it just has the same height as a balanced tree. But I’m fine with that.
There seems to be a lot of misconceptions around recursion out there, like that it is slow and uses an excessive amount of stack memory. Of course, calculating Fibonacci numbers using recursion instead of iteration should only be done as an intellectual exercise. But the fact that people think that it’s slow may be due to reasoning like this:
Fact: A recursive algorithm is slower than an iterative method when an equal iterative method exist.
Conclusion: All recursive algorithms are slow.
This is of course exactly the same reasoning as:
Fact: All cheeses are round and the moon is round.
Conclusion: The moon is made out of cheese.
Well, well. I don’t know how to end this, but I’ll give it a try anyway:
| Try and be nice to people, avoid eating fat, read a good book every now and then, get some walking in, and try and live together in peace and harmony with people of all creeds and nations. | ||
|
Monty Python |
Dan Byström's Bwain 
Morgan Persson said
nice.
So, has the duck talked back lately? 😉
danbystrom said
The Rubber Duck may very well have a finger, eh, foot in the above…. 😉
Stefan said
Det var trevlig läsning, härligt att se att du gymnastiserar de grå på småtimmarna!
En monolog som slog mig när jag läste det logiska resonemanget på slutet:
http://www.cse.unsw.edu.au/~norman/Jokes-file/LogicProfessor.html
Hoppas allt är väl för övrigt, vi får ta en lunch framöver!
/stefan
danbystrom said
Det var absolut inget sammanträffande! Självklart hade jag monologen från “The Album of the Soundtrack of the Trailer of the Film of Monty Python and the Holy Grail” i åtanke när jag skrev den! 🙂