Строительство хвойного дерева
Давайте рассмотрим следующую картину
это так называемое дерево диапазонов. Я не понимаю одну вещь, это похоже на двоичное дерево поиска, поэтому, если мы вставляем элементы, мы можем использовать ту же процедуру, что и при вставке двоичного дерева поиска. Так в чем же разница?
Я прочитал учебник и думаю, что это вариация деревьев kd, деревьев запросов (например, поиск геометрических точек и т. Д.), Но как его построить? Как бинарное дерево поиска или ему нужны дополнительные параметры? Может так
struct range
{
int lowerbound;
int upperbound,
int element;
};
и во время вставки мы должны проверить
if(element>lowerbound && element <upperbound)
then insert node
Пожалуйста, помогите мне правильно понять, как построить дерево диапазона.
Решение
В бинарном дереве поиска при вставке значения вы вставляете новый узел.
Дерево поиска диапазона больше похоже на дерево двоичного индекса. Эти две структуры данных имеют фиксированные структуры. Когда вы добавляете / вычитаете точку в заданном диапазоне, вы обновляете значения в узлах, но не вводите новые узлы.
Конструкция этой структуры очень похожа на KD-дерево: исходя из заданных точек вы выбираете наиболее подходящие точки расщепления.
Когда вы изучаете новую структуру данных, всегда учитывайте поддерживаемые операции — это поможет вам быстрее понять структуру. В вашем случае это помогло бы вам различить двоичное дерево поиска и дерево диапазона.
Другие решения
Других решений пока нет …