Какова минимальная / максимальная глубина бинарного дерева с n листовыми узлами? - PullRequest
Новая
       35

Какова минимальная / максимальная глубина бинарного дерева с n листовыми узлами?

0 голосов
/ 12 января 2019

Я знаю, что максимальная глубина бинарного дерева с n узлами равна n-1

Я знаю, что максимальная глубина бинарного дерева с n узлами равна floor(log2n)

Но что, если мне просто дается число листовых узлов ?

1 Ответ

0 голосов
/ 12 января 2019

В двоичных деревьях есть два идеала.

Идеальное "самое глубокое" дерево. 

 *
  *
   *
    *
     a

Это дерево, очевидно, содержит один листовой узел и может иметь бесконечное количество промежуточных узлов. Это означает, что максимальная глубина не ограничена для одного конечного узла (если ваша задача не требует внутренних узлов с более чем одним дочерним узлом)

Идеальное "самое мелкое" дерево 

          *
      *       *
    *   *   *   *
   a a a a a a a a

Это дерево, очевидно, содержит 2^(depth-1) листьев (для деревьев глубиной 1 или больше), и благодаря магии математики будет иметь глубину log(base2)(leaves) = depth-1 или 1+log(base2)(leaves). Поскольку у нас не может быть дробной глубины, это должно быть выровнено по ceil(1+log(base2)(leaves))

Чтобы проверить это, давайте создадим таблицу 

leaves formula                        depth
  1    ceil(1+log(base2)(1)) => ceil(1+0) => ceil(1) => 1
  2    ceil(1+log(base2)(2)) => ceil(1+1) => ceil(2) => 2
  3    ceil(1+log(base2)(3)) => ceil(1+1.58) => ceil(2.58) => 3
  4    ceil(1+log(base2)(4)) => ceil(1+2) => ceil(3) => 3
  5    ceil(1+log(base2)(5)) => ceil(1+2.32) => ceil(3.32) => 4

и т. Д.

Таким образом, диапазон глубины для дерева с n узлами (где n> 0) равен 

[ceil(1+log(base2)(n)), infinity)

, если нет более строгих ограничений на самое глубокое дерево, типа "каждый внутренний узел должен иметь двух братьев и сестер (или что-то в этом роде)"

...