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