Анализ дерева AVL

Question

Я читаю AVL tres в разделе Структуры данных и анализ Вайса

Одно из условий баланса настаивает на том, что у каждого узла должны быть левое и правое поддеревья одинаковой высоты.Если высота пустого поддерева определена равной -1 (как обычно), то этому критерию будут удовлетворять только идеально сбалансированные деревья ((от 2 до степени k) - 1) узлов.Таким образом, хотя это гарантирует деревья малой глубины, условие баланса слишком жесткое, чтобы быть полезным, и его нужно ослабить.

Запросите помощь в понимании вышеприведенного текста, приведя пример 1. Например, как пришел авторс ((от 2 до степени k) - 1) узлы будут удовлетворять этому критерию?2. Что означает утверждение «хотя это гарантирует деревья малой глубины, условие равновесия слишком жесткое, чтобы быть полезным, и его нужно ослабить»?

Спасибо!

Answer 1

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

1: *

3: *
  / \
 *   *

7:  *
   / \
  *   *
 / \ / \
 * * * *

и т. Д.

Математически это означает, что количество узлов в дереве равно 2 ^k -1,где k - целое число.

«Малая глубина» означает, что деревья этой формы имеют максимально возможное количество узлов для их заданной глубины: добавление еще одного узла должно увеличить глубину.