Сбалансированная глубина бинарных деревьев - PullRequest
Новая
       31

Сбалансированная глубина бинарных деревьев

0 голосов
/ 23 марта 2012

Когда задано количество узлов, мы можем вычислить минимальную глубину двоичного дерева, выполнив log2 (n)

, где n - количество узлов.

Если вы рисуетедерево для максимальной глубины, например, для 12 узлов вы работаете, что максимальная глубина может быть только 4, если дерево должно оставаться сбалансированным. 

                0
               /   \
              0     0
            /  \   / \
           0    0 0   0
          /\     \     \ 
        0   0      0    0

Извините за плохой ascii art.Кто-нибудь знает форум, который может рассчитать максимальную глубину бинарного дерева при заданном количестве узлов?Или, по крайней мере, указать мне правильное направление?

Ответы [ 3 ]

2 голосов
/ 13 июля 2013

Самый простой ответ выглядит так: 

int getMaxDepth(Node node)
{
    if(node == null) {
        return 0;
    }

    int leftDepth = 1 + getMaxDepth(node.left);
    int rightDepth = 1 + getMaxDepth(node.right);

    return left > right ? left : right;
}

Понятие объяснено

2 голосов
/ 23 марта 2012

Используя корневой элемент: 

int maxHeight(BinaryTree *p) {
  if (!p) return 0;
  int left_height = maxHeight(p->left);
  int right_height = maxHeight(p->right);
  return (left_height > right_height) ? left_height + 1 : right_height + 1;
}

Используя количество узлов и некоторую математическую логику (которую я точно не могу выразить правильно(Я ни в коем случае не математический гуру); но вот оно):

Наблюдение:

  • 2-3 узла => maxDepth = 1(2 = 2 ^ 1, 3 = 2 ^ 1, .. <2 ^ 2) </li>
  • 4-7 узлов => maxDepth = 2 (4 = 2 ^ 2, 5 = 2 ^ 2, .., 6 = 2 ^ 2, .., 7 = 2 ^ 2, ... <2 ^ 3) </li>
  • 8-15 узлов => maxDepth = 3
  • ...

Анализ:

  • m => max Depth (фактическая часть глубины INT, отбрасывать все десятичные разряды)

  • n => количество узлов

  • ln => натуральный логарифм (= log [e])

  • 2 ^ m = n

  • ln (2 ^ m) = ln (n)

  • m * ln (2) =ln (n)
  • m = ln (n) / ln (2)

Вывод:

Теперь, если m = 2, ..., тогда максимальная глубина равна 2. Просто получитеInt часть этого.; -)

ПРИМЕЧАНИЕ: Я определенно заново изобретаю колесо;но это, вероятно, часть удовольствия иметь дело с тем, о чем вы ничего не знаете;и делать это, исключительно следуя своему инстинкту и наблюдениям ...: -)

1 голос
/ 26 апреля 2013

Позвольте ни одному из заданных узлов (n) = 15 Формула islog2n (log n base 2) теперь принимает максимальное значение, которое должно быть меньше 15 и должно быть степенным результатом 2. Так как здесь 15 дается нетбудет 8. Теперь n = 8 log2 (8) = 3, что является нашим обязательным ответом

...