Как определить сбалансированное или идеально сбалансированное двоичное дерево поиска (только по картинке)

Question

Я не уверен, как определить, сбалансировано ли дерево, идеально сбалансировано или нет, если у меня есть это изображение, а не код

Например, если у меня есть это дерево Как я могу проверить, сбалансирован ли он, сбалансирован или неуравновешен? и может ли кто-нибудь дать мне пример идеально сбалансированного дерева?

[o] 
/ \ 
[b] [p] 
    \ /\ 
    [d] [m] [r] 

Очевидно, что я могу сказать, что дерево является несбалансированным, если это было что-то вроде этого:

 [b] 
     \ 
     [d] 
     \ 
      [r] 
      \ 
      [c] 

Однако, если бы это было что-то очень похож на тот, выше я не знаю, как получить это

Это идеально сбалансированный и сбалансированное дерево:

 [k] 
    / \ 
     [A] [p] 
      /\ 
      [N] [R] 

Может кто-то пожалуйста, по электронной xplain это для меня?

Answer 1

Совершенно сбалансированное дерево должно выглядеть следующим образом:

 [ R ] 
    / \ 
    [a]  [b] 
/ \ /\ 
[c] [d] [e] [f] 

Balanced: Вы можете сказать, что сбалансировано, так как высота левого и правого поддеревьев от каждого узла отличаются на 1 или менее (0 в в этом случае),

Perfect: Вы можете сказать, что это прекрасно, потому что число узлов равно 2^(n + 1) -1, где n - высота дерева, в этом случае (2^3) - 1 = 7

В ваших примерах 1-е дерево сбалансировано, но не идеально, второе не сбалансировано и не идеально. Третий сбалансирован, потому что глубина для левого и правого поддерева на каждом узле отличается на 1 или меньше, но она не идеальна, потому что число узлов равно 5, когда оно должно быть 7 согласно идеальному древовидному уравнению.

EDIT:

Что касается вашего длится комментарии, тот факт, что вы получили его на экзамене, не означает, что ответ был прав во всех смыслах. Понятие совершенного дерева связано с понятием полноты, полное дерево иногда называют «идеальным» деревом, а это означает, что число детей для каждого узла, кроме листьев, - это то, что я вам дал, - это уравнение для его вычисления , Третье дерево сбалансировано, потому что важна глубина левого и правого поддеревьев для каждого узла, а не количество детей в левом и правом поддеревах. В этом случае из узла A глубина левого поддерева равна 0, а глубина правого поддерева равна 0 -> 0 - 0 = 0, из P обе глубины составляют 1 -> 1 - 1 = 0, а от корня - глубина от левое поддерево 1, а из правого поддерева 2 -> 2 - 1 = 1 < - оно сбалансировано, так как разница должна быть 1 или меньше.

Надеюсь, это поможет!

Answer 2

Идеально сбалансированная AVL дерево будет иметь разницу в высоте не более 1 между левым поддерево и правое поддерево

Answer 3

Вопрос должен быть о бинарных деревьев (БТС) в целом, а не только бинарные деревья поиска (BST), поскольку порядок данных в узлах не имеет никакого отношения к тому, сбалансировано ли дерево.Одно место для начала - https://en.wikipedia.org/wiki/Binary_tree, но у него есть некоторые проблемы, так как это немного миш-мош различных возможных определений, некоторые из CS и некоторые из теории графов. Вероятно, наиболее полезное, непротиворечивое множество определений:

BT является совершенным или высоты сбалансированного если каждый лист находится на тот же уровень, что эквивалентно каждый путь от данного узла к лист имеет одинаковую длину; это полный, если каждый внутренний (нелистный) узел имеет 2 детей; это полный если он совершенный и полный; это почти завершено или почти завершено если оно совершенное и все уровни, но последние полны, а на последнем уровне листья как можно дальше слева (так что любые «вакансии» находятся справа); это вырожденный, если каждый нелистовой узел имеет только один ребенок (а в виде графика это путь от корня до одного листа).

Используя эти определения: ваше первое дерево совершенные, но не полный, так не полный --node [б] отсутствуют левый ребенок, и добавив, что бы дерево полного; ваше второе дерево вырождено (путь); ваше третье дерево полное (каждый узел, но листья имеют двоих детей) и 1-сбалансированный по высоте, но не «идеально сбалансированный (= идеально?)» или «сбалансированный (что означает« сбалансированный по высоте 0 »)« как вы утверждаете, поскольку не каждый путь от корня до листа имеет одинаковую длину.

В вашем первом дереве, если у [b] было двое детей, но [p] имел только левого ребенка, тогда это было бы почти полностью (идеально и полно, за исключением некоторых пропавших детей на последнем уровне и вакансий как можно правее) - и они важны для хранения двоичных кучек в массивах.

пример Серхио полный (идеальный или сбалансированный по высоте и полный). (И обратите внимание, что это не приятно и может привести к путанице в использовании «сбалансированного», чтобы означать «1-сбалансированное по высоте» или «идеально» как синоним «полного».)

Что-то менее строгое, чем идеальное (или идеально сбалансированный) балансируется по высоте k, что означает, что длины всех путей от данного узла до листа отличаются не более чем на k, что эквивалентно разнице в высоте каждого из левых и правых узлов -подписки не более k. Например, дерево AVL сбалансировано по 1 высоте.

Причина в том, что в этих определениях необходима «высота», заключается в том, что существует другая концепция «weight-balanced BT», которая имеет различные определения в зависимости от использования, причем одно из них означает, что для каждого узла количество узлов в левой части -tree - это то же самое, что и в правом поддереве, а другое заключается в том, что количество узлов в левом поддереве не менее половины и не более чем вдвое больше числа узлов в правом поддереве.