Как пример несбалансированного дерева AVL в Википедии?

Question

Изображение выше взято из "Запись Википедии о деревьях AVL" , которая, как указывает Википедия, не сбалансирована. Как это дерево уже не сбалансировано? Вот цитата из статьи:

Коэффициент баланса узла - это высота его правого поддерева минус высота его левого поддерева, а узел с коэффициентом баланса 1, 0 или -1 считается сбалансированным. Узел с любым другим фактором баланса считается несбалансированным и требует перебалансировки дерева. Коэффициент баланса либо сохраняется непосредственно в каждом узле, либо вычисляется по высоте поддеревьев.

Высота левого и правого поддеревьев равна 4. Высота правого поддерева левого дерева равна 3, что всего на 1 меньше 4. Может кто-нибудь объяснить, что мне не хватает?

Answer 1

Узел 76 не сбалансирован, например, потому что его правое поддерево имеет высоту 0, а левое имеет высоту 3.

Answer 2

Чтобы быть сбалансированным, каждый узел в дереве должен либо

• не имеет детей (быть "листовым" узлом)
• Двое детей.

• Или, если у него только один ребенок, этот ребенок должен быть листом.

  На графике, который вы разместили, 9, 54 и 76 нарушают последнее правило.

Правильно сбалансированное дерево будет выглядеть так:

Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76

ОБНОВЛЕНИЕ: (спустя почти 9 лет я создал крутой онлайн-график для графика на draw.io )

Answer 3

Еще один способ взглянуть на это состоит в том, что высота h любого узла определяется как:

h = 1 + max( left.height, right.height )

и узел неуравновешен всякий раз, когда:

abs( left.height - right.height ) > 1

Глядя на дерево выше:

- Node 12 is a leaf node so its height = 1+max(0,0) = 1
- Node 14 has one child (12, on the left), so its height is = 1+max(1,0) = 2
- Node 9 has one child (14, on the right), so its height is = 1+max(0,2) = 3

Чтобы определить, является ли узел 9 сбалансированным или нет, мы смотрим на высоту его дочерних элементов:

- 9's left child is NULL, so 9.left.height = 0
- 9's right child (14) has height 2, so 9.right.height = 2

Теперь решите, чтобы показать, что узел 9 не сбалансирован:

9.unbalanced = abs( 9.left.height - 9.right.height ) > 1
9.unbalanced = abs( 0 - 2 ) > 1
9.unbalanced = abs( -2 ) > 1
9.unbalanced = 2 > 1
9.unbalanced = true

Аналогичные вычисления могут быть сделаны для каждого другого узла.

Answer 4

Интуитивно, это потому, что он не настолько мал, насколько это возможно. например, 12 должно быть родительским для 9 и 14. Как таковое, у 9 нет левого поддерева, поэтому он не сбалансирован. Дерево - это иерархическая структура данных, поэтому правило типа «сбалансированный» часто применяется к каждому узлу, а не только к корневому узлу.

Вы правы, корневой узел сбалансирован, но не все узлы дерева.