бинарное Деревья на основе размера левого и правого поддеревьев ребенка

Question

У меня есть два вопроса:

1. В чем разница между почти сбалансированным BST и почти полное бинарное дерево. Даже если определение первого ясно, то мы можем различаться, но не в состоянии получить соответствующую статью.

2. Сегодня, в моем классе я учил о состоянии быть сбалансирован как:

   макс (размер (root.left), размер (root.right)) < = 3 * п/4 ------------ (eq 1).
   Следовательно, H (n) = высота для дерева из n узлов, следующего за указанным выше свойством < = 1 + H (3 * n/4).
   Продолжая рекурсивные шаги, мы получаем оценку для logn.

   Мой вопрос в том, что это конкретный тип BST? Например, в случае деревьев AVL, поскольку я помню, что условие заключается в том, что разница в высотах левого и правого дочерних элементов, являющаяся крайней точкой 1, или это более общий результат, и уравнение 1, как указано выше, можно уменьшить, чтобы доказать результат для деревьев AVL? то есть любой сбалансированный BST приведет к различию высот братьев и сестер, являющихся предельными 1?
   В случае, если он отличается от AVL, как мы управляем операциями Insertion и Delete в этом новом виде дерева?

EDIT: Также, если вы можете объяснить, почему только 3 * n/4?
Моя мысль: это потому, что мы можем тогда сказать, что H (n) < = 1 + H (3 * n/4), так как если взять что-то вроде 3n/5 меньше 3n/4, то H (3n/5) не обязательно будет меньше, чем H (2n/5), поскольку raio of 3n/5 и 2n/5 меньше 2, и, как известно, коэффициент в 2 для числа узлов увеличивает высоту на 1. Таким образом, мы не будем обязательно напишите H (n) < = 1 + H (3n/5), это может быть H (2n/5) вместо H (3n/5), верно?

Answer 1

1. почти полный BST является BST, где все уровни заполнены, за исключением последнего. Определения здесь перепутаны (некоторые называют это свойство совершенным). Для этого обратитесь к wikipedia.
   Будучи сбалансированным является менее строгим критерием, т. Е. Все (почти) полные BST сбалансированы, но не все сбалансированные BST завершены. В этой статье в Википедии это тоже определение. Im мой мир BST сбалансирован, если он приводит к стоимости операции O (log n).

2. К примеру, можно сказать, A БСТ сбалансирован, если каждое поддерево имеет не более эпсилон * N узлов, где эпсилон < 1 (например, эпсилон = 3/4 или даже эпсилон = 0,999 - которые практически не сбалансирован вообще). Причина в том, что высота такого BST примерно равна log_ {1/epsilon} n = log_2 n/(- log_2 epsilon) = O (log n), но 1/(- log_2 0.99) = 99.5 является огромная константа. Вы можете попытаться доказать это с помощью обычного рациона epsilon = 1/2, где оба поддерева имеют примерно одинаковый размер.

Я не знаю об общем BST, который использует это 3/4.Обычными BST являются, например, Red-Black-Trees, Splay-Trees или - если вы находитесь на жестком диске - целое семейство B-Trees. Для вашего примера вы, вероятно, можете реализовать операции, добавив каждый узел с двумя целыми числами, представляющими число узлов в левом и правом поддеревах соответственно. При вставке или удалении someting вы обновляете числа при прохождении от корня до листа (или вверх), и если условие проверено, вы делаете поворот.