搜索树

前面写过了向量和链表的结构，前者静态性能好而动态性能差，后者则相反。考虑改进树的结构，得到动态和静态性能都让人满意的数据结构，特别是在查找以及插入删除操作上具有优势。

查找或搜索(search)：从一组数据对象中找出符合条件者的操作。把数据对象，定义为词条的形式(Entry)，词条的形式为关键码-值，即为key-value形式，前者作为比较的依据，后者是实际存储的数据。词条必须定义key相关的比较操作，词条的排序就是key的排序。因此，查找的过程和结果，仅仅取决于目标对象的关键码，这种方式称作循关键码访问(call-by-key)。

二叉搜索树

考虑每个节点互不相等的情况，如果任一节点r的左子树中，所有节点都不大于r，右子树中，所有节点都不小于r，那么这棵树称为二叉搜索树(binary search tree)。

回想二叉树的中序遍历，总体即为lc-r-rc的顺序。按照如上定义的二叉搜索树，其中序遍历必然是非减的，反过来依然成立，即一棵二叉树是二叉搜索树，当且仅当其中序遍历是非减的。

下面，给出一个二叉搜索树的模板实现：

 1 template<typename T> class BST :public BinTree<T>
 2 {
 3 protected:
 4     BinNodePosi(T) _hot;//“命中”节点的父亲
 5     BinNodePosi(T) connect34(BinNodePosi(T), BinNodePosi(T), BinNodePosi(T),
 6         BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T));//联结3个节点和4颗子树
 7     BinNodePosi(T) rotateAt(BinNodePosi(T) x);//对x及其父亲、祖父做统一旋转调整
 8 public:
 9     virtual BinNodePosi(T)& search(const T& e);
10     virtual BinNodePosi(T) insert(const T& e);
11     virtual bool remove(const T& e);
12 };

继承二叉树的大部分操作，只需要重新定义查找、添加、删除操作即可。

查找

从二叉搜索树的定义即可发现，查找的过程，只需要从树根出发，根据大小转向左右子树即可。再回想二叉树中的定义，如果一棵树接近于一颗满二叉树，那么查找的操作，几乎与中序遍历顺序的数组二的分查找一模一样。当然，这是一种非常理想的状态，需要二叉树尽可能满。实际上，最坏的时候，二叉搜索树也会退化成链表，查找的效率仅为O(n)。这也是后面要介绍的几种搜索树的着手点：对树增加限制，使得查找更为高效。

按照上面思路的代码如下：

 1 template<typename T> //在以v为根的BST子树中查找关键码e
 2 static BinNodePosi(T)& searchIn(BinNodePosi(T)& v, const T& e, BinNodePosi(T)& hot)
 3 {
 4     if (equal(v, e)) return v; hot=v;
 5     while (1)
 6     {
 7         BinNodePosi(T) &c = (e < hot->data) ? hot->lc : hot->rc;
 8         if (equal(c, e)) return c; hot = c;
 9     }
10 }
11 template<typename T> BinNodePosi(T)& BST<T>::search(const T& e)
12 {
13     return searchIn(_root, e, _hot = NULL);
14 }

这里同样需要解决二分查找时相同的问题，如果不命中元素应该如何处理。这里，以_hot作为命中节点的父亲，如果查找的结果为NULL，它的父亲也可以指明位置。

如上面分析的，复杂度最坏可能为O(n)，当二叉搜索树退化链表时。

插入

插入操作的基础是查找，如果一个关键码已经存在，直接返回即可。如果不存在，返回插入的位置，申请一个新的节点空间并把它加入到二叉搜索树中，实现代码如下：

1 template<typename T> BinNodePosi(T) BST<T>::insert(const T& e)//将关键码e插入到BST树中
2 {
3     BinNodePosi(T)& x = search(e); if (x) return x;//如果e已经存在，直接返回，操作失败
4     x = new BinNode<T>(e, _hot);//search必然返回要插入的位置
5     _size++;
6     updateHeightAbove(x);
7     return x;
8 }

删除

与插入操作类似，删除操作同样需要先查找。如果关键码不存在，直接返回。不同之处在于，如果删除的节点不是叶节点，那么需要分情况讨论：如果只有左子树或者右子树，直接接入即可；如果两个子树都存在，那么需要把以被删除节点为根节点的子树重新接入原树中。这里，包含三个步骤：把要删除的节点删除，选取合适的节点重新接入，释放被删除的节点。

事实上，可以简化这个步骤：直接交换要删除的节点与替换的节点的value，然后删除掉交换完的节点并保留要删除的节点，再释放要删除的点。如下图所示。

这里，确定交换节点的方式，是使用了二叉树的后继。使用后继交换也会造成问题，删除大量元素后，二叉树左侧会高于右侧，造成不平衡。可以考虑等概率用前驱和后继替换解决这个问题。

template<typename T> bool BST<T>::remove(const T& e)//删除关键码e
{
    BinNodePosi(T)& x = search(e); if (!x) return false;
    removeAt(x, _hot); _size--;
    updateHeightAbove(_hot);
    return true;
}
template<typename T> static BinNodePosi(T) removeAt(BinNodePosi(T)& x, BinNodePosi(T)& hot)
{
    BinNodePosi(T) w = x;//实际被摘除的节点
    BinNodePosi(T) succ = NULL;
    if (!(x->lc))//如果左孩子为空
        succ = x = x->rc;//直接替换为右子树
    else if (!(x->rc))//如果右孩子为空
        succ = x = x->lc;
    else//左右孩子都存在，选择x的直接后继作为实际摘除的节点（可以画个图来理解）
    {
        w = w->succ();
        swap(x->data, w->data);//交换x与其直接后继的数值
        BinNodePosi(T) u = w->parent;
        ((u == x) ? u->rc : u->lc) = succ = w->rc;//隔离节点w，把w的孩子与原树连接起来
    }
    hot = w->parent;//记录被删除节点的父亲
    if (succ) succ->parent = hot;//将被删除节点的接替者与hot连接
    release(w->data); release(w); //释放被删除的节点
    return succ;//返回后继(接替)
}

删除操作的复杂度不超过树的高度。

平衡二叉搜索树

如果一棵二叉搜索树的高度小于log2N，那么称作理想平衡树。完全二叉树和满二叉树显然是理想平衡树。

然而事实上，维护一个理想平衡树是很困难的，叶节点均出现在最低两层的要求过高，维护代价会非常大。因此，引入了适度平衡的概念，即在渐进意义下放松标准的平衡。

将条件放松为高度渐进地不超过logn，则可以满足这个要求。AVL树，伸展树，红黑树，kd-树都是这样适度平衡的二叉搜索树。

因此，插入和删除操作都可能局部地破坏这个平衡性，为此，引入等价二叉搜索树的概念，以及一些用来恢复平衡的操作。

等价二叉树：如果经过某种变换后，二叉树的中序遍历不变，称为等价二叉树。变换可能会造成高度的改变，但是左右层次不会改变。

事实上，各种平衡二叉搜索树的条件是精妙的，具有局部性，即动态操作会造成局部失衡，但可以在很短的时间内恢复。

旋转

旋转是非常重要的操作，分两种：顺时针旋转zig和逆时针旋转zag，如下图所示：

可以发现，旋转操作后，树的中序遍历确实不会发生改变。因此，变换前后的树是等价的。此外，旋转后树的高度可能会发生变化，但是变化不超过1。