Посему ты предлагаешь делать это мне снова и снова :)
Ja Ja
Я пока делаю простое дерево в памяти и пытаюсь вникнуть в суть проблемы.
tree.h и еще одной реализации - пока хватает.
Вот и делай - *простое* дерево :)
Ну да. А *ето* как же?
Понял, что (для параллельной обработки дерева) нужно делать нисходящее
деление/объединение.
Слияние\разделение делается снизу вверх, ибо возникает на листовом
уровне
Вот ведь, а как же
"Сверху-вниз и слева-направо :)"
--
Я без проблем сделал добавление делением сверху. Обратного движения нету.
Минусы - лишняя работа в случае добавления дубля. И жопа в случае
внутреннего нода с емкостью равной двум. Дерево может начать бесконечно
расти. Но это экстремальный размер нода.
С удалением, тоже вроде должно получится.... то есть балансировка дерева
будет соблюдена.
Будем считать, что это оптимистическая реализация - когда мало конфликтов
при встаке и мало холостых удалений.
Зачем ? Ключ в предке по-прежнему не больше, чем первый ключ след.
уровня
Вот это мне и было интересно. Я тоже об этом подумал, но меня терзают
сомнения, что такое хамское удаление будет создавать мертвые зоны в дереве
... То есть ноды в которые больше никогда не будут добавлять новые элементы.
Коваленко Дмитрий.
