Одним китайским студентом был предложен вариант реализации само-балансирующегося дерева, с использованием только одного дополнительного поля – размер ветки.

Эта реализация идеально подошла для моего проекта. Так как мне очень важно чтобы использовались ровно 3 поля/свойства/значения на каждый элемент помимо самих данных, а именно:

1. Указатель на левую ветку. – Left
2. Указатель на правую ветку. – Right
3. Размер дерева (или текущей ветки). – Size

Эту структуру данных (3 поля) изменять нельзя.

Что хорошо:
1. Алгоритм действительно держит дерево в сбалансированном состоянии.
2. Балансировка происходит достаточно быстро.

Что хотелось бы:
Так как в моём проекте нагрузка на эту структуру максимальная. В перспективе это миллионы и миллиарды вставок и удалений.
Я хотел бы попросить экспертов проанализировать алгоритм балансировки и постараться его максимально ускорить. Возможно даже использовать, если возможно, помощь процессора, т.е. напрямую использовать инструкции архитектур Intel x86 и x86–64.
Как мне кажется первым шагом могла бы стать реализация балансировки не только при добавлении, но и при удалении (у меня не получилось сделать реализацию балансировки при удалении в своё время, и для простоты я решил её опустить – сейчас удаление технически разрушает балансировку).
Также явно в алгоритме есть простор для оптимизации – сейчас балансировка начинается как отдельный процесс, происходящий когда добавление было закончено полностью. Возможно это не совсем эффективно, ведь можно балансировку выполнять по ходу добавления, т.е. одновременно.
Эта проблема – балансировка после добавления в данный момент оправдана только тем, что балансировки при удалении вообще не происходит, и соответственно баланс будет восстановлен только после первого добавления следующим за серией удалений из дерева.

Прикрепляю два файла (исходное описание алгоритма его автором Chen Qifeng на английском).
Моя реализация основных методов алгоритма на макросах (си).

На выходе мне требуется проект-пример с исходным кодом, который можно скомпилировать как под Linux (gcc) так и под Windows (Visual C++ 2008–2010). Если оптимизацию можно будет выполнить с помощью ассемблера – желательно чтобы в файлах .asm были комментарии к каждой строчке (так как мои знания в асм-крайне поверхностные).
С++ вряд ли здесь пригодится, желательно использовать только чистый си (при необходимости сопровождать комментариями).
Также было бы замечательно получить описание выполненных оптимизаций, или если при оптимизации пришлось полностью переписать алгоритм, то описание работы нового алгоритма.
Обязательно добавить сравнение производительности операций добавления и удаления текущей реализации и оптимизированной.

По алгоритму:
- В новой реализации дерево должно оставаться идеально сбалансированным после каждой операции добавления/удаления.
- Либо балансировка должна происходить при удалении и добавлении не всегда, но так чтобы это не существенно влияло на производительность поиска по дереву.