Определение сбалансированного дерева

Мне просто интересно, сможет ли кто-нибудь прояснить для меня определение сбалансированного дерева. У меня есть то, что "дерево сбалансировано, если каждое поддерево сбалансировано, а высота двух поддеревьев отличается не более чем на единицу.

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

Ответ 1

Ограничение обычно применяется рекурсивно к каждому поддереву. То есть дерево только сбалансировано, если:

Высота левого и правого поддеревьев отличается не более чем на один, AND
Левое поддерево сбалансировано, AND
Правильное поддерево сбалансировано

В соответствии с этим следующее дерево сбалансировано:

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G

Следующий не сбалансирован, потому что поддеревья C отличаются на 2 по высоте:

     A
   /   \
  B     C   <-- difference = 2
 /     /
D     E  
     /  
    G

Тем не менее, конкретное ограничение первой точки зависит от типа дерева. Один из перечисленных выше является типичным для деревьев AVL.

Красно-черные деревья, например, накладывают более мягкое ограничение.

Ответ 2

Существует несколько способов определения "Сбалансированный". Основная цель - сохранить глубину всех узлов O(log(n)).

Мне кажется, что состояние баланса, о котором вы говорили, для дерева AVL.
Вот формальное определение состояния баланса AVL дерева:

Для любого node в AVL высота его левого поддерева отличается от не более 1 от высоты его правого поддерева.

Следующий вопрос, что такое высота "?

"Высота" node в двоичном дереве - это длина самого длинного пути от этого node до листа.

Есть один странный, но общий случай:

Люди определяют высоту пустого дерева как (-1).

Например, корневой левый дочерний элемент null:

              A  (Height = 2)
           /     \
(height =-1)       B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1
                    \
                     C (Height = 0)

Еще два примера для определения:

Да, Сбалансированное дерево Пример:

        A (h=3)
     /     \
 B(h=1)     C (h=2)        
/          /   \
D (h=0)  E(h=0)  F (h=1)
               /
              G (h=0)

Нет, Не сбалансированное дерево Пример:

        A (h=3)
     /     \
 B(h=0)     C (h=2)        <-- Unbalanced: 2-0 =2 > 1
           /   \
        E(h=1)  F (h=0)
        /     \
      H (h=0)   G (h=0)

Ответ 3

Нет никакой разницы между этими двумя вещами. Подумайте об этом.

Возьмем более простое определение: "Положительное число даже если оно равно нулю или что число минус два четное". Означает ли это, что 8 даже если 6 четное? Или это говорит, что 8 даже если 6, 4, 2 и 0 равны?

Нет никакой разницы. Если он говорит, что 8 даже если 6 четно, он также говорит, что 6 даже четно четно. И, следовательно, он также говорит, что 4 даже если 2 четный. И, таким образом, он говорит, что 2 даже если 0 четно. Так что, если он говорит, что 8 даже если 6 четное, он (косвенно) говорит, что 8 даже если 6, 4, 2 и 0 четные.

Это то же самое здесь. Любое косвенное поддерево может быть найдено цепочкой прямых поддеревьев. Поэтому, даже если он применяется только к прямым поддеревам, он по-прежнему косвенно относится ко всем поддеревам (и, следовательно, ко всем узлам).

Ответ 4

Сбалансированное дерево - это дерево, высота которого имеет порядок журнала (количество элементов в дереве).

height = O(log(n))
O, as in asymptotic notation i.e. height should have same or lower asymptotic
growth rate than log(n)
n: number of elements in the tree

Определение "дерево сбалансировано для каждого поддерева сбалансировано, а высота двух поддеревьев отличается не более чем одним", за ним следуют деревья AVL.

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

Ответ 5

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

Ответ 6

Высота узла в дереве - это длина самого длинного пути от этого узла вниз до листа, считая начальную и конечную вершины пути.
Узел дерева сбалансирован по высоте, если высота его поддеревьев отличается не более чем на 1.
Дерево сбалансировано по высоте, если все его узлы сбалансированы по высоте.