Дим, разве по дереву нельзя идти в обратном направлении?
Это просто так вопрос, или я что-то такое сказал, наводящее на эту мысль?
Во-первых, под "обратным" в дереве я понимаю "от листьев к корню". Во-вторых, конечно можно, если каждый дочерний узел хранит ссылку на родителя.
С помощью структуры "сбалансированное бинарное дерево" задача решается при помощи множества структур "Диапазон" и двух деревьев - одно для левых границ диапазона, другое - для правых. Каждый узел каждого дерева ссылается на соответствующий диапазон.
Тогда для [5, 16] нужно:
1) В дереве левых границ найти узел, ближайший и меньший 5 - это 3, и диапазон [3, 8].
2) В дереве правых границ найти узел, ближайший и больший 5 - это 8, и диапазон [3, 8].
3) Если найденные границы указывают на один и тот же диапазон, значит 5 попала в существующий диапазон - запомнить его как крайний левый. Если найденные границы указывают на разные диапазоны, значит 5 попала в "дыру" между существующими диапазонами - тогда от вершины, найденной в 1, нужно перейти к следующей в порядке обхода в глубину (либо это правый сын, либо, если его нет, родитель), и по этой вершине запомнить диапазон как крайний левый. Это [3, 8].
Аналогично с другого конца
4) В дереве левых границ найти узел, ближайший и меньший 16 - это 15.
5) В дереве правых границ найти узел, ближайший и больший 16 - это 20.
6) Если найденные границы указывают на один и тот же диапазон, значит 16 попало в существующий диапазон - запомнить его как крайний правый. Если найденные границы указывают на разные диапазоны, значит 16 попала в "дыру" между существующими диапазонами - тогда от вершины, найденной в 5, нужно перейти к предыдущей в порядке обхода в глубину (либо это левый сын, либо, если его нет, родитель), и по этой вершине запомнить диапазон как крайний правый. Это [11, 15].
7) По дереву левых (правых) вершин найти все диапазоны, у которых левая (правая) граница находится между левыми (правыми) границами найденных диапазонов (включительно). Это [3, 8], [11, 15]. Результатом может быть и пустое множество, если левая граница крайнего левого диапазона окажется больше левой границы крайнего правого диапазона. Тогда новый диапазон целиком умещается в "дыру". Может так быть, что нет крайнего левого или крайнего правого диапазонов - тогда вместо их левых (правых) границ взять, соответственно, наименьшее и наибольшее возможные значения границ для диапазонов.
8 ) Удалить все найденные диапазоны и их границы из деревьев.
9) Добавить новый диапазон [5, 16], добавить 5 в дерево левых границ, добавить 16 в дерево правых границ.
10) Сбалансировать деревья.