Constructing a weight balanced tree

Hi!

I have some difficult in understanding how to construct a weight balanced tree, given the following data:
``a(100),b(1),c(100),d(1),e(100),f(1),g(100)``
where the numbers represent the probabilities (or accesses).

The algorithm says:
Choose the root so that the maximum of the subtrees is minimal, i.e. minimize max(G(lt(x),G(rt(x)). Then process recursively with the subtrees.

So, I start by this:

a: max(0, 303) -> 303
b: max(100, 302) -> 302
c: max(101, 202) -> 202
d: max(201, 201) -> 201 -> d becomes root
e: max(202, 101) -> 202
f: max(302, 100) -> 302
g: max(303, 0) -> 303

Left Subtree:

a(100), b(1), c(100)

a: max(0, 101) -> 101
b: max(100, 100) -> 100 -> b becomes root
c: max(101, 0) -> 101

Right Subtree:

e(100),f(1),g(100)

e: max(0, 101) -> 101
f: max(100, 100) -> 100 -> f becomes root
g: max(101, 0) -> 101

When I then construct the tree, I get the inverse(!) of a weight-balanced graph!

Greets,

Oliver
• 1. Re: Constructing a weight balanced tree
Oh, okay... got it... the algorithm only constructs NEARLY optimal weight balanced trees...