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; //g复衡后,局部子树高度必然复原;其祖先亦必如此,故调整随即结束 0009 } else //否则(g依然平衡),只需简单地 0010 updateHeight ( g ); //更新其高度(注意:即便g未失衡,高度亦可能增加) 0011 } //至多只需一次调整;若果真做过调整,则全树高度必然复原 0012 return xx; //返回新节点位置 0013 } //无论e是否存在于原树中,总有AVL::insert(e)->data == e