Binary Tree Balancing Algorithm
Mystery Student
any binary tree and return one with lg(n) height (with n=number of nodes).
Could someone please help me.
Thanks,
--
===========================================================================
Mr. Leslie P. Howard "Mr. Lehrer's muse (is) not
University of Georgia fettered by such inhibiting
how...@castor.cs.uga.edu factors as taste"...New York Times
Eric Jacobsen
>I am looking for an algorithm to balance a binary tree. It should take in
>any binary tree and return one with lg(n) height (with n=number of nodes).
In a CACM issue about a year ago I read an article that promised
an algorithm with O(n) time. Sounded impressive to me. What they
did, though, was basically just to walk the tree, put it into an
array, then rearrange the tree. I may be wrong about the authors'
actual methodology, but for *your* task, it'll work, and is simple.
Good luck
Eric Jacobsen
Dave Schaumann
>I am looking for an algorithm to balance a binary tree. It should take in
>any binary tree and return one with lg(n) height (with n=number of nodes).
>Could someone please help me.
You should be able to find such an algorithm in any data structures text worth
the name.
Of course, the translation of the algorithm to compilable and executable code
is left as an exercise to the reader, but that's no problem, right?
--
Dave Schaumann da...@cs.arizona.edu
Gene Ressler
>In article <1992Apr19....@athena.cs.uga.edu> how...@castor.cs.uga.edu (Mystery Student) writes:
>>I am looking for an algorithm to balance a binary tree. It should take in
>>any binary tree and return one with lg(n) height (with n=number of nodes).
>>Could someone please help me.
>
>You should be able to find such an algorithm in any data structures text worth
>the name.
>
Well, data structure books talk a lot about _incrementally_ balancing a tree
in O(log n) time after a single add or delete, or in O(n log n) amortized time for n
such ops. Using this stuff, there's a trivial O(n log n) solution to balancing
an arbitrary tree: Insert each node into a new AVL or 2-3 tree or what have you.
But it's possible and in fact easy to do in O(n). This is another one of
those problems where it's useful to restate something that's inherently
recursive (i.e. an in-order tree traversal) in the form of an iterator with its
own state. Here's a hack:
( One other thing: Shame on the Mystery Student if this is homework. )
/* Balance a binary tree preserving in-order relation. */
#include <stdio.h>
#include <stdlib.h>
/* Good for a giga-node tree. */
#define LOG_N 30
/* Canonical tree node. */
typedef struct node {
int i; /* Label for printing only. Not used by algorithm. */
struct node *l, *r;
} *node_t;
/* Stack and pointers for tree fragments. */
static node_t stk[LOG_N], *p = stk, *root = stk;
/* Add a node to a balanced tree with fragments stored in the stack. */
void add_node(node_t n)
{
p[0] = n;
if (p > stk && p[-1] != NULL) {
if (p > root) root = p;
n->l = p[-1], p[-1] = NULL, p = stk;
}
else
for (++p; p[0] != NULL; ++p)
p[0]->r = p[-1], p[-1] = NULL;
}
/* Pass nodes in-order to the balancer. */
void walk(node_t tree)
{
node_t r;
if (tree == NULL)
return;
walk(tree->l);
r = tree->r; tree->r = tree->l = NULL;
add_node(tree);
walk(r);
}
/* Balance a tree. */
node_t balance(node_t tree)
{
int i;
node_t q;
walk(tree);
/* Collect fragments. Generally necessary unless n = 2^k - 1. */
for (q = *root, i = root - stk - 1; i >= 0 && q->r == NULL; --i)
if (stk[i] != NULL)
q->r = stk[i], q = stk[i], stk[i] = NULL;
/* Reinit for the next call. */
q = *root, *root = NULL, p = root = stk;
return q;
}
/* Sanity check. */
void print_tree(int level, node_t tree, int left_p)
{
static char branch_p[LOG_N];
int i;
for (i = 0; !left_p && i < level; ++i)
printf(branch_p[i] ? "| " : " ");
if (tree == NULL) { printf("*\n"); return; }
branch_p[level] = left_p;
printf("+%3d", tree->i);
print_tree(level+1, tree->r, 1);
print_tree(level+1, tree->l, 0);
}
void main(int argc, char *argv[])
{
int i, n;
node_t node, tree;
if (argc == 1 || sscanf(argv[1], "%d", &n) != 1)
n = 15;
tree = NULL;
/* Build right or left-skewed tree. */
if (n < 0)
for (i = -1 - n; i >= 0; --i) {
node = (node_t)malloc(sizeof(struct node));
node->i = i; node->r = tree; node->l = NULL;
tree = node;
}
else
for (i = 0; i < n; ++i) {
node = (node_t)malloc(sizeof(struct node));
node->i = i; node->l = tree; node->r = NULL;
tree = node;
}
print_tree(0, balance(tree), 0);
}
Mystery Student
>In article <36...@caslon.cs.arizona.edu> da...@cs.arizona.edu (Dave Schaumann) writes:
>>In article <1992Apr19....@athena.cs.uga.edu> how...@castor.cs.uga.edu (Mystery Student) writes:
>>>I am looking for an algorithm to balance a binary tree. It should take in
>>>any binary tree and return one with lg(n) height (with n=number of nodes).
>>>Could someone please help me.
>>
>>
>
>
Well, If this was homework, everyone was very helpful giving me the code to
do this, not a general algorithm. Anyway, the book that my school uses
for the algorithms class is really bad. (I checked it first but found
nothing usefull). I wanted to balance a binary tree in a program that I wrote
about a year ago, to speed it up, and I didn't want to go in and make it a 2-3
tree (because I didn't feel like rewriting that much code). So I was looking
for a neat, spiffy algorithm to balance it for me. The only thing I came up
with was to read the whole tree into an array (or a list) and put the middle
element in the root of the tree, and the middle of each remaining half, in
the children of the parent, etc... I figured that there must be a better way
than this.
General algorithms please, I prefer doing my own implementations!
me how to do it with code, not with a descriptive algorithm.
Mark-Jason Dominus
> The only thing I came up with was to read the whole tree into an
> array (or a list) and put the middle element in the root of the
> tree, and the middle of each remaining half, in the children of the
> parent, etc... I figured that there must be a better way than this.
Gee, that sounds great. It's fast and simple. (Constant time per
node). What is it you don't like about it?
I think you're going to have an awfully hard time finding a better way.
--
Millions for defense, but not one cent for tribute.
Mark-Jason Dominus m...@central.cis.upenn.edu
Jerry Penner
>In article <1992Apr20.1...@athena.cs.uga.edu> how...@castor.cs.uga.edu (Mystery Student) writes:
>> The only thing I came up with was to read the whole tree into an
>> array (or a list) and put the middle element in the root of the
>> tree, and the middle of each remaining half, in the children of the
>> parent, etc... I figured that there must be a better way than this.
> Gee, that sounds great. It's fast and simple. (Constant time per
>node). What is it you don't like about it?
>I think you're going to have an awfully hard time finding a better way.
There's the old AVL balanced binary tree algorithm. Each node
contains one additional value: balance. It's an integer which
determines which child is "heavier" ( <0 for left heavier, 0 if
balanced, >0 if right heavier). All the tree operations have to be
modified when using this algorithm. And balancing can take some time
but it's not as time consuming as making a linear list and rebuilding
the tree. I don't have the algorithm on hand here (I have pascal
source code on some bizarre disk format) but you can get it from
Algorithms + Data Structures = Programs (or is it P = A + D?? :-) by
Niklaus Wirth. Should be in any decent University library. I don't
own a copy. Just look for "AVL Balanced binary trees".
--
Jerry Penner jpe...@ee.ualberta.ca
Bennet Yee
>There's the old AVL balanced binary tree algorithm.
>source code on some bizarre disk format) but you can get it from
>Algorithms + Data Structures = Programs (or is it P = A + D?? :-) by
>Niklaus Wirth. Should be in any decent University library. I don't
>own a copy. Just look for "AVL Balanced binary trees".
Beware that Wirth's code in A+DS=P has a bug, so _think_ while you're
copying it.
Building the new tree using AVL from the old unbalanced tree requires
O(n logn) time, whereas walking it to generate a table and using the
table indices to build a new tree is O(n) as others have noted. Note
that if you want balance and you add/delete elements, using AVL or
splay or 2-3 or ... is better than periodically rebalancing in this
manner (i.e., if you rebalance after every k requests and tree has
``average'' size n (and k << n), you incur O(k logn) cost instead of
O(n) cost).
-bsy
--
Bennet S. Yee Phone: +1 412 268-7571 Email: bs...@cs.cmu.edu
School of Computer Science, Carnegie Mellon, Pittsburgh, PA 15213-3890
Sean Barrett
>In article <1992Apr20.1...@athena.cs.uga.edu> how...@castor.cs.uga.edu (Mystery Student) writes:
>> The only thing I came up with was to read the whole tree into an
>> array (or a list) and put the middle element in the root of the
>> tree, and the middle of each remaining half, in the children of the
>> parent, etc... I figured that there must be a better way than this.
> Gee, that sounds great. It's fast and simple. (Constant time per
>node). What is it you don't like about it?
It may be possible to do without the array--I'm not positive one
way or the other.
If you only need to access the nodes in order, rather than randomly,
then you don't need an array; an inorder walk of the tree will do.
Basically you build the tree upwards:
Suppose inorder your tree looks like 1-2-3-4-5-6- ... (you don't know
how far it goes yet).
Then you could build this as a node at a time as follows; this is rather
like building a b tree (you add nodes upwards)
add 1:
1
add 2:
2
1
add 3:
2
1 3
add 4:
4
2
1 3
add 5:
4
2 5
1 3
This starts getting hairy here.
add 6:
4
2 6
1 3 5
add 7:
4
2 6
1 3 5 7
etc.
It seems the running up and down the tree here
might end up taking you O(n lg n) time; it might
not.
Now, of course, you may not consider some of the
trees output by this routine balanced. (Look at
the case of only having built 1-4 above.) The
original question merely asked for a tree of the
correct depth.
buzzard
Richard J. Delahanty
>>>>I am looking for an algorithm to balance a binary tree. It should take in
>>>>any binary tree and return one with lg(n) height (with n=number of nodes).
>>>>Could someone please help me.
>>>
Check out _Fundamental Algorithms_ by Donald Knuth. It's an oldie (1968),
but a goodie. You may find your answer there.
--
===============================================================================
Rick Delahanty "VMS'er in Unixland" || Purgamentum init,
Internet: rdel...@cs.umb.edu || exit purgamentum.
Phone (work): 617/929-2509 ||
Martin Ehrenstein
Summary of the question (see References in the header for details and authors):
Given a (ordered) binary tree, turn it into a balanced (ordered) binary
tree as efficiently as possible (in terms of time and (extra) space).
*Balanced* is supposed to mean *a tree of least height*.
Yup, you can do without the array and you need O(n) time and O(height) extra
space.
(height) is (n) in the worst case but only (log n) in practice (on average??).
You may of course need space for the new balanced tree, but I have the
feeling if you really want to make things hard you can do it in situ,
that is just changing the pointers of the old tree around while walking
(or traversing if you prefer that term) the tree, but that seem quite
messy.
If you want a balanced tree in the sense that for each node the size of
the left subtree differs from the size of the right subtree by at most
one you probably need a two-pass algorithm (that is first finding out
how large that tree is before balancing it).
My algorithm is quite like Sean Barrett`s but you do not have to traverse
balanced subtrees again after you've build them once.
OKAY, THAT'S NOT MUCH OF A HINT, but I guess the problem is how to cook up
an algorithm in general. My favourite method is to read the problem and
read the recommended reading (this is the hard bit), then go windsurfing
(this is hard too, if there isn't any wind), then go to a party,
then get a piece of paper, and finally watch a boring TV programme.
The way I cooked up my algorithm (which I will mail/post you in a week
if you like) was to break the problem into simpler pieces:
(1) put tree into sorted array
(2) turn sorted array into balanced tree
Now can I think of (2') that is another algorithm to turn the array into
a tree. I worked a couple of examples (maybe on paper). And realized
that there were some features, or possibilities for shortcuts.
A good question was: Where does the first element go in the tree?
Where ... the first few? Where does the first half go.
Finally doing the reading (luckily I finished that a year or two ago)
was helpful to use a slightly different version of (1).
Last not least I just need to merge (1') and (2') togther, which turned
out to be much easier than merging (1) and (2).
Tell me if this is any use.
Martin E
--
---------------------------------------------------------------------------
mar...@comp.vuw.ac.nz Martin Ehrenstein mar...@romeo.anu.edu.au
> > > > > > > insert your favourite disclaimer here < < < < < < <
Jeremy Gibbons
>
> In article <1992Apr20.0...@cs.cornell.edu> res...@cs.cornell.edu (Gene Ressler) writes:
> >In article <36...@caslon.cs.arizona.edu> da...@cs.arizona.edu (Dave Schaumann) writes:
> >>In article <1992Apr19....@athena.cs.uga.edu> how...@castor.cs.uga.edu (Mystery Student) writes:
> >>>I am looking for an algorithm to balance a binary tree. It should take in
> >>>any binary tree and return one with lg(n) height (with n=number of nodes).
> >>>Could someone please help me.
> The only thing I came up
> with was to read the whole tree into an array (or a list) and put the middle
> element in the root of the tree, and the middle of each remaining half, in
> the children of the parent, etc... I figured that there must be a better way
> than this.
There is a better way, as Martin Ehrenstein points out. If you can turn the
tree into a linked list, then turn the linked list into a balanced tree,
you're done (because you can then fuse the two parts together to avoid having
to build the linked list in the first place). There's an obvious way to turn a
linked list into a balanced tree in O(n log n) time (find the length; build
trees from the first and from the second halves), but you want it in O(n) time.
The solution is to write a function that takes a linked list and a number k,
and returns the tree made from the first k elements of the list, and the
remaining n-k elements of the list (in O(k), rather than O(n), time). The
details are in Bird and Wadler, An Intro to Functional Programming, Prentice
Hall, section 9.5.
The interesting thing about this problem is that it helps to think about linked
lists (normally a handicap of functional languages), even in an imperative
language; it's only when you disallow random-access arrays that you can
fuse the two stages together. (If I had built an array, rather than the linked
list, it wouldn't have been at all obvious how to proceed without using an
extra O(n) space.)
Jeremy
*---------------------------------------------------------------------*
| Jeremy Gibbons <jer...@cs.aukuni.ac.nz> CS Dept, Auckland Univ, NZ |
*---------------------------------------------------------------------*
Lee Hollingworth
>In article <1992Apr20.1...@athena.cs.uga.edu>, how...@castor.cs.uga.edu (Mystery Student) writes:
>>
>> In article <1992Apr20.0...@cs.cornell.edu> res...@cs.cornell.edu (Gene Ressler) writes:
>> >In article <36...@caslon.cs.arizona.edu> da...@cs.arizona.edu (Dave Schaumann) writes:
>> >>In article <1992Apr19....@athena.cs.uga.edu> how...@castor.cs.uga.edu (Mystery Student) writes:
>> >>>I am looking for an algorithm to balance a binary tree. It should take in
>> >>>any binary tree and return one with lg(n) height (with n=number of nodes).
>> >>>Could someone please help me.
>
>> The only thing I came up
>> with was to read the whole tree into an array (or a list) and put the middle
>> element in the root of the tree, and the middle of each remaining half, in
>> the children of the parent, etc... I figured that there must be a better way
>> than this.
>
>There is a better way, as Martin Ehrenstein points out. If you can turn the
>tree into a linked list, then turn the linked list into a balanced tree,
>you're done (because you can then fuse the two parts together to avoid having
>to build the linked list in the first place). There's an obvious way to turn a
>linked list into a balanced tree in O(n log n) time (find the length; build
>trees from the first and from the second halves), but you want it in O(n) time.
Surely the limitations applied to this method when an insertion or deletion
occurs would make this solution unacceptable. As for each insertion, the
whole tree would need to be re-structured as a linked list, then re-structured
as a tree!
The easiest solution I know of is an AVL tree. There are plenty of texts
dealing with the relevant algorithms for insertion and deletion and they are
not difficult to implement.
Lee Hollingworth
s111...@giaeb.cc.monash.edu.au
Rob Allen
>> with was to read the whole tree into an array (or a list) and put the middle
>> element in the root of the tree, and the middle of each remaining half, in
>> the children of the parent, etc... I figured that there must be a better way
>tree into a linked list, then turn the linked list into a balanced tree,
>details are in Bird and Wadler, An Intro to Functional Programming, Prentice
>Hall, section 9.5.
Helman and Veroff: Walls and Mirrors, Chapter 9 of either Pascal or
Modula-2 editions.(Benjamin Cummings)
You don't need the linked list if you have coroutines or concurrent processes:
process 1 recursively traverses the source tree in order,
process 2 recursively builds the new tree.
Effectively nodes are piped from one process to the other. Easy in Ada.
You can fudge this in a non-concurrent language like Pascal by making
process 2 the master (still recursive) and use an iterative traversal
algorithm for process 1 with an explicit stack. The state of the
traversal is represented by the stack. Process 2 simply calls a func
to return the next item; the func manipulates the stack as a side-effect.
Rob Allen, Swinburne I T, Melbourne, Australia
Stuart MacMartin
try using skip lists. There are several articles by Bill Pugh, one in a CACM
which I don't have on me at the moment. The idea is basically each node in
a linked list has a random number of pointers. Level 1 pointers point to
the next element, level 2 pointers point to the next level 2 pointer, etc.
The depth is random so that a deterministic algorithm (such as "delete every
second element") has a low probability of removing all entries with depth > 1.
Pugh, W. Skip lists: A Probabilistic Alternative to Balanced Trees.
WADS 89 proceedings (Workshop on Algorithms and Data Structures)
Pugh, W. Skip lists: A Probabilistic Alternative to Balanced Trees,
Tech Report TR-CS-2190, University of Maryland, College Park, 1989
Pugh, W. Whatever you might want to do using Balanced Trees, you can do it
faster and more simply using Skip Lists
Tech Report CS-TR-2286, University of Maryland, College Park, July 1989
: Stuart MacMartin email: s...@bnr.ca :
: Bell-Northern Research phone: (613) 763-5625 :
: PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA :
Joseph Lavinus
>If you want the behaviour of a balanced tree without the coding problems,
>try using skip lists.
Some papers on Skip Lists are available by anonymous ftp from mimsy.cs.umd.edu.
There is also C code out there for them - I forget whether I saw it at mimsy
or at ftp.uu.net.
Joe
--
___________________________________ /o)\ _____________________________________
Joseph W. Lavinus, Virginia Tech \(o/ email: lav...@cstheory.cs.vt.edu
"How can I do this? I don't know; and because I do not know,
I shall make the attempt." --- e e cummings
Stephen Adams
> ...
>
> Pugh, W. Whatever you might want to do using Balanced Trees, you can do it
^^^^^^^^^^^^^^^
> faster and more simply using Skip Lists
> Tech Report CS-TR-2286, University of Maryland, College Park, July 1989
This clearly is not true. If you permit trees to share
subtrees I then you can perform the following operation in
time O(log n).
create a new tree that looks like the old tree with `x'
inserted (or deleted), without changing the old tree.
With skip lists you would have to copy O(n) of the list.
Disclaimer: I have not read this Tech Report. It is just
that the title is untrue. I quite like skip lists really,
but they do limit your style of programming.
--
Stephen Adams Email: S.R....@ecs.soton.ac.uk
Electronics and Computer Science Tel: 0703 593649
University of Southampton Fax: 0703 593045
Southampton SO9 5NH, UK
James Driscoll
>In article <1992May8.1...@bcrka451.bnr.ca> s...@bcrki65.bnr.ca (Stuart MacMartin) writes:
>
> > ...
> >
> > Pugh, W. Whatever you might want to do using Balanced Trees, you can do it
> ^^^^^^^^^^^^^^^
> > faster and more simply using Skip Lists
> > Tech Report CS-TR-2286, University of Maryland, College Park, July 1989
>
>This clearly is not true. If you permit trees to share
>subtrees I then you can perform the following operation in
>time O(log n).
>
> create a new tree that looks like the old tree with `x'
> inserted (or deleted), without changing the old tree.
>
>With skip lists you would have to copy O(n) of the list.
>
in O(log n) time and space, though a skip list with this property
will require an additional O(n) memory elments. (The implied
constant is small, and there is a time/space trade-off.) See,
for example, Making Data Structures Persistent, Journal of Computer
and Systems Sciences, v 38, 86-124 (1989).
-Jim Driscoll
James Driscoll
>in O(log n) time and space, though a skip list with this property
>will require an additional O(n) memory elments. (The implied
>constant is small, and there is a time/space trade-off.) See,
>for example, Making Data Structures Persistent, Journal of Computer
>and Systems Sciences, v 38, 86-124 (1989).
> -Jim Driscoll
skip list intact. Otherwise the statement is trivial.
Regards,
Jim Driscoll