iLoveIOI's blog

Balanced Binary Search Trees
By iLoveIOI, history, 4 years ago, In English

How do you count the number of balanced binary search trees with N nodes? Balanced as in the left subtree size and the right subtree size differ by at most 1.

Thanks!

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If I am not wrong, then this number series might help — It is the number of possible balanced binary search tree with $$$N$$$ unique nodes

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I don't think that is correct. 4 nodes has 4 trees N<=1e18 by the way

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 18   Vote: I like it +4 Vote: I do not like it

      I think your mean was to deal with the problem of counting such balanced tree with exact $$$N$$$ nodes

      Lets take a subtree $$$G_0$$$ with $$$N$$$ nodes, including root. Since the subtree construction depend on left and right subsubtree, we have:

      • Excluding root, if $$$N - 1$$$ is even then each subsubtree will have $$$K = \frac{N - 1}{2}$$$ nodes
      • Excluding root, if $$$N - 1$$$ is odd then one subtree will have $$$K_1 = \frac{N - 1}{2}$$$ nodes and other will have $$$K_2 = N - K_1$$$

      Lets $$$f(x) = $$$ numbers of balanced tree with $$$N$$$ nodes, from above observation, we have

      • When $$$N - 1$$$ is even $$$f(N) = f(K)^2$$$
      • When $$$N - 1$$$ is odd $$$f(N) = 2 \times f(K_1) \times f(K_2)$$$
      Example
      f(0) -> f(100)
      Series
      Generator

      Since every value is the power of 2, we also have this generator for a funny graph

      Generator
      Graph - 256

      It is A110316 OEIS

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow! Thanks! That helped a lot!

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          Then give me contribution UwU

          Just kidding, by the way, since there is $$$O(log_2(n))$$$ solution by matrix multiplication and $$$O(log_2^2(n))$$$ solutions by recursive-dp, do you think there is an $$$O(1)$$$ solution by combinatoric or something ?

          → Reply