如何在网站建设远程教育,门户网站建设信息化项目背景,广州专业seo公司,上海搜索引擎优化公司排名查找
所谓的查找或搜索#xff0c;指从一组数据对象中找出符合特定条件者#xff0c;这是构建算法的一种基本而重要的操作。其中的数据对象#xff0c;统一地表示和实现为 词条#xff08;entry#xff09; 的形式#xff1b;不同词条之间#xff0c;依照各自的 关键码…查找
所谓的查找或搜索指从一组数据对象中找出符合特定条件者这是构建算法的一种基本而重要的操作。其中的数据对象统一地表示和实现为 词条entry 的形式不同词条之间依照各自的 关键码key 彼此区分。
循关键码访问 查找的过程与结果仅仅取决于目标对象的关键码。
词条
template typename K, typename V struct Entry { //词条模板类K key; V value; //关键码、数值Entry ( K k K(), V v V() ) : key ( k ), value ( v ) {}; //默认构造函数Entry ( EntryK, V const e ) : key ( e.key ), value ( e.value ) {}; //基于克隆的构造函数bool operator ( EntryK, V const e ) { return key e.key; } //比较器小于bool operator ( EntryK, V const e ) { return key e.key; } //比较器大于bool operator ( EntryK, V const e ) { return key e.key; } //判等器等于bool operator! ( EntryK, V const e ) { return key ! e.key; } //判等器不等于
}; //得益于比较器和判等器从此往后不必严格区分词条及其对应的关键码词条对象拥有成员变量key和value。前者作为特征是词条之间比对和比较的依据后者为实际的数据。
任意词条之间可相互比较大小是有序向量得以定义以及二分查找算法赖以成立的基本前提。
二叉搜索树
二叉搜索树中处处都满足顺序性任一 节点r的 左右子树中 所有节点 若存在均不大于不小于r 假定所有节点互不相等 回避边界情况任一 节点r 的 左右子树中 所有 节点 若 存在均小于大于r。 在实际应用中对相等元素的禁止既不自然也不必要。
包含不同的 n n n 个节点可以构成的不同二叉搜索树有 C a t a l a n ( n ) ( 2 n ) ! / [ ( n 1 ) ! n ! ] Catalan(n) (2n)!/[(n1)!n!] Catalan(n)(2n)!/[(n1)!n!] 棵。
任何 一棵二叉树是二叉搜索树当且仅当其中序遍历序列单调非降。
BST 模板类
#include ../BinTree/BinTree.h //引入BinTreetemplate typename T class BST : public BinTreeT{ //由BinTree派生BST模板类
protected:BinNodePosi(T)_hot; //“命中”节点的父亲BinNodePosi(T) connect34 (//按照“34”结构联接3个节点及四棵子树BinNodePosi(T)BinNodePosi(T)BinNodePosi(T),BinNodePosi(T)BinNodePosi(T)BinNodePosi(T)BinNodePosi(T));BinNodePosi(T) rotateAt ( BinNodePosi(T) x );//对x及其父亲、祖父做统一旋转调整
public: //基本接口︰以virtual修饰强制要求所有派生类(BST变种根据各自的规则对其重写virtual BinNodePosi(T) search ( const Te );//查找virtual BinNodePosi(T) insert ( const Te );//插入virtual bool remove ( const Te );//删除
};BST查找
采用了减而治之的思路与策略其执行过程可描述为从树根出发 逐步地缩小查找范围直到发现目标成功或缩小至空树失败
查找过程中一旦发现当前节点为NULL即说明查找范围已经缩小至空查找失败否则视关键码比较结果向左更小或向右更大深入或者报告成功相等。
template typename T //在以v为根的AVL、SPLAY、rbTree等BST子树中查找关键码e
static BinNodePosi(T) searchIn ( BinNodePosi(T) v, const T e, BinNodePosi(T) hot ) {if ( !v || ( e v-data ) ) return v; //逑弻基在节点v或假想的通配节点处命中hot v; //一般情况先记下当前节点然后再return searchIn ( ( ( e v-data ) ? v-lc : v-rc ), e, hot ); //深入一层递归查找
} //返回时返回值指向命中节点或假想的通配哨兵hot指向其父亲退化时为初始值NULLtemplate typename T BinNodePosi(T) BSTT::search ( const T e ) //在BST中查找关键码e
{ return searchIn ( _root, e, _hot NULL ); } //返回目标节点位置的引用以便后续插入、删除操作若查找成功则searchIn()以及search()的返回值都将如图(a)所示指向一个关键码为e且真实存在的节点若查找失败则返回值的数值虽然为NULL但是它作为引用将如图(b)所示指向最后一次试图转向的空节点。 在调用searchIn()算法之前search()接口首先将内部变量_hot初始化为NULL然后作为引用型参数hot传递给searchIn()。在整个查找的过程中hot变量始终指向当前节点的父亲。因此在算法返回时按照如上定义_hot亦将统一指向“命中节点”的父亲。
_hot节点是否拥有另一个孩子与查找成功与否无关。查找成功时节点e可能是叶子也可能是内部节点查找失败时假想的哨兵e等效于叶节点但可能有兄弟。
复杂度 总体所需时间应线性正比于查找路径的长度或最终返回节点的深度最好为O(1)最坏为O(n). 若要控制单次查找在最坏情况下的运行时间须从控制二叉搜索树的高度入手。
BST插入
为了在二叉搜索树中插入一个节点首先需要利用查找算法search()确定插入的位置及方向然后才能将新节点作为叶子插入。
template typename T BinNodePosi(T) BSTT::insert ( const T e ) { //将关键码插入BST树中BinNodePosi(T) x search ( e ); if ( x ) return x; //确认目标不存在留意对_hot癿设置x new BinNodeT ( e, _hot ); //创建新节点x以e为关键码以_hot为父_size; //更新全树规模updateHeightAbove ( x ); //更新x及其历代祖先的高度return x; //新插入的节点必为叶子
} //无论e是否存在于原树中返回时总有x-data e首先调用search()查找e。若返回位置x非空则说明已有雷同节点插入操作失败。否则x必是_hot节点的某一空孩子于是创建这个孩子并存入e。此后更新全树的规模记录并调用updateHeightAbove()更新x及其历代祖先的高度。 按照以上实现方式无论插入操作成功与否都会返回一个非空位置且该处的节点与拟插入的节点相等。如此可以确保一致性以简化后续的操作。
复杂度 节点插入操作所需的时间主要消耗于对算法search()及updateHeightAbove()的调用。后者与前者一样在每一层次至多涉及一个节点仅消耗O(1)时间故其时间复杂度也同样取决于新节点的深度在最坏情况下不超过全树的高度。
BST删除
为从二叉搜索树中删除节点首先也需要调用算法BST::search()判断目标节点是否的确存在于树中。若存在则需返回其位置然后方能相应地具体实施删除操作。
单分支 若欲删除节点69需首先通过search(69)定位待删除节点69。因该节点的右子树为空故只需如图(b)所示将其替换为左孩子64则拓扑意义上的节点删除即告完成。 当然为保持二叉搜索树作为数据结构的完整性和一致性还需更新全树的规模记录释放被摘除的节点69并自下而上地逐个更新替代节点64历代祖先的高度。注意首个需要更新高度的祖先58恰好由_hot指示。
双分支
设拟再删除二度节点36。如图(b)所示首先调用BinNode::succ()算法找到该节点的直接后继40。然后只需如图©所示交换二者的数据项则可将后继节点等效地视作待删除的目标节点。不难验证该后继节点必无左孩子从而相当于转化为此前相对简单的情况。于是最后可如图(d)所示将新的目标节点36替换为其右孩子46。 请注意在中途互换数据项之后这一局部如图( c )所示曾经一度并不满足顺序性。但这并不要紧–不难验证在按照上述方法完成整个删除操作之后全树的顺序性必然又将恢复。 同样地除了更新全树规模记录和释放被摘除节点此时也要更新一系列祖先节点的高度。不难验证此时首个需要更新高度的祖先53依然恰好由_hot指示。
remove() 删除关键码
1 template typename T bool BSTT::remove ( const T e ) { //从BST树中删除关键码e
2 BinNodePosi(T) x search ( e ); if ( !x ) return false; //确荏目标存在留意_hot癿设置
3 removeAt ( x, _hot ); _size--; //实施删除
4 updateHeightAbove ( _hot ); //更新_hot及其历代祖先的高度
5 return true;
6 } //删除成功与否由返回值指示首先调用search()查找e。若返回位置x为空则说明树中不含目标节点故删除操作随即可以失败返回。否则调用removeAt()删除目标节点x。同样此后还需更新全树的规模并调用函数updateHeightAbove(_hot)更新被删除节点历代祖先的高度。
/*******************************************容*********容************************容***********
* BST节点删除算法︰删除位置x所指的节点全局静态模板函数适用于AVL、Splay、RedBlack等各种BST )
*目标x在此前经查找定位并确认非NULL故必删除成功;与searchIn不同调用之前不必将hot置空
*返回值指向实际被删除节点的接替者hot指向实际被删除节点的父亲——二者均有可能是NULL
*************************************牢*容**牢****水*容容容***水水水容容容*容容容容容容容容容容容容容容容容容字米林容容容容容**/
template typename T
static BinNodePosi(T) removeAt ( BinNodePosi(T) xBinNodePosi(T) hot ) {BinNodePosi(T) w x; //实际被摘除的节点初值同xBinNodePosi(T) succ NULL;//实际被删除节点的接替者if (!HasLChild ( *x ) ) //若*x的左子树为空则可succ x x-rc; //直接将*x替换为其右子树else if ( ! HasRChild (*x ) ) //若右子树为空则可succ x x-lc; //对称地处理——注意∶此时succ ! NULLelse { //若左右子树均存在则选择x的直接后继作为实际被摘除节点为此需要w w-succ(); //在右子树中)找到*x的直接后继*wswap ( x-dataw-data );//交换*x和*w的数据元素BinNodePosi(T) u w-parent;( ( u x ) ? u-rc : u-lc ) succ w-rc;//隔离节点*w}hot w-parent;//记录实际被删除节点的父亲if ( succ ) succ-parent hot; //并将被删除节点的接替者与hot相联release ( w-data ); release ( w ); return succ;//释放被摘除节点返回接替者
}复杂度 删除操作所需的时间主要消耗于对search()、succ()和updateHeightAbove()的调用。在树中的任一高度它们至多消耗O(1)时间。故总体的渐进时间复杂度亦不超过全树的高度。
平衡
search()、insert()和remove()等主要接口的运行时间均线性正比于二叉搜索树的高度。 在最坏情况下二叉搜索树可能彻底地退化为列表此时的查找效率甚至会降至O(n)线性正比于数据集的规模。 因此需要控制树高。
任意的n个互异关键码都可以构成n!种全排列。若各排列作为输入序列的概率均等则只要将它们各自所生成二叉搜索树的平均查找长度进行平均即可在一定程度上反映二叉搜索树的平均查找性能。可以证明在这一随机意义下二叉搜索树的平均高度为O(logn)。 假定n个互异节点同时给定然后在遵守顺序性的前提下随机确定它们之间的拓扑联接。如此称二叉搜索树由这组节点“随机组成”。由n个互异节点组成的二叉搜索树总共可能有(2n)!/n!/(n 1)!棵。若这些树出现的概率均等则通过对其高度做平均可知 平均查找长度为 O ( n ) O(\sqrt n) O(n )。
理想平衡与适度平衡
既然二叉搜索树的性能主要取决于高度故在节点数目固定的前提下应该尽可能降低高度。相应地应尽可能使兄弟子树的高度彼此接近即全树尽可能地平衡。 包含n个节点的二叉树高度不可能小于 [ log 2 n ] [\log_2n] [log2n]。若高度恰好为 [ log 2 n ] [\log_2n] [log2n]则称作理想平衡树。
在渐进意义下适当放松标准之后的平衡性称作适度平衡。
等价交换
若两颗二叉搜索树的中序遍历序列相同则称它们彼此等价反之亦然。 虽然等价二叉搜索树中各节点的垂直高度可能有所不同但水平次序完全一致。
平衡二叉搜索树的适度平衡性都是通过对树中每一局部增加某种限制条件来保证的。具有以下局部性 1经过单次动态修改操作后至多只有O(1) 处局部不再满足限制条件 2总可在O(log n)时间内使这O(1)处局部以至全树重新满足限制条件。 意味着刚刚失去平衡的二叉搜索树必然可以迅速转换为一棵等价的平衡二叉搜索树。等价二叉搜索树之间的上述转换过程也称作等价变换。
旋转调整
最基本的修复手段就是通过围绕特定节点的旋转实现等价前提下的局部拓扑调整。 zig 旋转顺时针旋转将X和v作为c的左子树、右孩子Y和Z分别作为v的左、右子树。 zag旋转逆时针旋转将v和Z作为c的左孩子、右子树X和Y分别作为v的左、右子树。
zig和zag旋转均属局部操作均属于等价操作仅涉及常数个节点及其之间的联接关系故均可在常数时间内完成。就与树相关的指标而言经一次 zig 或 zag 旋转之后节点v的深度加一节点c的深度减一这一局部子树乃至全树的高度可能发生变化但上、下幅度均不超过一层。
AVL树
通过合理设定适度平衡的标准并借助等价变换AVL树AVL tree可以实现近乎理想的平衡 。 在渐进意义下AVL树可始终将其高度控制在O(logn)以内从而保证每次查找、插入或删除操作均可在O(logn)的时间内完成。
AVL树重平衡
任一节点v的平衡因子定义为“其左、右子树的高度差”即balFac(v) height(lc(v)) - height(rc(v))。 所谓AVL树即平衡因子受限的二叉搜索树—其中各节点平衡因子的绝对值均不超过1。
AVL 模板类
#include ../BST/BST.h” //基于BST实现AVL树
template typename T class AVL : public BSTT{ //由BST派生AVL树模板类
public:BinNodePosi(T) insert ( const T e ); //插入重写)bool remove ( const T e ); //删除重写)
//BST::search()等其余接口可直接沿用
};#define Balanced(x) ( stature( (x).lc ) stature( (x).rc ) )//理想平衡条件
#define BalFac(x) ( stature( (x).lc ) - stature( (x).rc ) )//平衡因子
#define AvlBalanced(x)( ( -2BalFac(x) ) ( BalFac(x)2 ) )//AVL平衡条件在完全二叉树中各节点的平衡因子非0即1故完全二叉树必是AVL树。
结论高度为h的AVL树至少包含fib(h 3) - 1个节点数学归纳所得 包含n个节点的AVL树的高度应为O(logn)。
失衡与重平衡
AVL 树经过插入、删除等动态修改操作之后节点的高度可能发生变化以致于不再满足AVL树的条件。 因节点x的插入或删除而暂时失衡的节点构成失衡节点集记作UT(x)。请注意若x为被摘除的节点则UT(x)仅含单个节点但若x为被引入的节点则UT(x)可能包含多个节点。
AVL树插入
新引入节点x后UT(x)中的节点都是x的祖先且高度不低于x的祖父。以下将其中的最深者记作g(x)。在x与g(x)之间的通路上设p为g(x)的孩子v为p的孩子。注意既然g(x)不低于x的祖父则p必是x的真祖先。 g(x)是因x的引入而失衡则p和v的高度均不会低于其各自的兄弟。
借助如下代码所示的宏tallerChild()即可反过来由g(x)找到p和v
/**************************************************************************************
*在左、右孩子中取更高者
*在AVL平衡调整前借此确定重构方案
*************************************************************************************/
#define tallerChild(x)( \stature( (x)-lc ) stature( (x)-rc ) ?(x)-lc : (/*左高*/ \stature( (x)-lc ) stature( (x)-rc ) ?(x)-rc : (/*右高*/ \IsLChild(* (x)) ? (x)-lc : (x)-rc /*等高︰与父亲x同侧者(zIg-zIg或zAg-zAg )优先*/ \
) \
) \单旋 做逆时针旋转zag(g(x))得到如图(b)所示的另一棵等价二叉搜索树。
双旋 节点插入后通过连续的两次旋转操作使AVL树重新平衡 此时可先做顺时针旋转zig(p)得到如图(b)所示的一棵等价二叉搜索树。再做逆时针旋转zag(g(x))得到如图( c )所示的另一棵等价二叉搜索树。
实现
template typename T BinNodePosi(T) AVLT::insert ( const T e ) { //将关键码e插入AVL树中BinNodePosi(T) x search ( e ); if ( x ) return x;//确认目标节点不存在BinNodePosi(T) xx x new BinNodeT ( e,_hot ); _sizet;//创建新节点x
//此时x的父亲_hot若增高则其祖父有可能失衡for ( BinNodePosi(T) g _hot; g; g g-parent ) { //从x之父出发向上逐层检查各代祖先gif ( !AvlBalanced ( *g ) ) { //一旦发现g失衡则(采用“34”算法使之复衡并将子树FromParentTo ( *g ) rotateAt ( tallerChild ( tallerchild ( g ) ) );//重新接入原树break; //g复衡后局部子树高度必然复原;其祖先亦必如此故调整随即结束}else //否则( g依然平衡只需简单地updateHeight ( g );//更新其高度注意∶即便g未失衡高度亦可能增加)}//至多只需一次调整﹔;若果真做过调整则全树高度必然复原return xx;//返回新节点位置
}//无论e是否存在于原树中总有AVL::insert(e)-data e无论单旋或双旋经局部调整之后不仅g(x)能够重获平衡而且局部子树的高度也必将复原。这就意味着g(x)以上所有祖先的平衡因子亦将统一地复原。换而言之在AVL树中插入新节点后仅需不超过两次旋转即可使整树恢复平衡。
算法首先按照二叉搜索树的常规算法在O(logn)时间内插入新节点x。既然原树是平衡的故至多检查O(logn)个节点即可确定g(x)如有必要至多旋转两次即可使局部乃至全树恢复平衡。 AVL树的节点插入操作可以在O(logn)时间内完成
AVL树删除
与插入操作十分不同在摘除节点x后以及随后的调整过程中失衡节点集UT(x)始终至多只含一个节点。而且若该节点g(x)存在其高度必与失衡前相同。另外还有一点重要的差异是g(x)有可能就是x的父亲。
与插入操作同理从_hot节点出发沿parent指针上行经过O(logn)时间即可确定g(x)位置。作为失衡节点的g(x)在不包含x的一侧必有一个非空孩子p且p的高度至少为1。于是可按以下规则从p的两个孩子其一可能为空中选出节点v若两个孩子不等高则v取作其中的更高者否则优先取v与p同向者亦即v与p同为左孩子或者同为右孩子。
单旋 (a)所示由于在T3中删除了节点而致使g(x)不再平衡但p的平衡因子非负时通过以g(x)为轴顺时针旋转一次即可恢复局部的平衡。平衡后的局部子树如图(b)所示。
双旋 节点删除后通过两次旋转恢复局部平衡。 g(x)失衡时若p的平衡因子为-1则经过以p为轴的一次逆时针旋转之后图(b)即可转化为图(a)。再以g(x)为轴顺时针旋转即可恢复局部平衡图( c )。
在删除节点之后尽管也可通过单旋或双旋调整使局部子树恢复平衡但复平衡之后局部子树的高就全局而言依然可能再次失衡。这种由于低层失衡节点的重平衡而致使其更高层祖先失衡的现象称作“失衡传播” 失衡传播的方向必然自底而上而不致于影响到后代节点。
实现
template typename T bool AVLT::remove ( const T e ) { //从AVL树中删除关键码eBinNodePosi(T) x search ( e ); if ( !x ) return false;//确认目标存在留意_hot的设置)removeAt ( x,_hot ); _size--;//先按BST规则删除之此后原节点之父_hot及其祖先均可能失衡)for ( BinNodePosi(T) g _hot; g; g g-parent ) { //从_hot出发向上逐层检查各代祖先gif ( !AvlBalanced ( *g ) )//一旦发现g失衡则(采用“34”算法使之复衡并将该子树联至g FromParentTo ( *g ) rotateAt ( tallerchild ( tallerChild ( g ) ) );//原父亲updateHeight ( g );//并更新其高度注意:即便g未失衡高度亦可能降低)}//可能需做O(logn)次调整——无论是否做过调整全树高度均可能降低return true;//删除成功
}//若目标节点存在且被删除返回true;否则返回false较之插入操作删除操作可能需在重平衡方面多花费一些时间。不过既然需做重平衡的节点都是x的祖先故重平衡过程累计只需不过O(logn)时间。 综合各方面的消耗AVL树的节点删除操作总体的时间复杂度依然是O(logn)。
AVL树(34)-重构
同样需要从刚发生修改的位置x出发逆行而上直至遇到最低的失衡节点g(x)。于是在g(x)更高一侧的子树内其孩子节点p和孙子节点v必然存在而且这一局部必然可以g(x)、p和v为界分解为四棵子树将它们按中序遍历次序重命名为 T0 至 T3。 若同样按照中序遍历次序重新排列g(x)、p和v并将其命名为a、b和c则这一局部的中序遍历序列应为{T0 , a, T1 , b, T2 , c, T3} 将这三个节点与四棵子树重新“组装”起来恰好即是一棵AVL树 这一理解涵盖了此前两节所有的单旋和双旋情况。相应的重构过程仅涉及局部的三个节点及其四棵子树故称作 “3 4”重构 。
/********************************************************************
*按照“34”结构联接3个节点及其四棵子树返回重组之后的局部子树根节点位置即b)
*子树根节点与上层节点之间的双向联接均须由上层调用者完成
*可用于AVL和RedBlack的局部平衡调整
***********************************************************************/
template typename T BinNodePosi(T) BSTT::connect34 (BinNodePosi(T) aBinNodePosi(T) b BinNodePosi(T) c,BinNodePosi(T)T0BinNodePosi(T)T1BinNodePosi(T) T2BinNodePosi(T) T3
) {a-lc T0; if ( T0 ) T0-parent a;a-rc T1; if ( T1 ) T1-parent a; updateHeight ( a );c-lc T2; if ( T2 ) T2-parent c;c-rc T3; if ( T3 ) T3-parent c; updateHeight ( c );b-lc a; a-parent b;b-rc c; c-parent b; updateHeight ( b );return b;//该子树新的根节点
}利用以上connect34()算法即可视不同情况按如下具体方法完成重平衡
/**********************************************************************
* BST节点旋转变换统一算法( 3节点4子树)返回调整之后局部子树根节点的位置
*注意:尽管子树根会正确指向上层节点如果存在但反向的联接须由上层函数完成
*************************************************************************/
template typename T BinNodePosi(T) BSTT::rotateAt ( BinNodePosi(T)v ) { //v为非空孙辈节点BinNodePosi(T) p v-parent;BinNodePosi(T) g p-parent;//视v、 p和g相对位置分四种情况if ( IsLChild ( *p ) )/* zig */if ( IsLChild (*v ) ) {/* zig-zig*/p-parent g-parent;//向上联接return connect34 ( v, p g v-lc v-rc, p-rc, g-rc );}else { /* zig-zag */v-parent g-parent;//向上联接return connect34 ( p, vgp-lc, v-lc v-rc g-rc );else/* zag */if ( IsRChild (*v ) ) {/* zag-zag */p-parent g-parent;//向上联接return connect34 ( g, p, v, g-lcp-lcv-lc, v-rc );}else { /* zag-zig */v-parent g-parent;//向上联接return connect34 ( g, v, pg-lc v-lc v-rcp-rc );}
}复杂度也依然是O(1)
