Estoy buscando la mejor manera de calcular el saldo de un nodo en una AVL-tree. Pensé que lo tenía funcionando, pero después de una fuerte inserción / actualización puedo ver que no funciona correctamente (en absoluto).

Esta es una pregunta de dos partes, la primera parte sería cómo calcular la altura de un subárbol, conozco la definición "La altura de un nodo es la longitud del camino descendente más largo hacia una hoja desde ese nodo". y lo entiendo, pero no puedo implementarlo. Y para confundirme más, esta cita se puede encontrar en wikipedia en tree-heights "Convencionalmente, el valor -1 corresponde a un subárbol sin nodos, mientras que cero corresponde a un subárbol con un nodo".

Y la segunda parte es obtener el factor de equilibrio de un subárbol en un árbol AVL, no tengo ningún problema para entender el concepto, "obtén la altura de tuL yR subárboles y restarR desdeL". Y esto se define como algo así:BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

Reading en wikipedia dice esto en las primeras líneas que describen las inserciones en un árbol AVL: "Si el factor de equilibrio se convierte en -1, 0 o 1, el árbol todavía está en forma AVL y no se necesitan rotaciones".

uego continúa diciendo que "Si el factor de equilibrio se convierte en 2 o -2, entonces el árbol enraizado en este nodo está desequilibrado y se necesita una rotación de árbol. Como máximo, se necesitará una rotación simple o doble para equilibrar el árbol". - que no tengo problemas para comprender.

Pero (sí, siempre hay un pero).

Aquí es donde se vuelve confuso, el texto dice "Si el factor de equilibrio de R es 1, significa que la inserción se produjo en el lado derecho (externo) de ese nodo y se necesita una rotación hacia la izquierda". Pero desde mi comprensión, el texto decía (como cité) que si el factor de equilibrio estaba dentro de[-1, 1] entonces no hubo necesidad de equilibrar?

Siento que estoy tan cerca de comprender el concepto, he conseguido reducir las rotaciones de los árboles, he implementado un árbol de búsqueda binario normal y estoy a punto de comprender los árboles AVL, pero parece que me falta esa epifanía esencial.

Editar Los ejemplos de código son preferibles a las fórmulas académicas, ya que siempre me ha sido más fácil comprender algo en el código, pero cualquier ayuda es muy apreciada.

Editar Desearía poder marcar todas las respuestas como "aceptadas", pero para mí la respuesta de NIck fue la primera que me hizo decir "ajá".