0001 #include "BinTree/BinTree.h" //引入BinTree
0002 
0003 template <typename T> class BST : public BinTree<T> { //由BinTree派生BST模板类
0004 protected:
0005    BinNodePosi<T> _hot; //“命中”节点的父亲
0006    BinNodePosi<T> connect34 ( //按照“3 + 4”结构，联接3个节点及四棵子树
0007       BinNodePosi<T>, BinNodePosi<T>, BinNodePosi<T>,
0008       BinNodePosi<T>, BinNodePosi<T>, BinNodePosi<T>, BinNodePosi<T> );
0009    BinNodePosi<T> rotateAt ( BinNodePosi<T> x ); //对x及其父亲、祖父做统一旋转调整
0010 public: //基本接口：以virtual修饰，强制要求所有派生类（BST变种）根据各自的规则对其重写
0011    virtual BinNodePosi<T> & search ( const T& e ); //查找
0012    virtual BinNodePosi<T> insert ( const T& e ); //插入
0013    virtual bool remove ( const T& e ); //删除
0014 };