WikiSort.ru - Программирование

Функция Insert

• Вызывает ChooseLeaf, чтобы выбрать лист, куда необходимо добавить элемент. Если вставка выполнена, то дерево могло быть разделено, и разделение могло дойти до вершины. В этом случае ChooseLeaf возвращает две разделенные вершины SplitNodes для вставки в корень
• Вызывает функцию AdjustBounds, которая расширяет ограничивающий прямоугольник корня на вставляемую точку
• Проверяет, если ChooseLeaf вернула ненулевые SplitNodes, то дерево растёт на уровень вверх: с этого момента корнем объявляется вершина, дети которой те самые SplitNodes

Функция ChooseLeaf

• если на входе лист (база рекурсии), то:
  • вызывает функцию DoInsert, которая осуществляет непосредственную вставку элемента в дерево и возвращает два листа, если произошло разделение
  • изменяет ограничивающий прямоугольник вершины с учётом вставленного элемента
  • возвращает SplitNodes, которые нам вернул DoInsert
• если на входе нелистовая вершина:
  • из всех потомков выбирается тот, чьи границы требуют минимального увеличения для вставки данного элемента
  • рекурсивно вызывается ChooseLeaf для выбранного потомка
  • поправляются ограничивающие прямоугольники
  • если splittedNodes от рекурсивного вызова нулевые, то покидаем функцию, иначе:
    • если NumEntries < MaxEntries, то добавляем новую вершину к детям, чистим SplitNodes
    • иначе (когда нет мест для вставки), мы конкатенируем массив детей с новой вершиной и передаём полученное функции LinearSplitNodes или другой функции разделения вершин, и вернём из ChooseLeaf те SplitNodes, которые нам вернула используемая функция разделения.

Функция LinearSplit

Для разделения вершин могут использоваться разные алгоритмы, это один из них. Он имеет всего линейную сложность и просто реализуется, правда выдаёт не самое оптимальное разделение. Однако практика показывает, что такой сложности обычно достаточно.

• по каждой координате для всего набора разделяемых вершин вычисляется разница между максимальной нижней границей прямоугольника по этой координате и минимальной верхней, затем эта величина нормализуется на разницу между максимальной и минимальной координатой точек исходного набора для построения всего дерева
• находится максимум этого нормализованного разброса по всем координатам
• устанавливаем в качестве первых детей для возвращаемых вершин node1 и node2 те вершины из входного списка, на которых достигался максимум, удаляем их из входного списка, корректируем bounds для node1 и node2
• далее, выполняется вставка для оставшихся вершин:
  • если в списке осталось настолько мало вершин, что если их все добавить в одну из выходных вершин, то в ней окажется MinEntries вершин, то в неё добавляется остаток, возврат из функции
  • если в какой-то из вершин уже набран максимум потомков, то остаток добавляется в противоположную, возврат
  • для очередной вершины из списка сравнивается, на сколько надо увеличить ограничивающий прямоугольник при вставке в каждую из двух будущих вершин, где меньше — туда её и вставляется

Функция физической вставки DoInsert

• если в вершине есть свободные места, то точка вставляется туда
• если же мест нет, то дети вершины конкатенируются со вставляемой точкой и вызывается функция LinearSplit или другую функцию разделения, возвращающую две разделённые вершины, которые мы возвращаем из doInsert

Разбиение с помощью алгоритмов кластеризации

Иногда вместо R-дерева используют так называемое cR-дерево (c означает clustered). Основная идея в том, что для разделения вершин или точек используются алгоритмы кластеризации, такие как k-means. Сложность k-means тоже линейная, но он в большинстве случаев даёт лучший результат, чем линейный алгоритм разделения Гуттмана, в отличие от которого он не только минимизирует суммарную площадь огибающих параллелепипедов, но и расстояние между ними и площадь перекрытия. Для кластеризации точек используется выбранная метрика исходного пространства, для кластеризации вершин можно использовать расстояние между центрами их огибающих параллелепипедов или максимальное расстояние между ними.

Алгоритмы кластеризации не учитывают то, что число потомков вершины ограничено сверху и снизу константами алгоритма. Если кластерный сплит выдаёт неприемлемый результат, можно использовать для этого набора классический алгоритм, так как на практике такое происходит не часто.

Интересна идея использовать кластеризацию на несколько кластеров, где несколько может быть больше двух. Однако надо учитывать, что это накладывает определённые ограничения на параметры структуры р-дерева.

Отметим, что помимо cR-дерева существует его вариация clR-дерево, основанное на методе кластеризации, где в качестве центра использован итерационный алгоритм решения «задачи размещения». Алгоритм имеет квадратичную вычислительную сложность, но обеспечивает построение более компактных огибающих параллелепипедов в записях вершин структуры.