Ответ 1
Существует множество алгоритмов для самоустанавливающихся деревьев поиска, многие из которых являются сложными, а другие из них довольно просты (хотя и с некоторыми оговорками).
Книга "Введение в алгоритмы, второе издание" Cormen, Leisserson, Rivest и Stein - отличное введение в алгоритмы и покрытия красные/черные деревья очень хорошо. Это также отличная книга в целом по алгоритмам и структурам данных.
Если вы заинтересованы в использовании splay trees, которые чрезвычайно быстры и на самом деле довольно просты в реализации, оригинальная бумага в структуре данных является очень доступной. Кроме того, он включает в себя доказательство всех границ времени выполнения.
treap - это простое рандомизированное сбалансированное двоичное дерево поиска, которое можно реализовать довольно легко, как только вы знаете, как реализовать вращения дерева. Вращения деревьев также используются в деревьях splay, и поэтому, возможно, стоит изучить.
Для деревьев AVL, эта лекция кажется хороший ресурс.
Надеюсь, это поможет!