Красно-черные деревья - Стирание узла с двумя нелистовыми детьми
Я реализовывал свою собственную версию красно-черного дерева, главным образом основывая мои алгоритмы из Википедии (http://en.wikipedia.org/wiki/Red-black_tree). Его довольно краткое по большей части, но существует одна часть, по поводу которой я хотел бы разъяснение.
При стирании узла из дерева, которое имеет 2 нелиста (непустой указатель) дети, он говорит, чтобы переместить детей любой стороны в удаляемый узел и удалить того ребенка.
Я немного смущен относительно который сторона удалить из, на основе этого. Я выбираю сторону случайным образом, я чередуюсь между сторонами, или я придерживаюсь той же стороны для каждого будущего удаления?
1 ответ
Если у вас нет предварительных знаний о ваших входных данных, вы не можете знать, какая сторона более выгодна: новый промежуточный узел или новый дочерний узел.
Поэтому вы можете просто применить правило, которое вам больше всего подходит (проще всего написать / вычислить - вероятно, «всегда выбирайте левое»). Использование случайной схемы обычно просто вводит больше ненужных вычислений.