0001 template <typename T> BNP<T> Splay<T>::insert(const T& e) { //将关键码e插入伸展树中
0002    if (!_root) { _size = 1; return _root = new BinNode<T>(e); } //原树为空
0003    search(e); if (e == _root->data) return _root; //查找成功（否则，_p已伸展至根）
0004    if (_p->data < e) //在右侧嫁接（rc或为空，lc == _p必非空）
0005       { _root = new BinNode<T>(e, nullptr, _p, _p->rc);  _p->rc = nullptr; }
0006    else  //e < _p->data：在左侧嫁接（lc或为空，rc == _p必非空）
0007       { _root = new BinNode<T>(e, nullptr, _p->lc, _p);  _p->lc = nullptr; }
0008    _p->updateHeightAbove();  _size++; return _root;
0009 } //insert