Балансировка kd-дерева любым существующим алгоритмом
Я пытаюсь реализовать kd-дерево, но у меня проблема с одной операцией - балансировка. Есть ли существующий способ сбалансировать kd-дерево? Например: после вставки нового элемента я хотел бы иметь сбалансированное дерево
2 ответа
Кажется, что обычный подход состоит в том, чтобы собирать новые элементы в списке и время от времени перестраивать дерево со всеми изменениями полностью.
Полностью перебалансировать kd-дерево явно невозможно. Вероятно, есть некоторые компромиссные решения.
Но обычно, если вы хотите сбалансированное дерево, вместо этого вы должны использовать R*-дерево.
После некоторой вставки и удаления вам нужно перестроить KD-дерево, это обычный способ сделать его сбалансированным.
Полностью сбалансированное KD-дерево практически невозможно. Или, может быть, вы можете попробовать KDB-дерево.