Дерево Kd: данные хранятся только в листьях, а не в листьях и узлах

Вы можете просто пометить узлы как удаленные, и отложить любые структурные изменения до следующей перестройки дерева. Со временем k-d-деревья ухудшаются, поэтому вам придется часто перестраивать деревья. k-d-деревья отлично подходят для низкоразмерных наборов данных, которые не меняются, или где вы можете легко позволить себе построить (приблизительно) оптимальное дерево.

Что касается реализации дерева, я рекомендую использовать минималистичную структуру. Я обычно делаю не использовать узлы. Я использую массив ссылок на объекты данных. Ось определяется текущей глубиной поиска, нет необходимости хранить ее где-либо. Левые и правые соседи задаются двоичным деревом поиска массива. (В противном случае просто добавьте массив byteполовину размера вашего набора данных, для хранения осей, которые вы использовали). Загрузка дерева осуществляется специализированной быстрой сортировкой. По идее это O(n^2) наихудший случай, но с хорошей эвристикой, такой как Median-of-5, вы можете получить O(n log n) достаточно надежно и с минимальными постоянными накладными расходами.

Хотя для C / C ++ это не так уж и много, во многих других языках вы заплатите немалую цену за управление многими объектами. type*[] это самая дешевая структура данных, которую вы найдете, и, в частности, она не требует больших управленческих усилий. Чтобы пометить элемент как удаленный, вы можете null и искать обе стороны, когда вы сталкиваетесь с null, Для вставок я бы сначала собрал их в буфер. И когда счетчик изменений достигнет порогового значения, перестройте.

И в этом весь смысл: если ваше дерево действительно дешево перестраивать (столь же дешево, как использование почти предварительно отсортированного массива!), То это не повредит частой перестройке дерева.
Линейное сканирование по короткому «списку вставок» очень удобно для кэша ЦП. Пропуская nullс тоже очень дешево.

Если вы хотите более динамичную структуру, я рекомендую взглянуть на R * -деревья. Они на самом деле предназначены для балансировки на вставках и удалениях и организации данных в диско-ориентированную блочную структуру. Но даже для R-деревьев были сообщения о том, что сохранение буфера вставки и т. Д. Для отсрочки структурных изменений повышает производительность. А массовая загрузка во многих ситуациях тоже очень помогает!