0001 template <typename T> BinNodePosi<T> AVL<T>::insert( const T& e ) { //将关键码e插入AVL树中
0002    BinNodePosi<T>& x = search( e ); if ( x ) return x; //插入失败
0003    BinNodePosi<T> xx = x = new BinNode<T>( e, _hot ); _size++; //创建新节点x
0004 // 此时，x的父亲_hot若增高，则其祖父有可能失衡
0005    for ( BinNodePosi<T> g = _hot; g; g->updateHeight(), g = g->parent ) //逐层上溯
0006       if ( !AvlBalanced( g ) ) { //一旦发现失衡祖先g，则
0007          rotateAt( tallerChild( tallerChild( g ) ) ); //（采用“3+4”算法）使之复衡
0008          break; //并随即终止（局部子树复衡后，高度必然复原；所有祖先亦必复衡）
0009       }
0010    return xx; //插入成功
0011 } //至多会做O(1)次调整