[prog] balancing a binary tree

Jacinta Richardson jarich at perltraining.com.au
Tue Mar 9 18:48:49 EST 2004


On Mon, 8 Mar 2004, ed orphan wrote:

> Can anyone direct me to a tutorial on how
> to balance a binary tree?
> I've got plenty of information on how to
> build a binary tree, but from what I've read,
> after a while the tree becomes unbalanced
> due to insertions and deletions. As a result,
> the tree's efficiency goes way down.
> Not much purpose in using a tree if it
> self-destructs efficency-wise and I can't
> repair it.

How balanced your tree is depends on how well you picked the pivot point
and how random your data is.

For example consider the phone book.  A naive program would pick the pivot
point to be right in the middle of the alphabet: n.  This would always
tend to give you unbalanced trees as there will be more data in A-N than
O-Z.  Of course experience shows us that K would be a better pivot point
here.

Still, you're correct.  Consider the following tree:

                          Kane
                   Aaabert   Kanea

If we pretend that Aaabert is the first entry in the phonebook then
everything in the A-K tree is going to end up down the right hand side of
the Aaabert tree.  Likewise if Kanea is the next entry (in sort order)
after Kane, then everything in the K-Z tree is going to end up down the
right hand side of Kanea.

In the general case (with properly randomised data) your tree will remain
_fairly_ balanced, or at least not too unbalanced to be useless.

However, if you want a good balancing algorithm, consider AVL trees:
	http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html

Alternately there's a reasonable article over here:
	http://www.mactech.com/articles/mactech/Vol.06/06.08/BinaryTrees/

Good luck.

	Jacinta

--
   ("`-''-/").___..--''"`-._          |  Jacinta Richardson         |
    `6_ 6  )   `-.  (     ).`-.__.`)  |  Perl Training Australia    |
    (_Y_.)'  ._   )  `._ `. ``-..-'   |      +613 9354 6001         |  
  _..`--'_..-_/  /--'_.' ,'           | contact at perltraining.com.au |
(il),-''  (li),'  ((!.-'              |   www.perltraining.com.au   |



More information about the Programming mailing list