Блог пользователя iLoveIOI

Balanced Binary Search Trees
Автор iLoveIOI, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      5 лет назад, скрыть # ^ |
      ← Rev. 18  
      Проголосовать: нравится +4 Проголосовать: не нравится

      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

      → Ответить