Процедура удаления дерева двоичного поиска с детьми

Question

Не знаю, как сформулировать этот вопрос. В основном принимает следующий BST:

 25 
    / \ 
    20  30 
/\ /\ 
18 23 27 31 
/\ /\ 
8 19 22 24 

Если бы я удалить значение 25 и вращать значение 20 в своем месте, он делает больше смысла для добавления 23 поддерева до 27, или для добавления 30 поддерева к 24. И я не имею в виду конкретное дело, но с более широкой точки зрения.

Просто чтобы быть ясно, что предпочтительнее между этими двумя аранжировок:

 20 
    / \ 
    18  23 
/\ /\ 
8 19 22 24 
       \ 
       30 
       /\ 
       27 31 

     20 
    / \ 
    18  30 
/\ /\ 
8 19 27 31 
     /
     23 
    /\ 
    22 24 

Answer 1

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

Если вы хотите повернуть свой путь, нет никакой разницы между высотами древовидного дерева, и оба они будут одинаковыми с точки зрения сложности времени.