Aqui está um código em C++ para uma Árvore AVL visando fins mais educacionais do que práticos. Apesar da teoria ser muito importante, não adianta nada ler pseudo-algorítmos sem saber como a teoria pode ser, de fato, aplicada. Ainda mais quando a maioria dos livros-texto deixa o método de remoção como exercício. Que mania!
A Árvore apresentada abaixo utiliza apenas uma técnica que pode parecer estranha, a primeira vista, para quem está acostumado a tratar com árvores em algoritmo puro. As subárvores esquerda e direita, presentes em cada nó, estão dispostas em um vetor de dois elementos. Isto traz uma vantagem imensa na hora de rotacionar a árvore, pois corta a necessidade de métodos auxiliares pela metade. Ao invés de termos de implementar rotações à esquerda e depois a direita, por exemplo, aproveitamos um mesmo método para realizar a operação de rotação em ambas as direções.
Fora este recurso adicional, o restante da implementação é bem similar aos textbooks que encontramos por aí. O nó não precisa de uma referência adicional ao seu pai (que é desnecessária, por sinal) e guarda apenas seu fator de balancemento (outras implementações guardam sua altura). O código é orientado a objetos (nada de código C disfarçado), e não está sobrecarregado com templates, embora qualquer um possa modificar o código de forma a suportá-los facilmente.