1 Reply Latest reply: Aug 7, 2009 1:32 PM by 843853 RSS

    Constructing a weight balanced tree

    843853
      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