Извлечение элемента из сбалансированного KD-дерева двух измерений

Для стандартного дерева k-d вы можете удалять элементы, но перебалансировки не происходит, поэтому, если вы удалите почти все элементы, у вас может получиться длинное тонкое несбалансированное дерево. Тебя волнует? Дерево на самом деле не становится глубже: оно не сбалансировано, но, поскольку оно было сбалансировано, когда оно было создано, оно никогда не должно быть невероятно глубоким.

Если удаление — это все, что вас волнует, вы можете восстановить дерево с нуля, когда вы удалили половину элементов — это будет означать, что оно никогда не выходит из-под контроля. Кроме того, вы можете пометить элементы как удаленные, а не удалять их, это может упростить некоторые вещи.

Это особый случай создания динамических структур данных или динамизации. За счет фактора log n вы можете сделать структуры данных, которые вы знаете, как перестраивать, но не сбалансировать, динамическими, чтобы справляться как со вставками, так и с удалениями. Основная идея состоит в том, чтобы построить динамическую структуру данных как набор нединамических структур с дико меняющимися размерами, такими как степени двух: большинство изменений приводят к перестройке только одной или двух меньших нединамических структур, но при Для более длительных интервалов вам потребуется время, чтобы восстановить более крупные. Очень свободным примером этого будет хранение ежедневных записей в тетради с вкладными листами и использование их для обновления шкафа для хранения документов в одночасье. Смотри например http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2009/GDS/slides/S12.pdf или же http://www.mpi-inf.mpg.de/~mehlhorn/ftp/mehlhorn27.pdf.