26. Расскажите про красно-черное дерево.

Усовершенствованная версия бинарного дерева.

Каждый узел в к/ч дереве имеет дополнительное поле - цвет. К/ч дерево отвечает следующим требованиям:

1. Узел либо красный, либо черный
2. Корень - черный.
3. Все листья - черные и не хранят данных.
4. Оба потомка каждого красного узла - черные.
5. Любой простой путь от узла-предка до листового узла-потомка содержит одинаковое число черных узлов. Если не одинаковое, то происходит переворот.

При добавлении постоянно увеличивающихся/уменьшающихся чисел в бинарное дерево, оно вырождается в связанный список и теряет свои преимущества. Тогда как к/ч дерево может потребовать до двух поворотов для поддержки сбалансированности, чтобы избежать вырождения.

При операциях удаления в бинарном дереве для удаляемого узла надо найти замену. К/ч дерево сделает тоже самое, но потребует до трёх поворотов для поддержки сбалансированности.
В этом и состоит преимущство.

Сложность поиска, вставки и удаления - O(log(n))

Предыдущий вопрос: 25. Расскажите про бинарное дерево.

Следующий вопрос: 27. Расскажите про линейный и бинарный поиск.

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку: напишите мне