хочу уточнить свой первый пост: в очень неудачных случаях «всё сортировано» высота иногда будет больше, чем log(N), потенциально до 2*log(N). это всё ещё лучше, чем N для простых бинарных. и при активном добавлении элементов дерево быстро «уплощается» обратно до примерно 1.5*log(N). плата за простоту реализации.

p.s.: и да, если добавить в ноды parent (указатель на ноду-родителя), то можно вообще без рекурсии обойтись. код, правда, усложнится рихтовкой парентов и взбиранием обратно по ним. вот это вы все точно напишете сами, если захотите: алгоритм тот же самый, что и у рекурсии, только чуть более грязный. хотя я, признаться, не вижу особого смысла заморачиваться: ну, максимальная глубина рекурсии в районе 64 вызовов для дерева с 2^32 элементов. кого реально это парит?

впрочем, удобство parent в том, что можно делать обход дерева в любом направлении за O(1) без дополнительного стека. опять же, это есть в любом учебнике по структурам данных.

позже причешу и выложу реализацию ranges на этой штуке. фактически, это массивы с амортизированым временем O(log N) на добавление, удаление и поиск. то, на чём я хочу переписать TextModels. если хотите хинт, то: в ноде надо хранить размер левого поддерева, и рихтовать его в процессе балансировки. можно делать как классические массивы, так и массивы, где одна нода покрывает больше одного элемента (удобно для хранения attribute runs в редакторе, например). а классические, например, использовать для хранения начальных позиций строк — за счёт быстрой вставки и удаления, а также O(1) перебора это получается шустро и сердито.