首页 > 代码库 > 搜索树

搜索树

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

查找或搜索(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。

搜索树