Премахване на двоично търсене дърво

Ако отстраняването е необходимо да се разгледа три дела [3]:

1. Ако отстранява възел все още няма синове, ще бъдат отстранени, без допълнително регулиране на дървото (фиг. 4.6 (а)).

2. Ако отстранен възел има само едно поддърво, само си дете може да бъде поставена до заеме своето място (фиг. 7.6 (б)).

3. Ако отстранява възел р има две поддървета, той е приемник по симетричен начин (или прекурсор от него по симетричен начин) трябва да заеме своето място. Потомък по симетричен начин не може да се остави под-дърво (като че ли той е напуснал си дете ще бъде р приемник по симетричен начин). Така полето син елемент и може да се премества нагоре, за да заеме мястото на S (фиг. 4.6 (а)).

Фиг. 4.6. Премахване на възли от двоично дърво за търсене

и - премахване с ключ монтаж 15;

б - премахване на 5 блок с ключ;

в - отстраняване монтаж с ключ 11

В следния алгоритъм, дървото остава същата, ако тя не съществува възел с ключ.

// търсене в сайта с ключ. Задайте р така, че да сочи

// в този сайт, както и р - баща му, ако има такъв

докато ((р! = NULL) (Р> к! = Ключ))

ако (ключк) р = р> наляво;

Cout<<”такого ключа нет в дереве. Дерево остается не измененным \n”;

// Задаване на променлива възлова точка V, който замества стр.

// изтриване на възел е с най-много един син

ако (р> наляво == NULL) V = р> полето;

друг (ако р> полето == NULL) V = р> наляво;

друго // р възел има два сина

// Определете приемник на о р по симетричен начин,

// променлива т - бащата на об

S = v-> наляво; // ите - ляв син о

// В този момент, о е приемник на възел стр

// в симетричен начин

// р е бащата на променлива V, U V = трет> наляво.

// Изтриване на възел о от сегашната си позиция и да я замените с възлова точка дясната дете

// създаде синове V, така че те са синове на р

// въведете възел V в положение преди проведе от възел стр

ако (р == NULL) // р възел е в основата на дървото