Как построить сбалансированное бинарное дерева поиска, в котором данные хранятся в листах?

Question

[borgch]

Пытаюсь построить range tree для некоторого набора n-мерных точек в целях обучения. Для начала - одномерный случай. По книге де Берга, для простоты алгоритма предлагается создать сбалансированное бинарное дерево поиска, причём данные хранятся в листах этого дерева. Не могу придумать, как такое дерево создавать. Картинка.

Comments

[Николай]

Я так понимаю, вам нужно АВЛ-дерево. Алгоритмов довольно много и ничего сложного в них нет. На английской wiki довольно подробно описан алгоритм построения такого дерева (https://en.wikipedia.org/wiki/AVL_tree).

[borgch]

Николай: Получилось так: сначала нужно создать АВЛ-дерево из чисел последовательности, а потом, не балансируя, добавить эти числа ещё раз в дерево, как в дерево поиска. Они как раз станут листами, это нетрудно доказать. Получается сбалансированное дерево, в листах которого заданные числа. Спасибо большое!

Answer 1

[Станислав Макаров]

Если хотите хранить данные только в листах, храните в нелистовых вершинах интервал. Например, в дереве на рисунке вместо нелистовой вершины 37 храните интервал [30, 49]. Подобная идея используется в https://en.wikipedia.org/wiki/R-tree - почитайте про него тоже, если вам нужно для точек. Это как раз дерево для пространственной индексации.

Comments

[borgch]

Спасибо. Но уже начал разбираться с range tree, надо "добить" :)