Hi,
 -=> Quoting Don Guy to Soren Petersen <=-
 DG> It could certainly be done, though I think you would be wasting your
 DG> time. In a worst case scenario, you'd have to re-balance the tree after
 DG> the addition of any new node. I expect that the time consumed by the
 DG> process of re-balancing, would effectively negate any advantage which
 DG> you might gain from searching through a balanced BST as opposed to a
 DG> BST in its "natural" state. 
But not balancing it would have a worst case scenario of basically having a
linked list!  This would kinda defeat the Binary Tree idea.  :)
[Digging out Uni Notes]
With a 'balanced' Binary Tree, the worst case search time is
"log n (base 2)"     (Where n is number of elements)
With a completely unbalanced tree (Linked list) worst case time would be
"n"
Admittedly this is not going to be much difference for small trees but for
huge trees this could really matter.
It would also depend on how often the tree was searched compared to be being
updated.  If it was searched once, then updated there would be no point. But
if it were a dictionary it would probably be searched many times before being
updated, and in this case, the time taken to balance would be worth it to
speed up searching.
I agree with you that there would be no real point in balancing, as long as
tree is small.  But I think it would be 'dangerous' to ignore it, especially
for very large trees.
See ya,
Neil Burrows
  /~\  /~\ /~~~~\   E-Mail   - neil@remo.demon.co.uk
  |   \| | | () /            - nburrows@cs.strath.ac.uk
  | |\   | | () \
  \_/  \_/ \____/   Internet - http://www.remo.demon.co.uk/
PGP Key avalible from http://www.remo.demon.co.uk/pgp/
... The fun in C is no one is ever 'wrong', just right in a different way!
---
(2:259/36)
---------------