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 = g->parent ) //从x之父出发向上,逐层检查各代祖先g 0006 if ( !AvlBalanced ( *g ) ) { //一旦发现g失衡,则(采用“3 + 4”算法)使之复衡,并将子树 0007 FromParentTo ( *g ) = rotateAt ( tallerChild ( tallerChild ( g ) ) ); //重新接入原树 0008 break; //局部子树复衡后,高度必然复原;其祖先亦必如此,故调整结束 0009 } else //否则(g仍平衡) 0010 updateHeight ( g ); //只需更新其高度(注意:即便g未失衡,高度亦可能增加) 0011 return xx; //返回新节点位置 0012 } //无论e是否存在于原树中,总有AVL::insert(e)->data == e