577
правок
Изменения
→Вставка элемента
Узел, с которым мы работаем, на картинках имеет имя <tex>x</tex>.
=== Вставка элемента ===
Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет <tex>nil</tex>(то есть этот сын {{---}} лист). Вставляем вместо него новый элемент с <tex>nil</tex>-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство <tex>3</tex>, для исправления достаточно рассмотреть только два случая:
1. "Дядя" этого узла тоже красный. Тогда просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" {{---}} в красный. Проверяем, не нарушает ли он теперь балансировку. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет.
