120
правок
Изменения
м
# * Узел <tex>y</tex> не помечен, тогда помещаем поддерево с корнем в самом левом сыне узла <tex>y</tex> на место пропущенного в братском списке. Узел <tex>y</tex> становится помеченным, дерево становится корректным, процедура исправления завершается.# * Узел <tex>y</tex> помечен, тогда уменьшаем ранг узла <tex>y</tex> на единицу. Теперь узлом локализации нарушения будет либо левый брат узла <tex>y</tex>, либо его родитель, тогда нарушение станет родительским.
Нет описания правки
Пусть узел <tex>y</tex> — это узел локализации братского нарушения.
С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.
Пусть узел <tex>y</tex> — это узел локализации родительского нарушения, а узел <tex>z</tex> — родитель узла <tex>y</tex>.
Переместим все поддерево с корнем в <tex>y</tex> в корневой список и уменьшим ранг <tex>y</tex>. Если узел * Узел <tex>z</tex> не был помечен, то пометим его, тогда дерево станет корректным.* Узел <tex>z</tex> был помечен, иначе тогда <tex>z</tex> {{---}} новый узел локализации родительского нарушения, переходим к нему.
Продолжая эту процедуру, мы или остановимся, или дойдем до корня дерева, тогда достаточно сделать ранг корня на 1 больше ранга его самого левого сына.
