Алгоритм на псевдокоде

RL - поворот

q := p→ Right, r := q→ Left

IF (r→Balance>0) p→Balance := -1 ELSE p→Balance := 0 FI

IF (r→Balance<0) q→Balance := 1 ELSE q→Balance := 0 FI

r→Balance := 0

p→ Right:= r→ Left, q→ Left:= r→ Right

r→ Left := p, r→Right := q, p := r

12.3 Добавление вершины в дерево

Добавление новой вершины в АВЛ-дерево происходит следующим образом. Вначале добавим новую вершину в дерево так же как в случайное дерево поиска (проход по пути поиска до нужного места). Затем, двигаясь назад по пути поиска от новой вершины к корню дерева, будем искать вершину, в которой нарушился баланс (т. е. высоты левого и правого поддеревьев стали отличаться более чем на 1). Если такая вершина найдена, то изменим структуру дерева для восстановления баланса с помощью процедур поворотов.