Keeping a binary search tree complete

[Max]

Hi guys, did some searching on the topic, but can't find much more then
just basic info on binary trees. I need to write a binary tree
implementation so that it is always complete. In other words operations
such as add and delete will not cause the completeness to break.
Re-adding all of the elements to a brand new tree and wiping out the old
one is not an option, so any sorting that I do must be in place.

Does anyone know of a good algorithm for this problem? If you have some
code examples that would be nice, but even just the concept will do. Sat
for a while with paper and pencil and can't quiet figure it out
Recursion would probably be best for this, but every time I write
something that I think will work, there's always some special case where
it doesn't. Anyway, if there is a good sorting routine that I can simply
run on the entire tree to make it complete, please let me know.
Otherwise, I need to know specifics for adding and deleting. In either
case, efficiency is important, so that's why I can't do anything like
copying the data to another location and then messing with it there.
Everything has to be done within the original tree.

Thanks for any advice.

 

[Jeff Flinn]

Hi guys, did some searching on the topic, but can't find much more then
just basic info on binary trees. I need to write a binary tree
implementation so that it is always complete. In other words operations

try googling "binary tree balanced"

 

[Max]

try googling "binary tree balanced"

Well the only thing I found on this topic would be this:
http://www.stanford.edu/~blp/avl/libavl.html/Balancing-a-BST.html

However, that talks about converting the tree into a linked list type
structure and then back to the tree. Is there no way to add and delete
nodes is such a way that the tree is always complete. Sort of like a
bubble sort modification? What I originally thought of doing was to keep
on adding all the new nodes to the right-most place in the lowest level.
So from the time that you add the new node, the tree is complete. Now,
however, I need to move that value to the right place and that's what I
have a problem with. Any good way to do that?

 

[Ivan Vecerina]

Well the only thing I found on this topic would be this:
http://www.stanford.edu/~blp/avl/libavl.html/Balancing-a-BST.html

What about: http://www.nist.gov/dads/HTML/redblack.html
This also gives some background and has up-to-date links...

However, that talks about converting the tree into a linked list type
structure and then back to the tree. Is there no way to add and delete
nodes is such a way that the tree is always complete. Sort of like a
bubble sort modification? What I originally thought of doing was to keep
on adding all the new nodes to the right-most place in the lowest level.
So from the time that you add the new node, the tree is complete. Now,
however, I need to move that value to the right place and that's what I
have a problem with. Any good way to do that?

Of course, unless you have 2n-1 elements, the tree cannot be 'complete',
so it is best to say 'balanced'.
Having an optimally balanced tree at all times also can be difficult,
as you also want to minimize changes (not rebuild the tree every time).
The above link describes known approaches (red-black and avl trees)
that do a decent job.

Note that associative containers in the standard C++ library (such
as std::set) are typically implemented using such techniques.


hth

 

[Max]

Of course, unless you have 2n-1 elements, the tree cannot be 'complete',
so it is best to say 'balanced'.
Having an optimally balanced tree at all times also can be difficult,
as you also want to minimize changes (not rebuild the tree every time).
The above link describes known approaches (red-black and avl trees)
that do a decent job.

Note that associative containers in the standard C++ library (such
as std::set) are typically implemented using such techniques.


hth

When I say complete I mean balanced. We've been taught to use full tree
to indicate one that has 2n-1 elements and is complete. Same thing, just
taught using different terminology. Unfortunately I can't get into
anything more complicated then a regular binary search tree (project
requirements). We didn't get to AVL yet and I can't modify any of the
object definitions, only need to implement them. Right now I'm thinking
about just giving up on the idea, seems too complicated given our
project requirements. Thanks anyway.