Блог

Пожалуйста, скажите мне, есть ли какая-либо формула для вычисления минимальных / максимальных красных узлов в красно-черном дереве?

Красно-черные деревья — это бинарные деревья поиска, которые дополнительно ограничены 4 правилами

1. каждый узел либо красный, либо черный
2. корень черный
3. каждый красный узел должен иметь либо 0, либо 2 черных дочерних элемента
4. каждый путь от корня до нуля должен иметь одинаковое количество черных узлов

Минимальное количество красных узлов просто равно 0. Нет требования, заставляющего красно-черное дерево иметь какие-либо красные узлы.

Мы можем получить максимальное количество красных узлов, если мы чередуем красные и черные узлы на каждом пути и делаем количество настоящих красных листьев как можно больше. В этом случае каждый красный узел имеет два дочерних черных узла, а корневой узел должен быть черным. Поэтому => n_black = 2 * n_red 1 Мы также знаем, что n_black n_red = n (n — наше общее количество узлов)

Вот несколько ссылок, если вам нужна дополнительная помощь: http://doctrina.org/maximum-height-of-red-black-tree.html , https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap13b.pdf