Два определения сбалансированных бинарных деревьев

26

Я видел два определения сбалансированных бинарных деревьев, которые выглядят по-другому для меня.

  1. Бинарное дерево сбалансировано, если для каждого узла установлено, что количество внутренних узлов в левом поддереве и количество внутренних узлов в правом поддереве отличаются не более чем на 1.

  2. Бинарное дерево сбалансировано, если для любых двух листьев разница глубины составляет не более 1.

Делает ли каждое дерево, которое удовлетворяет def. 1 также удовлетворяет деф. 2? А как насчет наоборот?

Форрест Гамп
источник
2
Вы пытались доказать любое направление? Каковы ваши выводы?
Рафаэль

Ответы:

17

Определение 1. также известно как сбалансированность по весу ¹ и определение 2. как сбалансированность по росту .

Сбалансированность по высоте не означает сбалансированность по весу; Примерами являются AVL- и Red-Black-Trees. Смотрите здесь и здесь для доказательства, соответственно.

Однако сбалансированность по весу подразумевает сбалансированность по высоте. Это можно доказать, продемонстрировав следующий более сильный факт по индукции (по росту): сбалансированное по весу дерево завершено на всех уровнях, кроме самого глубокого². Существенным аргументом в индуктивном шаге является то, что у поддеревьев не может быть разницы в росте больше, чем один, потому что - оба обладают заявленным свойством по предположению индукции - тогда они не будут сбалансированы по весу.


  1. Статья дает другое, более общее определение.
  2. Другими словами, такое дерево высоты без листьев на уровне k является идеальным деревом высоты k - 1 .kkk1
Рафаэль
источник
Я только что понял, что более сильный факт можно использовать, чтобы просто упростить доказательства, на которые я ссылаюсь.
Рафаэль
Возможно, это хорошая идея, чтобы включить эту реализацию в ваш ответ.
Дискретная ящерица
@Discretelizard Вы имеете в виду, другие ответы?
Рафаэль
О, я не осознавал, что эти ссылки были ответами по информатике или что они были вашими ответами. Ну, в любом случае, все, что я хотел сказать, это то, что было бы хорошей идеей записать упрощенные доказательства. Ваши связанные ответы тогда кажутся подходящим местом.
Дискретная ящерица