0001 template <typename T> BinNodePosi<T> Splay<T>::insert( const T& e ) { //将关键码e插入伸展树中
0002    if ( !_root ) { _size = 1; return _root = new BinNode<T>( e ); } //原树为空
0003    BinNodePosi<T> t = search( e );
0004    if ( e == t->data ) return t; //目标节点t若存在，伸展至根
0005    if ( t->data < e ) //在右侧嫁接
0006       { t->parent = _root = new BinNode<T>( e, NULL, t, t->rc ); t->rc = NULL; }
0007    else //在左侧嫁接
0008       { t->parent = _root = new BinNode<T>( e, NULL, t->lc, t ); t->lc = NULL; }
0009    _size++; t->updateHeightAbove(); return _root; //更新规模及高度，报告插入成功
0010 } //无论e是否存在于原树中，返回时总有_root->data == e