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

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

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

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

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

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

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

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

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

Может кто-то пожалуйста, объясните это мне?

3 4
binary-tree binary-search-tree

3 ответа:

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

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

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

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

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

Правка:

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

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

8

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

2

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

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

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

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

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

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

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

0