В этом случае нам надо
В этом случае нам надо добавить дополнительную вершину с префиксом key, дочернюю по отношению к последней вершине пути.
key и rest — суть непустые строки. В этом случае последняя вершина xn разбивается на три: одну с префиксом common, с двумя исходящими из неё — xn, префиксом которой становится rest, и final-вершину с префиксом key.
Основной момент, который связан с разделением на блоки, заключается в том, что в случае 4 и 5 если ветка, в которую мы производим добавление, имеет дочерние ветки, мы создаём новую вершину с key в новой ветке. Для этого мы находим среди дочерних веток ту, на странице которой осталось больше всего места. Это самая дорогая из всех приведённых операций, т.к. требует в худшем случае чтение такого количества страниц, которое равно количеству различных возможных дочерних веток. На практике это неприемлемо. Поэтому в нашей реализации мы ограничеваем количество просматриваемых страниц некоторой константой D (в реализации равна 2). В случае, если среди первых просмотренных D страниц не нашлось той, в которую помещается добавляемая вершина, пытаемся расширить самую занятую из просмотренных. При таком подходе затрагивается не более D+2 страниц.
Содержание Назад Вперед