Arvores AVL

Boas pessoal, estou desenvolvendo um template para uma arvore AVL.

Mas estou com algumas dúvidas em como checar desequilibrios, para efetuar as roações.

A estrutura que estou utilizando para o template é:

template<class T>
class AVLTree
{
public:
struct _AVLNODE
{

 T value;
 //int _height;
 struct _AVLNODE* right;
 struct _AVLNODE* left;
 };

//... resto da classe...Agora vem o problema:É preferivel manter a altura de cada vertticie (ou nó, se você preferir) na propria estrutura, e conforme percorro a arvore para adicionar um novo verticie eu atualizo as alturas, e então checo por uma diferença >= 2 nas alturas e vejo se é preciso rodar, ou não.

Ou eu computo todas as alturas on-the-fly, ao adicionar um nó...

Esse segundo método é de maior complexidade, mas economiza 4 bytes em cada nó...

Qual optar?