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

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

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

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

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

По этому уравновешивается следующее дерево:

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

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

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

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

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

Есть несколько способов определить «Сбалансированный». Основная цель - сохранить глубины всех узлов 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 (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)      

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

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

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

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

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

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

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

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