- 浏览: 2962678 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (2529)
- finance (1459)
- technology (218)
- life (343)
- play (150)
- technology-component (0)
- idea (6)
- house (74)
- health (75)
- work (32)
- joke (23)
- blog (1)
- amazing (13)
- important (22)
- study (13)
- Alternative (0)
- funny (8)
- stock_technology (12)
- business (16)
- car (21)
- decorate (4)
- basketball (2)
- English (16)
- banker (1)
- TheBest (1)
- sample (2)
- love (13)
- management (4)
最新评论
-
zhongmin2012:
BSM确实需要实践,标准ITIL服务流程支持,要做好,需要花费 ...
BSM实施之前做什么 -
shw340518:
提示楼主,有时间逻辑bug:是你妈二十那年写的 那会儿连你爹都 ...
80后辣妈给未来儿子的信~我的儿,你也给我记住了~~~ -
guoapeng:
有相关的文档吗?
it项目管理表格(包含146个DOC文档模板) -
solomon:
看到的都是 这种 CTRL+C 和 CTRL+V 的文章, ...
Designing a website with InfoGlue components -
wendal:
恩, 不错. 有参考价值
Designing a website with InfoGlue components
7.6 AVL树
7.6.1 AVL树的定义
高度平衡的二叉搜索树
一棵AVL树或者是空树,或者是具有下列性质的二叉搜索树:它的左子树和右子树都是AVL树,且左子树和右子树的高度之差的绝对值不超过1。
高度不平衡的二叉搜索树 高度平衡的二叉搜索树
结点的平衡因子balance (balance factor)
1、每个结点附加一个数字,给出该结点右子树的高度减去左子树的高度所得的高度差。这个数字即为结点的平衡因子balance 。
2、根据AVL树的定义,任一结点的平衡因子只能取 -1,0和 1。
3、如果一个结点的平衡因子的绝对值大于1,则这棵二叉搜索树就失去了平衡,不再是AVL树。
4、如果一棵二叉搜索树是高度平衡的,它就成为 AVL树。如果它有n个结点,其高度可保持在O(log2n),平均搜索长度也可保持在O(log2n)。
AVL树的类定义
template <class Type> class AVLTree {
public:
struct AVLNode {
Type data;
AVLNode *left, *right;
int balance;
AVLNode ( ) : left (NULL), right (NULL), balance (0) { }
AVLNode ( Type d, AVLNode *l = NULL, AVLNode *r = NULL )
: data (d), left (l), right (r), balance (0) { }
};
protected:
Type RefValue;
AVLNode *root;
int Insert ( AVLNode* &tree, Type x, int &taller );
void RotateLeft ( AVLNode *Tree, AVLNode* &NewTree );
void RotateRight ( AVLNode *Tree, AVLNode* &NewTree );
void LeftBalance ( AVLNode* &Tree, int &taller );
void RightBalance(AVLNode* &Tree, int &taller);
int Depth ( AVLNode *t ) const;
public:
AVLTree ( ) : root (NULL) { }
AVLNode ( Type Ref ) : RefValue (Ref), root (NULL) { }
int Insert ( Type x ) {
int taller;
return Insert ( root, x, taller );
}
friend istream& operator >> ( istream& in, AVLTree<type>& Tree );
friend ostream& operator << ( ostream& out, const AVLTree<type>& Tree );
int Depth ( ) const;
}
7.6.2 平衡化旋转
1、如果在一棵平衡的二叉搜索树中插入一个新结点,造成了不平衡。
此时必须调整树的结构,使之平衡化。
2、平衡化旋转有两类:
单旋转 (左旋和右旋) 双旋转 (左平衡和右平衡)
3、每插入一个新结点时,AVL树中相关结点的平衡状态会发生改变。因此,在插入一个新结点后,需要从插入位置沿通向根的路径回溯,检查各结点的平衡因子(左、右子树的高度差)。
4、如果在某一结点发现高度不平衡,停止回溯。
5、从发生不平衡的结点起,沿刚才回溯的路径取直接下两层的结点。
6、 如果这三个结点处于一条直线上,则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转,其中一个是另一个的镜像,其方向与不平衡的形状相关。
7、如果这三个结点处于一条折线上,则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。
右单旋转
左单旋转
左右双旋转
右左双旋转
1、左单旋转 (RotateLeft )
(1)如果在子树E中插入一个新结点,该子树高度增1导致结点A的平衡因子变成+2,出现不平衡。
(2)沿插入路径检查三个结点A、C和E。它们处于一条方向为“\”的直线上,需要做左单旋转。
(3)以结点C为旋转轴,让结点A反时针旋转。
左单旋转的算法
template <class Type> void AVLTree<type>:: RotateLeft ( AVLNode *Tree, AVLNode* &NewTree ) {
NewTree = Tree→right;
Tree→right = NewTree→left;
NewTree→left = Tree;
}
2、右单旋转 (RotateRight )
(1)在左子树D上插入新结点使其高度增1,导致结点A的平衡因子增到 -2,造成了不平衡。
(2) 为使树恢复平衡,从A沿插入路径连续取3个结点A、B和D,它们处于一条方向为“/”的直线上,需要做右单旋转。
(3) 以结点B为旋转轴,将结点A顺时针旋转。
右单旋转的算法
template <class Type> void AVLTree<type>:: RotateRight( AVLNode *Tree, AVLNode* &NewTree) {
NewTree = Tree→left;
Tree→left = NewTree→right;
NewTree→right = Tree;
}
3、先左后右双旋转 (RotationLeftRight)
(1)在子树F或G中插入新结点,该子树的高度增1。结点A的平衡因子变为 -2,发生了不平衡。
(2) 从结点A起沿插入路径选取3个结点A、B和E,它们位于一条形如“?”的折线上,因此需要进行先左后右的双旋转。
(3)首先以结点E为旋转轴,将结点B反时针旋转,以E代替原来B的位置,做左单旋转。
(4) 再以结点E为旋转轴,将结点A顺时针旋转,做右单旋转。使之平衡化。
左平衡化的算法
template <class Type> void AVLTree<type>:: LeftBalance ( AVLNode * &Tree, int & taller ) {
AVLNode *leftsub = Tree→left, *rightsub;
switch ( leftsub→balance ) {
case -1 :
Tree→balance = leftsub→balance = 0;
RotateRight ( Tree, Tree );
taller = 0;
break;
case 0 :
cout << “树已经平衡化.\n";
break;
case 1 :
rightsub = leftsub→right;
switch ( rightsub→balance ) {
case -1:
Tree→balance = 1;
leftsub→balance = 0;
break;
case 0 :
Tree→balance = leftsub→balance = 0;
break;
case 1 :
Tree→balance = 0;
leftsub→balance = -1;
break;
}
rightsub→balance = 0;
RotateLeft ( leftsub, Tree→left );
RotateRight ( Tree, Tree );
taller = 0;
}
}
4、先右后左双旋转 (RotationRightLeft)
(1)右左双旋转是左右双旋转的镜像。
(2) 在子树F或G中插入新结点,该子树高度增1。结点A的平衡因子变为2,发生了不平衡。
(3) 从结点A起沿插入路径选取3个结点A、C和D,它们位于一条形如“?”的折线上,需要进行先右后左的双旋转。
(4)首先做右单旋转:以结点D为旋转轴,将结点C顺时针旋转,以D代替原来C的位置。
(5) 再做左单旋转:以结点D为旋转轴,将结点A反时针旋转,恢复树的平衡。
右平衡化的算法
template <class Type> void AVLTree<type>:: RightBalance ( AVLNode * &Tree, int & taller ) {
AVLNode *rightsub = Tree→right, *leftsub;
switch ( rightsub→balance ) {
case 1 :
Tree→balance = rightsub→balance = 0;
RotateLeft ( Tree, Tree );
taller = 0;
break;
case 0 :
cout << “树已经平衡化.\n";
break;
case -1 :
leftsub = rightsub→left;
switch ( leftsub→balance ) {
case 1 :
Tree→balance = -1;
rightsub→balance = 0;
break;
case 0 :
Tree→balance = rightsub→balance = 0;
break;
case -1 :
Tree→balance = 0;
rightsub→balance = 1;
break;
}
leftsub→balance = 0;
RotateRight ( rightsub, Tree→left );
RotateLeft ( Tree, Tree );
taller = 0;
}
}
7.6.3 AVL树的插入和删除
AVL树的插入:
1、在向一棵本来是高度平衡的AVL树中插入一个新结点时,如果树中某个结点的平衡因子的绝对值 |balance| > 1,则出现了不平衡,需要做平衡化处理。
2、在AVL树上定义了重载操作“>>”和“<<”,以及中序遍历的算法。利用这些操作可以执行AVL树的建立和结点数据的输出。
3、 算法从一棵空树开始,通过输入一系列对象的关键码,逐步建立AVL树。在插入新结点时使用了前面所给的算法进行平衡旋转。
例,输入关键码序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 },插入和调整过程如下。
从空树开始的建树过程
1、下面的算法将通过递归方式将新结点作为叶结点插入并逐层修改各结点的平衡因子。
2、 在发现不平衡时立即执行相应的平衡化旋转操作,使得树中各结点重新平衡化。
3、 在程序中,用变量success记载新结点是否存储分配成功,并用它作为函数的返回值。
4、算法从树的根结点开始,递归向下找插入位置。在找到插入位置(空指针)后,为新结点动态分配存储空间,将它作为叶结点插入,并置success为1,再将taller置为1,以表明插入成功。在退出递归沿插入路径向上返回时做必要的调整。
template <class Type> int AVLTree<type>:: Insert ( AVLNode* &tree, Type x, int &taller ) {
int success;
if ( tree == NULL ) {
tree = new AVLNode (x);
success = tree != NULL ? 1 : 0;
if ( success ) taller = 1;
}
else if ( x < tree→data ) {
success = Insert ( tree→left, x, taller );
if ( taller )
switch ( tree→balance ) {
case -1 :
LeftBalance ( tree, taller );
break;
case 0 :
tree→balance = -1;
break;
case 1 :
tree→balance = 0;
taller = 0;
break;
}
}
else {
success = Insert ( tree→right, x, taller );
if ( taller )
switch ( tree→balance ) {
case -1 :
tree→balance = 0;
taller = 0;
break;
case 0 :
tree→balance = 1;
break;
case 1 :
RightBalance ( tree, taller );
break;
}
}
return success;
}
AVL树的重载操作 >>、<< 和遍历算法的实现 :
template <class Type> istream & operator >> ( istream & in, AVLTree<type> & Tree ) {
Type item;
cout << “构造AVL树 :\n";
cout << “输入数据(以" << Tree.RefValue << “结束): ";
in >> item;
while ( item != Tree.RefValue ) {
Tree.Insert (item);
cout << “输入数据(以" << Tree.RefValue << “结束): ";
in >> item;
}
return in;
}
template <class Type> void AVLTree type
:: Traverse ( AVLNode *ptr, ostream & out ) const { //AVL树中序遍历并输出数据
if ( ptr != NULL ) {
Traverse ( ptr→left, out );
out << ptr→data << ' ';
Traverse ( ptr→right, out );
}
}
template <class Type> ostream & operator << ( ostream & out, const AVLTree<type> & Tree ) {
out << “AVL树的中序遍历.\n";
Tree.Traverse ( Tree.root, out );
out << endl;
return out;
}
AVL树的删除
1、如果被删结点x最多只有一个子女,那么问题比较简单。如果被删结点x有两个子女,首先搜索 x 在中序次序下的直接前驱 y (同样可以找直接后继)。再把 结点y 的内容传送给结点x,现在问题转移到删除结点 y。 把结点y当作被删结点x。
2、 将结点x从树中删去。因为结点x最多有一个子女,我们可以简单地把x的双亲结点中原来指向x的指针改指到这个子女结点;如果结点x没有子女,x双亲结点的相应指针置为NULL。然后将原来以结点x为根的子树的高度减1,
3、必须沿x通向根的路径反向追踪高度的变化对路 径上各个结点的影响。
4、 用一个布尔变量 shorter 来指明子树的高度是否被缩短。在每个结点上要做的操作取决于 shorter 的值和结点的 balance,有时还要依赖子女的 balance 。
5、 布尔变量 shorter 的值初始化为True。然后对于从 x 的双亲到根的路径上的各个结点 p,在 shorter 保持为 True 时执行下面的操作。如果 shorter 变成False,算法终止。
6、case 1 : 当前结点p的balance为0。如果它的左子树或右子树被缩短,则它的 balance改为1或-1,同时 shorter 置为False。
7、case 2 : 结点p的balance不为0,且较高的子树被缩短,则p的balance改为0,同时 shorter 置为True。
8、case 3 : 结点p的balance不为0,且较矮的子树又被缩短,则在结点p发生不平衡。需要进行平衡化旋转来恢复平衡。令p的较高的子树的根为 q (该子树未被缩短),根据q的balance ,有如下3种平衡化操作。
9、case 3a : 如果q的balance为0,执行一个单旋转来恢复结点p的平衡,置shorter为False。
10、 case 3b : 如果q的balance与p的balance相同,则执行一个单旋转来恢复平衡,结点p和q的balance均改为0,同时置shorter为True。
11、case 3c : 如果p与q的balance相反,则执行一个双旋转来恢复平衡,先围绕 q 转再围绕 p 转。新的根结点的balance置为0,其它结点的balance相应处理,同时置shorter为True。
12、 在case 3a, 3b和3c的情形中,旋转的方向取决于是结点p的哪一棵子树被缩短。
7.6.4 AVL树的高度
1、设在新结点插入前AVL树的高度为h,结点个数为n,则插入一个新结点的时间是O(h)。对于AVL树来说,h多大?
2、设 Nh 是高度为 h 的AVL树的最小结点数。根的一棵子树的高度为 h-1,另一棵子树的高度为 h-2,这两棵子树也是高度平衡的。因此有 N-1 = 0 (空树) N0 = 1 (仅有根结点) Nh = Nh-1 + Nh-2 +1 , h > 0
3、可以证明,对于 h ? 0,有 Nh = Fh+3 -1 成立。
4、有n个结点的AVL树的高度不超过
5、在AVL树删除一个结点并做平衡化旋转所需时间为 O(log2n)。
6、 二叉搜索树适合于组织在内存中的较小的索引(或目录)。对于存放在外存中的较大的文件系统,用二叉搜索树来组织索引不太合适。
7、 在文件检索系统中大量使用的是用B_树或B+树做文件索引。
发表评论
-
New Enterprise Security Solutions
2011-09-13 15:46 0<!-- [if !mso]> <styl ... -
ES Announces Enterprise Security Solutions
2011-09-13 15:40 0<!-- [if !mso]> <styl ... -
linux下如何将文件打包、压缩并分割成制定大小?
2010-09-15 18:52 3318将大文件或目录打包、 ... -
rhel4 yum安装, 使用
2010-09-07 16:37 0第一种方法: yum源来自chinalinuxpub.com ... -
Windows: 远程自动安装程序
2010-08-26 15:48 1107问题的提出 作为 ... -
Oracle体系结构
2010-08-07 09:53 1044Oracle体系结构 Oracle Server包括Oracl ... -
ocp sesson 3
2010-07-31 14:39 0show parameter undo 只有 默认情况下服务 ... -
ocp session 2
2010-07-25 17:00 0/home/oracle/raInventory/orains ... -
ocp session 1
2010-07-24 13:02 0ocp first lesson D:\oracle_cou ... -
Python的xmlrpc调试
2010-07-19 23:55 2132Python的xmlrpc 调 试 ----------- ... -
mdadm使用详解及RAID 5简单分析
2010-07-11 16:19 1399http://blog.csdn.net/chinalinux ... -
Linux的lvm的基本配置步骤
2010-07-11 14:53 12901.增加硬件 增加的ide硬盘前缀为hd,scs ... -
OCP study material
2010-07-11 13:52 0\\192.168.1.105watch -n 1 'stat ... -
apache+python+mod_python+django 编译安装指南
2010-06-24 17:25 14771、本文将知道你在 linux 下使用源码包安装 ... -
在ubuntu下配置apache运行python脚本
2010-06-22 16:11 2278常用的简单命令 sudo apt ... -
Python 2.5 Quick Reference
2010-06-21 11:18 1473... -
shell 面试题汇集
2010-06-10 19:50 1066利用 top 取某个进程的 CPU 的脚本 : ... -
shell程序面试题
2010-06-10 19:48 29321.要求分析Apache访问日志,找出里面数量在前面100位的 ... -
EMC技术支持工程师笔试部分试题回忆
2010-06-07 15:16 1655要查看更多EMC公司笔经相关信息,请访问EMC公司校园招聘CL ... -
linux shell 条件语句
2010-06-03 23:29 1799...
相关推荐
最后,AVLTree类还可以包含其他功能,如中序遍历、前序遍历和后序遍历等,这些都可以通过递归或迭代的方式来实现。 总的来说,这个C++实现的AVL树利用了模板类的灵活性和`shared_ptr`的自动内存管理,能够高效且...
8. **遍历操作**:AVL树支持前序、中序和后序遍历,这些可以通过递归轻松实现。 在`avl.C`和`avl.h`这两个文件中,应该包含了上述所有操作的实现。通过理解这些核心概念,你可以阅读源码并了解AVL树的C++实现细节。...
7. **遍历操作**:AVL树支持前序遍历、中序遍历和后序遍历。遍历顺序分别为:根-左-右、左-根-右和左-右-根。 8. **实际应用**:AVL树在数据库索引、编译器符号表、文件系统等场景中有广泛应用,因为它们需要高效的...
8. **遍历**:键树支持前序、中序和后序遍历,这些遍历方法分别以根节点、左子树和右子树为优先顺序。在实际应用中,中序遍历常用于生成排序序列。 了解了这些基本概念后,阅读并理解`keyTree`源代码将变得容易许多...
这里我们关注的是C++实现的二叉平衡排序树(BST),这是一种特殊的二叉树,它保证了左子节点的值小于父节点,右子节点的值大于父节点,从而使得树的搜索、插入和删除操作具有较高的效率。 首先,我们来讨论一下...
这可能涉及到旋转操作,例如AVL树的单旋、双旋,或者红黑树的色调整和旋转。 3. **删除操作**:找到并移除指定节点,同时维护树的平衡。删除操作通常比插入更复杂,需要处理多种情况,如删除叶子节点、只有一个孩子...
5. **遍历**:AVL树支持前序遍历、中序遍历和后序遍历。中序遍历的结果是有序的,可用于搜索、排序等操作。 6. **查找**:AVL树的查找效率较高,因为它的最大高度是O(log n),其中n是树中的节点数量。 7. **模板类...
在实际编程中,二叉树的实现可能涉及递归函数、迭代循环、指针操作以及各种树遍历方法(如前序、中序和后序遍历)。同时,为了测试和调试代码,可以创建示例树并打印其结构,或者使用图形化工具来可视化树的操作。 ...
4. `avl.hpp` 和 `avl.h`:可能包含了AVL树的实现细节,如AVL树特有的平衡操作,如单旋、双旋等。 5. `bt.hpp`:可能定义了二叉树的一般操作,如遍历方法(前序、中序、后序)。 6. `btpostorderiterator.h`, `...
在插入或删除节点后,通过旋转操作(单旋或双旋)来重新平衡树。 红黑树则是一种弱平衡的二叉搜索树,它允许局部不平衡,但通过红色和黑色节点的规则来保证任何路径到叶子节点的长度最多是两倍于最短路径,保证了...