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

Question

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

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

Answer 1

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

1. Высота левого и правого поддеревьев различается не более чем на единицу, И
2. Левое поддерево сбалансировано, И
3. Правильное поддерево сбалансировано

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

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

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

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

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

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

Answer 2

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

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

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

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

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

Тамодин странный, но распространенный случай:

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

Например, левый дочерний элемент root равен 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Сбалансированное дерево Пример:

        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)      

Answer 3

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

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

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

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

Answer 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 требуют, чтобы все внутренние узлы были сбалансированы.

Answer 5

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

Answer 6

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