/red-black-tree-notes

red-black-tree-notes

Свойства:

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

Вставка:

- Если узел уже есть, то не надо вставлять
-Если возможно, окрашиваем узел в красный цвет
2 варианта:
1. Родитель черный, тогда все нормально
2. Родитель красный - нарушается глубина, тк у красного может быть только черный сын

Удаление. 6 + 2 случаев:

1. Удаление красного листа

3. Удаление черного узла с красным потомком.

2. Удаление черного листа

2.1.1.1 Когда родитель красный и имеет еще черного сына с красным сыном
2.1.1.2 Когда родитель красный и имеет еще черного сына без красных потомков

2.2.1.1 Когда родитель черный и имеет еще черного сына с красным сыном
2.2.1.2 Когда родитель черный и имеет еще черного сына без красных потомков

2.2.2.1 Когда родитель черный и имеет еще красного сныа с черным сыном, который имеет красного потомка
2.2.2.2 Когда родитель черный и имеет еще красного сныа с черным сыном, который не имеет красных потомков