Будучи студентом, я пытался сам реализовать дерево B+ на C. Вставка в порядке, но удаление меня сдерживает. Один из моих вопросов таков: можно ли оставаться ключом во внутреннем узле, когда его ключ в листовом узле был удален? Это может произойти, когда внутренний узел не является родителем листа. Достаточно ли понятно мое описание? Есть ли у кого-нибудь подобный опыт?
удаление на B+ дереве
comment
Вы хотите ответ да или нет? Это домашнее задание?
- person Gigamegs schedule 09.07.2011
comment
Можно ли оставаться ключом... Ты имеешь в виду оставить ключ...? Эта фраза сбила меня с толку.
- person Joey Adams schedule 09.07.2011
Ответы (1)
Вопрос, который вы должны задать себе при работе со структурой данных: «Что такое инварианты?» Для дерева B+ некоторые из инвариантов таковы:
- Записи хранятся в листовых узлах,
- Листовые узлы должны быть заполнены как минимум наполовину.
Поэтому, если вы решите, что деревья B+ позволяют хранить ключи, которые больше не соответствуют записям, это нормально. Просто убедитесь, что ваши алгоритмы вставки и поиска по-прежнему работают с вашим конкретным набором инвариантов.
В общем, довольно странно встретить в каком-либо дереве ключ, который не соответствует ни одной из записей. Я также ожидаю, что стоимость исправления этого в дереве B+ с большим разветвлением будет довольно небольшой.
person
Dietrich Epp
schedule
09.07.2011
