Изменения

Первая модификация {{---}} занесем все элементы в двусвязный список в порядке, в котором они лежат в боре. Добавим операцию <tex>\mathrm{succOrPred}</tex>, которая возвращает следующий или предыдущий в зависимости от того, что проще. Работает она так: спускается вниз до наибольшего общего префикса, а потом до минимума в правом дереве или же до максимума в левом. Тогда мы получим какой-то элемент списка и не более чем за два шага в списке сможем получить ответ на запрос.

Операции поиска минимума и максимума дорогие, выполним их за <tex>O(1)</tex>. Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершины нет левого сына, отметим это одним битом, а вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации <tex>\mathrm{succOrPred}</tex>. Если нет правого сына, то храним ссылку на максимум в левом поддереве.

При вставке с помощью <tex>\mathrm{succOrPred}</tex> и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины (у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки.