算法与数据结构——AVL树（平衡二叉树）
2024-10-21 05:53:42
定义
typedef struct AVLNode* Position;
typedef Position AVLTree; /* AVL树类型 */
struct AVLNode {
ElementType Data; /* 结点数据 */
AVLTree Left; /* 指向左子树 */
AVLTree Right; /* 指向右子树 */
int Height; /* 树高 */
};
前期准备函数
int Max(int a, int b)
{
return a > b ? a : b;
}
int GetHeight(Position T)
{
int hr, hl;
if (!T)
{
return 0;
}
hl = GetHeight(T->Left);
hr = GetHeight(T->Right);
return (hl > hr) ? ++hl : ++hr;
}
实现功能的主要函数
调整函数
Position SingleRoateWithLeft(Position A)
{
Position B;
B = A->Left;
A->Left = B->Right;
B->Right = A;
A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
B->Height = Max(GetHeight(B->Left), GetHeight(B->Right)) + 1;
return B;//new node
}
//右单旋
Position SingleRoateWithRight(Position A)
{
Position B;
B = A->Right;
A->Right = B->Left;
B->Left = A;
A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
B->Height = Max(GetHeight(B->Left), GetHeight(B->Right)) + 1;
return B;
}
//右左双旋
Position DoubleRoateWithLeft(Position A)
{
A->Left = SingleRoateWithRight(A->Left);
return SingleRoateWithLeft(A);
}
//左右双旋
Position DoubleRoateWithRight(Position A)
{
A->Right = SingleRoateWithLeft(A->Right);
return SingleRoateWithRight(A);
}
插入函数（兼具建树功能）
AVLTree Insert(ElementType X, AVLTree T)
{
if (T == NULL)
{
T = new AVLNode;
T->Data = X;
T->Left = T->Right = NULL;
T->Height = 0;
}
else if (X < T->Data)
{
T->Left = Insert(X, T->Left);
if (GetHeight(T->Left) - GetHeight(T->Right) == 2)
{
if (X < T->Left->Data)
{
T = SingleRoateWithLeft(T);
}
else
{
T = DoubleRoateWithLeft(T);
}
}
}
else
{
T->Right = Insert(X, T->Right);
if (GetHeight(T->Right) - GetHeight(T->Left) == 2)
{
if (X > T->Right->Data)
{
T = SingleRoateWithRight(T);
}
else
{
T = DoubleRoateWithRight(T);
}
}
}
T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
return T;
}
删除函数
删除函数和插入函数很像，删除的情况要考虑好。图解参考
AVLTree Delete(ElementType X, AVLTree T)
{
if (T == NULL)
{
return NULL;
}
if (X < T->Data)
{
T->Left = Delete(X, T->Left);
}
else if (X > T->Data)
{
T->Right = Delete(X, T->Right);
}
else
{
if (T->Left)
{
AVLTree tmp= FindMax(T->Left);
T->Data = tmp->Data;
T->Left = Delete(tmp->Data, T->Left);
}
else if (T->Right)
{
AVLTree tmp = FindMin(T->Right);
T->Data = tmp->Data;
T->Right = Delete(tmp->Data, T->Right);
}
else
{
free(T);
return NULL;
}
}
if (GetHeight(T->Left) - GetHeight(T->Right) == 2)
{
if (GetHeight(T->Left->Left)>GetHeight(T->Left->Right))
{
T = SingleRoateWithLeft(T);
}
else
{
T = DoubleRoateWithLeft(T);
}
}
else if (GetHeight(T->Right) - GetHeight(T->Left) == 2)
{
if (GetHeight(T->Right->Right) > GetHeight(T->Right->Left))
{
T = SingleRoateWithRight(T);
}
else
{
T = DoubleRoateWithRight(T);
}
}
T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
return T;
}
其他函数
VLTree MakeEmpty(AVLTree T)
{
if (T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
Position Find(ElementType X, AVLTree T)
{
if (T == NULL)
{
return NULL;
}
if (X < T->Data)
{
return Find(X,T->Left);
}
else if(X>T->Data)
{
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)
{
return NULL;
}
else if(T->Right==NULL)
{
return T;
}
else
{
return FindMax(T->Right);
}
}
深度和高度
void showHeight(int a,Position T)
{
if (T == NULL)
{
return;
}
showHeight(a,T->Left);
cout << T->Height << ' ';
showHeight(a,T->Right);
}
void showdeep(int depth,Position T)
{
if (T == NULL) return;
if (T)
{
showdeep(depth + 1, T->Left);
cout << depth+1<<' ';
showdeep(depth + 1, T->Right);
}
}
最新文章
- CentOS：设置系统级代理（转）
- POJ 2356. Find a multiple 抽屉原理 / 鸽巢原理
- xUtils 中的BitmapUtils 全面注释
- Twain头文件
- Jquery note
- C语言带参数的main()函数
- OC加强-day02
- Windows Server 2012 R2里十个极好的新功能
- strcat()的编写
- mysql 各数据类型的 大小及长度
- 百度java开发面试题
- 二进制数据的序列化反序列化和Json的序列化反序列化的重要区别
- 关于新学期Python的一点见解
- Centos7 设置静态IP地址
- [Leetcode 18]四数之和 4 Sum
- C#-1-1-.net
- 跨域验证cookie与缓存控制
- Hibernate JPA 关联关系
- apigateway-kong(三)Proxy规则
- AngularJS入门之动画