Не все красные черные деревья сбалансированы?

Question

Интуитивно, «сбалансированные деревья» должны быть деревьями, где левые и правые под деревья в каждом узле должны иметь «приблизительно одинаковое» количество узлов.

Конечно, когда мы говорим о красных черных деревьях*(см. Определение в конце) сбалансировано, мы на самом деле имеем в виду, что они высота Сбалансированные и в этом смысле они сбалансированы.

Предположим, мы пытаемся формализовать вышеуказанную интуицию следующим образом:

Определение: Двоичное дерево называется $ mu $ -бановое, с $ 0 le mu leq frac {1} {2} $, если для каждого узла $ n $, неравенство

$$ mu le frac {| n_l | + 1} {| n | + 1} le 1 - mu $$

удерживает, и для каждого $ mu ' gt mu $ есть какой -то узел, для которого приведенный выше оператор не удается. $ | N_l | $-это количество узлов в левом подрисе $ n $, а $ | n | $-это количество узлов под деревом с $ n $ root (включая корень).

Я считаю, что они называются сбалансированный вес Деревья в некоторых из литературы по этой теме.

Можно показать, что если двоичное дерево с узлами $ n $ имеет $ mu $ -бановое (для постоянной $ mu gt 0 $), то высота дерева равна $ mathcal {o} ( log n ) $, таким образом, поддерживая хорошие поисковые свойства.

Итак, вопрос:

Есть ли немного $ mu gt 0 $, что каждое достаточно большое красное черное дерево было $ mu $ -бано?

---

Определение красных черных деревьев, которые мы используем (от введения в алгоритмы Cormen et al):

Дерево бинарного поиска, где каждый узел окрашен красным или черным и

• Корень черный
• Все нулевые узлы черные
• Если узел красный, то оба его детей черные.
• Для каждого узла все пути от этого узла к потомкам нулевых узлов имеют одинаковое количество черных узлов.

Примечание. Мы не считаем нулевые узлы в определении $ mu $ -бано, выше. (Хотя я считаю, что это не имеет значения, если мы это делаем).

Answer 1

Требовать: Красные черные деревья могут быть произвольно не-$ mu $-балено.

Идея доказательства: Заполните правое поддерево как можно большим количеством узлов, а слева - как можно меньшим количеством узлов для данного числа $ k $ черных узлов на каждом пути корневого листа.

Доказательство: Определите последовательность $ T_k $ красно-черных деревьев, чтобы $ T_k $ имеет $ k $ Черные узлы на каждом пути от корня до любого (виртуального) листа. Определять $ T_k = b (l_k, r_k) $ с

• $ R_k $ Полное дерево высоты $ 2K - 1 $ с первым, третьим, ... окрашенный в уровень красный, остальные черные, и
• $ L_k $ Полное дерево высоты $ k-1 $ со всеми узлами окрашены в черный цвет.

Очевидно, все $ T_k $ красно-черные деревья.

Например, это $ T_1 $, $ T_2 $ а также $ T_3 $, соответственно:

---

^{[источник]}

---

^{[источник]}

---

^{[источник]}

---

Теперь давайте подтвердим визуальное впечатление правой стороны огромный по сравнению с левыми. Я не буду считать виртуальные листья; Они не влияют на результат.

Левый поддерек $ T_k $ Полный и всегда имеет высоту $ k-1 $ и поэтому содержит $ 2^k - 1 $ узлы. Правая поддерево, с другой стороны, завершено и имеет высоту $ 2K - 1 $ и, таким образом, содержит $ 2^{2k} -1 $ узлы. Сейчас $ mu $-баловое значение для корня

$ qquad displaystyle frac {2^k} {2^k + 2^{2k}} = frac {1} {1 + 2^k} underset {k to infty} { to} 0 $

что доказывает, что нет $ mu> 0 $ как просили.

Answer 2

Нет. Рассмотрим красное черное дерево со следующей специальной структурой.

• Левый поддерек - это полное двоичное дерево с глубиной $ d $, в которой каждый узел черный.
• Правая поддерево - это полное двоичное дерево с глубиной $ 2d $, в которой каждый узел на нечетной глубине красный, а каждый узел на глубине - черный.

Ярко проверить, что это действительное красное черное дерево. Но количество узлов в правом подтерее ($ 2^{2d+1} -1 $) примерно площадь из количества узлов в левом подтере ($ 2^{D+1} -1 $).