7.1 二叉搜索树

循关键码访问(call-by-key)：数据项之间，依照各自的关键码彼此区分
关键码之间支持大小比较与相等比对
数据集合中的数据项统一表示与实现为词条(entry)形式

template <typename K, typename v> struct Entry { // 词条模板类
    K key; // 关键码
    V value; // 数值
    Entry(K k = K(), V v = V()): key(k), value(v) {}; // 默认构造函数
    Entry(Entry<K, V> const & e): key(e.key), value(e.value) {}; // 克隆
    bool operator< (Entry<K, V> const & e) { // 小于
        return key < e.key;
    }
    bool operator> (Entry<K, V> const & e) { // 大于
        return key > e.key;
    }
    bool operator== (Entry<K, V> const & e) { // 等于
        return key == e.key;
    }
    bool operator!= (Entry<K, V> const & e) { // 不等于
        return key != e.key;
    }
}; // 比较器、判等器

Binary Search Tree(BST)基本组成单位为节点，每个节点中各自存有一个词条，每个词条唯一对应一个关键码
顺序性：任一节点均不小于/不大于其左/右后代
顺序性虽然只是对局部特征的刻画，但由此却可以导出某种全局特征
单调性：BST中序遍历序列，必然单调非降

BST模板类

template <typename T> class BST: public BinTree<T> { // 由BinTree派生
public: // 以virtual修饰，以便派生类重写
    virtual BinNodePosi(T) & search(const T &); // 查找
    virtual BinNodePosi(T) insert(const T &); // 插入
    virtual bool remove(const T &); // 删除
protected:
    BinNodePosi(T) _hot; // 命中节点的父节点
    BinNodePosi(T) connect34(BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T)); // 3+4重构
    BinNodePosi(T) rotateAt(BinNodePosi(T)); // 旋转调整
};

查找
从根节点出发，逐步缩小查找范围，直至发现目标（成功），或查找范围缩小至空树（失败）

template <typename T> BinNodePosi(T) & BST<T>::search(const T & e) {
    return searchIn(_root, e, _hot = NULL); // 从根节点启动查找
}
static BinNodePosi(T) & searchIn(BinNodePosi(T) & v, const T & e, BinNodePosi(T) & hot) { // 当前（子）树根，目标关键码，记忆热点
    if (!v || (e == v -> data))
        return v; // 足以确定失败或成功
    hot = v; // 记录当前（非空）节点
    return searchIn(((e < v -> data) ? v -> lChild : v -> rChild), e, hot);
}

返回的引用值：成功时指向一个关键码为e且真实存在的节点，失败时指向最后一次试图转向的空节点NULL（假想为数值为e的哨兵节点）
无论成功与否，返回值总是等效指向命中节点，而_hot总是指向命中节点的父节点

插入
借助search(e)确定插入位置及方向，将新节点插入
若e不存在，则_hot为新节点的父节点，v = search(e)为_hot对新子节点的引用

template <typename T> BinNodePosi(T) BST<T>::insert(const T & e) {
    BinNodePosi(T) & x = search(e); // 查找目标
    if (!x) { // 禁止相同元素，故仅在查找失败时插入
        x = new BinNode<T>(e, _hot); // 在x处创建新节点，以_hot为父节点
        _size++; // 更新全树规模
        updateHeightAbove(x); // 更新全树节点高度
    }
    return x; // 无论e是否存在于原树中，至此总有x -> data == e
}

删除

template <typename T> bool BST<T>::remvoe(const T & e) {
    BinNodePosi(T) & x = search(e); // 定位目标节点
    if (!x)
        return false; // 确认目标存在（此时_hot为x的父节点）
    removeAt(x, _hot); // 删除
    _size--; // 更新全树规模
    updateHeightAbove(_hot); // 更新全树节点高度
    return true;
} // 返回是否成功删除

若*x某一子树为空，则可将其替换为另一子树
二叉搜索树的拓扑结构依然完整，顺序性依然满足

template <typename T> static BinNodePosi(T) removeAt(BinNodePosi(T) & x, BinNodePosi(T) & hot) {
    BinNodePosi(T) w = x; // 被删除的节点，初值同x
    BinNodePosi(T) succ = NULL; // 被删除节点的接替者
    if (!HasLChild(*x))
        succ = x = x -> rChild; // 左子树为空
    else if (!HasRChild(*x))
        succ = x = x -> lChild; // 右子树为空
    else { // 左右子树并存
        w = w -> succ();
        swap(x -> data, w -> data); // 令*x与其后继*w互换数据
        BinNodePosi(T) u = w -> parent; // 原问题转化删除节点w
        (u == x ? u -> rChild : u -> lChild) = succ = w -> rChild;
    }
    hot = w -> parent; // 记录被删除节点的父节点
    if (succ)
        succ -> parent = hot; // 将被删除节点的接替者与hot相联
    release(w -> data);
    release(w); // 释放被删除节点
    return succ; // 返回接替者
}