首页 > 代码库 > 搜索树
搜索树
前面写过了向量和链表的结构,前者静态性能好而动态性能差,后者则相反。考虑改进树的结构,得到动态和静态性能都让人满意的数据结构,特别是在查找以及插入删除操作上具有优势。
查找或搜索(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。
搜索树