Binary trees?

hi people :)

does anyone know of a good site, or tutorial that descibes the HOWS, WHATS, AND WHERES of binary trees.

regards:

Regan

Do you mean Balanced Trees?

I think therefore I am... sometimes right. images/icons/wink.gif

Really, i'm not sure what i mean images/icons/smile.gif

i've been trying to learn about the Huffman compression. ZIP.... but his method uses block-block coding that builds binary trees to store repeated byte data. (for strings) The problems lies in the fact that i have no understand "Binary Trees", which makes understanding Huffman kinda difficult.

Maybe thats what i'm looking for, is "Balanced trees". If so, any suggestions where to start?

thanks:

You can probably find "Algorithms" by Robert Sedgewick in your library. It's kind of a standard reference....

It has chapters on binary trees, balanced trees, b-trees etc....

ISBN 0-201-06673-4


"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

I had never heard of binary trees. A balanced-tree structure is the normal
way almost all databases build indexes. It allows for efficient search and
retrieval of a particular key. Even though it is referred to as a tree, it looks
more like a pyramid. The number of total keys stored and the number of
keys that can hang from any branch determine how many levels it has.
An index on a table with 10 million rows will usually only require 6 or 7
levels (disk reads) to locate any one key.

I think therefore I am... sometimes right. images/icons/wink.gif

thanks guys,

Billsoo i'll look in the library tomorrow, if its not to pricy i'll pick up a copy. By what thinker has descibed, "Balance trees" are a powerful tool.

Are they used much in professional software, and could i expect to encounter one in an aplication sometime do the road?



"The crows seem to be calling his name, thought Caw."

You will probably not see a balanced tree because it would be hidden in the level below.

As a database user, you don't have to know how the DB stores it's indices, just as long as it works and works well.



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Im quite familiar with binary trees. The basic concept is a tree network where each node can have up to two branches, so from the top, the maximum amount of nodes on each level are 1,2,4,8,16 and so on, (hence binary).

Binary trees are arranged in the order in which they are most useful, usually in alphabetical order or numerical order, depending on the data.

To add an item, you look at the top node. If your item belongs later than the node, you go right, otherwise you go left. Then, you perform the same comparison on the next node, going left or right, until you reach a node where you must create a new branch. A balanced tree is one where each side of the tree has a similar number of nodes. An example of an unbalanced tree is one where every node only has a branch to the left (and in this case the tree is as unbalanced as possible).

To search the tree, you use the same method as you do for adding items, starting at the top node and working downwards until you come to a node which matches or reach a node with no branches (no match).

There are 3 method displaying the whole tree data, pre-order, in-order and post-order. The most useful one, and the one you want is in-order as this results in listing the items in the correct order (either alphabetical or numerical or whatever........). It follows a simple recursive algorithm:

<pre>Sub TestNode(Node as Node)
If Node has a left branch then
TestNode(leftbranchnode)
End If
Display Node
If Node has a right branch then
TestNode(rightbranchnode)
End If
End Sub</pre>

its simple to remember but very hard to visualise it working in your head. Basically, it will visit the left branch first, then the node, then the right branch. If the left branch happens to have its own left branch then that is processed first, and so on......

This is just a little help to get you started..... images/icons/smile.gif

Thank you squirm :)

very informative reply !

best regards:

Regan

"The crows seem to be calling his name, thought Caw."

Thanks, but Im on a roll here......

To use a binary tree you need a 2d array....... such as Node(nodemax, 3)

The second dimension has 3 parts...... Node(x,1) is the subscript of a node that lies to the LEFT. Node(x,3) is the subscript of a node that lies to the RIGHT. Node(x,2) contains the node data (im sure this can be better arranged as the data is likely to be a string and the left and right pointers will be integers). If a node doesnt have a left branch then Node(x,1) = -1 and the same for right branch.

Node(0) will always be the root node, at the top of the whole tree. Depending on whether it has left or right branches, it will have them stores as numbers in (x,1) and (x,3). To give you an example of how they are arranged:

the data in the right branch of node 0 will be : Node(Node(0,3),2)

I hope you follow........