Операция удаления в бинарном дереве поиска

Question

Мне нужно жестко закодировать двоичное дерево поиска для класса. Я несколько понимаю метод удаления узла, но получаю смешанную информацию о том, что я заменяю его ...

Мне сказали использовать самый левый узел в правом поддереве ИЛИ самый правый узел в левом поддереве ... Заменить ли наименьший узел в правом поддереве или самый большой узел в левом поддереве?

Имеет ли значение, какой я использую? Должен ли я реализовать оба варианта и поочередно отключить программу от каждого?

Answer 1

Неважно, какой вы реализуете. Замена удаленного узла самым правым узлом левого поддерева или самым левым узлом правого поддерева приведет к созданию правильного двоичного дерева поиска.

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