Как пример несбалансированного AVL-дерева из Википедии действительно несбалансирован?

Question

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

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

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

Answer 1

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

• не иметь детей (быть «листовым» узлом)
• Иметь двоих детей.

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

  В опубликованной вами таблице числа 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 2

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

Answer 3

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

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

Answer 4

Другой способ взглянуть на это состоит в том, что высота 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

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