#data-structures #binary-tree #avl-tree
#структуры данных #двоичное дерево #avl-дерево
Вопрос:
Я знаю, как найти минимальное количество узлов в дереве AVL высотой h (которое включает внешние узлы) с формулой n (h) = n (h-1) n (h-2) 1, но мне было интересно, существует ли формула для простого нахождения минимальноготолько внутренние узлы дерева AVL высотой h.
Итак, для n (3) = 4, если мы считаем только внутренние узлы. n (4) = 7, если мы считаем только внутренние узлы. Я могу извлечь его и посчитать внутренние узлы, но когда вы переходите к большим деревьям AVL, это беспорядок.
Кажется, я ничего не могу найти по этому вопросу, и попытка найти шаблон с последовательными ответами привела только к часам разочарования. Заранее спасибо.
Комментарии:
1. вы хотите найти количество внутренних узлов для полного двоичного дерева? имеет ли значение, является ли дерево AVL или нет? я думаю, что это не так
Ответ №1:
Да, есть хороший способ вычислить это. Давайте начнем с двух простейших деревьев AVL, которые имеют порядок 0 и порядок 1:
* *
|
*
Это первое дерево не имеет внутренних узлов, а второе имеет один внутренний узел. Это дает нам наши базовые примеры для рекуррентного отношения:
- I (0) = 0
- I (1) = 1
Отсюда мы замечаем, что способ получить наименьшее количество внутренних узлов в дереве AVL порядка n 2 — это выбрать два дерева порядка n и n 1 в качестве дочерних (минимизируя количество узлов), которые имеют наименьшее количество возможных внутренних узлов. Результирующее дерево будет иметь количество внутренних узлов, равное количеству внутренних узлов в двух поддеревьях, плюс один для нового корня. Это означает, что
- I(n 2) = I (n) I (n 1) 1.
Применение этого повторения дает нам последовательность
0, 1, 2, 4, 7, 12, 20, и т.д.
И привет — мы где-нибудь видели это раньше? У нас есть! Добавление одного к каждому термину дает нам
1, 2, 3, 5, 8, 13, 21, и т.д.
какая последовательность Фибоначчи сдвинута на две позиции вниз! Итак, наша гипотеза заключается в том, что
I (n) = F (n 2) — 1
Вы можете доказать, что это так, путем индукции по n .
Вот другой способ получить этот результат. Представьте, что вы берете дерево AVL высотой n и удаляете все листья. Теперь у вас осталось дерево AVL высотой n-1 (докажите это!), И все остальные узлы в этом дереве являются внутренними узлами исходного дерева. Наименьшее возможное количество узлов в дереве AVL высотой n равно F(n 2) -1, что соответствует нашему результату.