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

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

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

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

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

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

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

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

1. Статья дает другое, более общее определение.
2. Другими словами, такое дерево высоты без листьев на уровне k является идеальным деревом высоты k - 1 .$k$$k$$k-1$