"Kovalenko Dmitry" ...
По-разному, вестимо :)
См. BTR_remove_node :-D
Да я рехнуся, если еще и туда полезу :)
Посему ты предлагаешь делать это мне снова и снова :)
Я пока делаю простое дерево в памяти и пытаюсь вникнуть в суть проблемы. tree.h
и еще одной реализации - пока хватает.
Вот и делай - *простое* дерево :)
Понял, что (для параллельной обработки дерева) нужно делать нисходящее
деление/объединение.
Слияние\разделение делается снизу вверх, ибо возникает на листовом уровне
PS Я не понял в чём конкретно твои сомнения...
Ключ первого элемент каждого нода дерева используется на уровне родителя.
Есть такие ключи, которые уходят вверх по дереву. То есть юзаются и у дедушки и
у прадедушки.
Когда грохается элемент с таким ключом, надо бы его везде у предков обновить.
Зачем ? Ключ в предке по-прежнему не больше, чем первый ключ след. уровня
При спуске вниз по дереву такое не сделаешь, потому что вместо этого ключа надо поставить следующий. А следующего мы узнаем только
спустившись до нижних листьев дерева - когда найдем удаляемый элемент.
Вопрос FB - обновляет такие ключи у всех предков или только у непосредственного
родителя?
FB не делает лишней работы, когда её можно не делать. По крайней мере таковы
намерения :) Ключи вверху удаляются если внизу было объединение страниц. Если
это привело к объединению страниц и вверху, то процесс продолжается рекурсивно,
вплоть до корня дерева.
--
Хорсун Влад
