Красно-черные деревья - стирание узла с двумя не листовыми детьми

Question

Я реализую свою собственную версию красно-черного дерева, в основном основанную на моих алгоритмах из Википедии (http://en.wikipedia.org/wiki/Red-black_tree).. По большей части она довольно лаконична, но есть одна часть, которую я хотел бы пояснить.

При удалении узла из дерева, у которого есть 2 дочерних элемента (не NULL), он говорит, что нужно переместить дочерние элементы любой стороны в удаляемый узел и удалить этот дочерний элемент.

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

Answer 1

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

Поэтому вы можете просто применить правило, которое подходит вам больше всего (проще всего написать / вычислить - возможно, «всегда выбирайте левое»). Использование случайной схемы обычно просто вводит больше ненужных вычислений.