`
- 浏览:
28223 次
- 性别:
- 来自:
北京
-
AVL 树是带有平衡条件的儿茶查找树。这个平衡条件必须要容易保持,而且必须保证书的深度是O(log N),最简单的想法是
要求左右子树具有相同的高度
另一种平衡条件是要求每个节点都唏嘘要具有相同的高度的做子树和右子树
定义:AVL树是其每一个节点的左子树和右子树的高度最多差1的二叉树(空树的高度定义为-1)
AVL树节点的声明:
#ifndef _AvlTree_h
struct AvlNode;
typedef struct AvlNode *Position ;
typedef struct AvlNode *AvlTree ;
AvlTree MakeEmpty(AvlTree T);
Position Find(ElementType X,AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElementType X,AvlTree T);
AvlTree Delete(ElementType X,AvlTree T);
ElementType Retrieve(Position P);
#endif
struct AvlNode
{
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};
Position
Find( ElementType X, AvlTree T )
{
if( T == NULL )
return NULL;
if( X < T->Element )
return Find( X, T->Left );
else
if( X > T->Element )
return Find( X, T->Right );
else
return T;
}
Position
FindMin( AvlTree T )
{
if( T == NULL )
return NULL;
else
if( T->Left == NULL )
return T;
else
return FindMin( T->Left );
}
Position
FindMax( AvlTree T )
{
if( T != NULL )
while( T->Right != NULL )
T = T->Right;
return T;
}
计算AVL节点的高度的函数
static int Height(Position P)
{
if(P==NULL)
return -1;
else
return P->Height;
}
向AVL插入节点的函数
AvlTree Insert(ElementType X,AvlTree T)
{
if(T==NULL)
{
T=malloc(sizeof(struct AvlNode));
if(T==NULL)
FatalError("out of space");
else
{
T->Element=X;
T->Height=0;
T->Left=T->Right=NULL:
}
}
else
{
if(X<T->Element)
{
T->Left=Insert(X,T->Left);
if(Height(T->Left)-Height(T->Right)==2)
if(X<T->Left->Element)
T=SingleRotateWithLeft(T);
else
T=DoubleRotateWithLeft(T);
}
else if(X>T->Element)
{
T->Right=Insert(X,T->Right);
if(Height(T->Right)-Height(T->Left)==2)
if(X>T->Right->Element)
T=SingleRotateWithRight(T);
else
T=DoubleRotateWithRight(T);
}
T->Height=Max(Height(T->Left),Height(T->Right))+1;
return T;
}
}
执行单旋转过程
static Position SingleRotateWithLeft(Position K2)
{
Position K1;
K1=K2->Left;
K2->Left=K1->Right;
K1->Right=K2;
K2->Height=Max(Height(K2->Left),Height(K2->Right))+1;
K1->Height=Max(Height(K1->Left),K2->Height)+1;
return K1;
}
static Position
SingleRotateWithRight( Position K1 )
{
Position K2;
K2 = K1->Right;
K1->Right = K2->Left;
K2->Left = K1;
K1->Height = Max( Height( K1->Left ), Height( K1->Right ) ) + 1;
K2->Height = Max( Height( K2->Right ), K1->Height ) + 1;
return K2; /* New root */
}
执行双旋转过程
static Position DoubleRotateWithLeft(Position K3)
{
K3->Left=SingleRotateWithRight(K3->Left);
return SingleRotateWithLeft(K3);
}
static Position
DoubleRotateWithRight( Position K1 )
{
/* Rotate between K3 and K2 */
K1->Right = SingleRotateWithLeft( K1->Right );
/* Rotate between K1 and K2 */
return SingleRotateWithRight( K1 );
}
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
主要内容包括:算法效率的输入规模、阶和大O,数据结构的无序和有序列表,队列和栈基于数组和链表的设计实例,递归详解,二叉查找树和AVL树,堆、散列表和排序以及图论等。对于每一种数据结构的性质和用途,《计算机...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
数据结构与算法分析 经典笔记学习笔记 1 前言 1.1 所选教材 1.2 写作原因 1.3 一些约定 1.4 历史记录 1.5 联系方式 2 单链表 2.1 代码实现 2.2 效率问题 2.3 应用:一元多项式(加法和乘法) 2.3.1 基础知识 2.3.2 ...
该代码由Amit Bansal在学习数据结构和算法时编写。 参考GFG,NPTEL,CLRS。 该存储库包含: 单链表。 添加两个数字表示的链表。 气泡在链接列表中排序合并在链接列表中排序合并排序链表反向使用或不使用堆栈的...
该存储库包含许多流行算法和数据结构的基于 ...A AVL树 A 红黑树 A 线段树- 带有最小/最大/总和范围查询示例 A Fenwick 树(二元索引树) A 图(有向图和无向图) A 不相交集- 联合查找数据结构或合并查找集 A 布隆
这是我对于AVL学习时的一些代码和学习资料,~ 包括了AVL的删除与实现。代码与《数据结构》相似。
3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可直接用于毕设、课设、作业等。 适用工作项目、毕业设计,课程设计,项目源码均经过助教老师测试,运行无误,轻松复刻,欢迎下载 -------- 下载后...
## 数组 ...3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。 --------
AVL树作为数据结构,说简单也简单,说复杂也复杂。对初学者来说,一定要掌握的是检测和调整AVL树平衡(含四种旋转)的代码,随着学习的深入,应该尝试编写AVL树的完整代码。 这里就给大家提供一份可用
特点: - 逐步处理所有算法 - 排序算法 - 动态数组 - 二叉堆和二项堆 - AVL 树 - (a, b) 树 - 规划中的散列: - 图形 - O 符号 重要说明:即使这个程序应该展示一些众所周知的算法和数据结构是如何高效实现的,这些...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
这是一篇学习完邓俊辉老师的数据结构课程后,对课程中讲到的各种 数据结构 和 算法 的总结、回顾和归纳。 课程地址: 所有代码都是在: WINDOW系统下 VS2017 编写和运行的 数据结构 向量 向量的特点和构成 向量的常用...
二叉树的前序建立法、广义表非递归建立法,前中后序、层次序、广义表、图形显示,二叉搜索树的实现及二叉平衡搜索树的实现代码与大家分享!
④AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下,n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树高度约为lgn,AVL树是最接近最优的。 1.2.6 平衡因子 二叉树上任一结点的左子树...
DSA_CPP_Deng:【清华大学】数据结构与算法邓俊辉教授课程学习代码。堆栈,队列,AVL,BST,B树,RB树等的实现
基本数据结构和算法 这些算法全部自己敲一遍: 链表 链表 双向链表 哈希表/散列表 (Hash Table) 散列函数 碰撞解决 字符串算法 排序 查找 BF算法 KMP算法 BM算法 正则表达式 数据压缩 树 二叉树 二叉查找树 伸展树...
AdvancedDataStructures:大学时期学习数据结构的C ++源码,包含AVL树,Treap,多个有序链表合并,二叉查找树,二项堆,红黑树,扭曲树,跳表,栈与数量相互模拟以及最小(大)值改善,主席树的C ++版实现,欢迎指出...
学习数据结构的一些代码,包括数组,链表,二分搜索树,集合,映射,优先队列,并查集,线段树,字典树(前缀树),AVL树,红黑树,哈希表,如有错误,多多指教。 我们在调用set,map等标准库里的东西,大多使用平衡...