首页 > 代码库 > 数据结构--Avl树的创建，插入的递归版本和非递归版本，删除等操作
数据结构--Avl树的创建，插入的递归版本和非递归版本，删除等操作
AVL树本质上还是一棵二叉搜索树，它的特点是：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值最多为1（空树的高度为-1）。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
对Avl树进行相关的操作最重要的是要保持Avl树的平衡条件。即对Avl树进行相关的操作后，要进行相应的旋转操作来恢复Avl树的平衡条件。
对Avl树的插入和删除都可以用递归实现，文中也给出了插入的非递归版本，关键在于要用到栈。
代码如下：
#include <iostream>
#include<stack>
using namespace std;
struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *Avltree;
struct AvlNode //AVL树节点
{
int Element;
Avltree Left;
Avltree Right;
int Hight;
int Isdelete; //指示该元素是否被删除
};
///////////////AVL平衡树的函数的相关声明//////////////////////
Avltree MakeEmpty(Avltree T); //清空一棵树
static int Height(Position P); //返回节点的高度
Avltree Insert(int x, Avltree T); //在树T中插入元素x
Avltree Insert_not_recursion (int x, Avltree T); //在树T中插入元素x,非递归版本
Position FindMax(Avltree T); //查找Avl树的最大值，和二叉树一样
Avltree Delete(int x,Avltree T); //删除元素，非懒惰删除
///////////////AVL平衡树的函数的相关定义//////////////////////
Avltree MakeEmpty(Avltree T)
{
if (T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
delete T;// free(T);
}
return NULL;
}
static int Height(Position P) //返回节点的高度
{
if(P == NULL)
return -1;
else
return P->Hight;
}
static int Element(Position P) //返回节点的元素
{
if(P == NULL)
return -1000;
else
return P->Element;
}
int Max(int i,int j) //返回最大值
{
if(i > j)
return i;
else
return j;
}
static Position SingleRotateWithLeft (Position k2) //单旋转，左子树高度比较高
{
Position k1;
k1 = k2->Left;
k2->Left = k1->Right;
k1->Right = k2;
k2->Hight = Max(Height(k2->Left), Height(k2->Right)) + 1;
k1->Hight = Max(Height(k1->Left), Height(k1->Right)) + 1;
return k1; //新的根
}
static Position SingleRotateWithRight (Position k1) //单旋转，右子树的高度比较高
{
Position k2;
k2 = k1->Right;
k1->Right = k2->Left;
k2->Left = k1;
k1->Hight = Max(Height(k1->Left), Height(k1->Right)) + 1;
k2->Hight = Max(Height(k2->Left), Height(k2->Right)) + 1;
return k2; //新的根
}
static Position DoubleRotateWithLeft (Position k3) //双旋转，当k3有左儿子而且k3的左儿子有右儿子
{
k3->Left = SingleRotateWithRight(k3->Left);
return SingleRotateWithLeft(k3);
}
static Position DoubleRotateWithRight (Position k1) //双旋转，当k1有右儿子而且k1的又儿子有左儿子
{
k1->Right = SingleRotateWithLeft(k1->Right);
return SingleRotateWithRight(k1);
}
//对Avl树执行插入操作，递归版本
Avltree Insert(int x, Avltree T)
{
if(T == NULL) //如果T为空树，就创建一棵树，并返回
{
T = static_cast<Avltree>(malloc(sizeof(struct AvlNode)));
if (T == NULL)
{
cout << "out of space!!!" << endl;
}
else
{
T->Element = x;
T->Left = NULL;
T->Right = NULL;
T->Hight = 0;
T->Isdelete = 0;
}
}
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->Hight = Max(Height(T->Left), Height(T->Right)) + 1;
return T;
}
//对Avl树进行插入操作，非递归版本
Avltree Insert_not_recursion (int x, Avltree T)
{
stack<Avltree> route; //定义一个堆栈使用
//找到元素x应该大概插入的位置，但是还没进行插入
Avltree root = T;
while(1)
{
if(T == NULL) //如果T为空树，就创建一棵树，并返回
{
T = static_cast<Avltree>(malloc(sizeof(struct AvlNode)));
if (T == NULL) cout << "out of space!!!" << endl;
else
{
T->Element = x;
T->Left = NULL;
T->Right = NULL;
T->Hight = 0;
T->Isdelete = 0;
route.push (T);
break;
}
}
else if (x < T->Element)
{
route.push (T);
T = T->Left;
continue;
}
else if (x > T->Element)
{
route.push (T);
T = T->Right;
continue;
}
else
{
T->Isdelete = 0;
return root;
}
}
//接下来进行插入和旋转操作
Avltree father,son;
while(1)
{
son = route.top ();
route.pop(); //弹出一个元素
if(route.empty())
return son;
father = route.top ();
route.pop(); //弹出一个元素
if(father->Element < son->Element ) //儿子在右边
{
father->Right = son;
if( Height(father->Right) - Height(father->Left) == 2)
{
if(x > Element(father->Right))
father = SingleRotateWithRight(father);
else
father = DoubleRotateWithRight(father);
}
route.push(father);
}
else if (father->Element > son->Element) //儿子在左边
{
father->Left = son;
if(Height(father->Left) - Height(father->Right) == 2)
{
if(x < Element(father->Left))
father = SingleRotateWithLeft(father);
else
father = DoubleRotateWithLeft(father);
}
route.push(father);
}
father->Hight = max(Height(father->Left),Height(father->Right )) + 1;
}
}
Position FindMax(Avltree T)
{
if(T != NULL)
{
while(T->Right != NULL)
{
T = T->Right;
}
}
return T;
}
Position FindMin(Avltree T)
{
if(T == NULL)
{
return NULL;
}
else
{
if(T->Left == NULL)
{
return T;
}
else
{
return FindMin(T->Left );
}
}
}
Avltree Delete(int x,Avltree T) //删除Avl树中的元素x
{
Position Temp;
if(T == NULL)
return NULL;
else if (x < T->Element) //左子树平衡条件被破坏
{
T->Left = Delete(x,T->Left );
if(Height(T->Right) - Height(T->Left) == 2)
{
if(x > Element(T->Right) )
T = SingleRotateWithRight(T);
else
T = DoubleRotateWithRight(T);
}
}
else if (x > T->Element) //右子树平衡条件被破坏
{
T->Right = Delete(x,T->Right );
if(Height(T->Left) - Height(T->Right) == 2)
{
if(x < Element(T->Left) )
T = SingleRotateWithLeft(T);
else
T = DoubleRotateWithLeft(T);
}
}
else //执行删除操作
{
if(T->Left && T->Right) //有两个儿子
{
Temp = FindMin(T->Right);
T->Element = Temp->Element;
T->Right = Delete(T->Element ,T->Right);
}
else //只有一个儿子或者没有儿子
{
Temp = T;
if(T->Left == NULL)
T = T->Right;
else if(T->Right == NULL)
T = T->Left;
free(Temp);
}
}
return T;
}
int main ()
{
Avltree T = NULL;
T = Insert_not_recursion(3, T); //T一直指向树根
T = Insert_not_recursion(2, T);
T = Insert_not_recursion(1, T);
T = Insert_not_recursion(4, T);
T = Insert_not_recursion(5, T);
T = Delete(1,T);
// T = Insert_not_recursion(6, T);
/*
T = Insert(3, T); //T一直指向树根
T = Insert(2, T);
T = Insert(1, T);
T = Insert(4, T);
T = Insert(5, T);
T = Insert(6, T);*/
cout << T->Right->Right->Element << endl;
return 0;
}
递归与栈的使用有着不可描述的关系，我觉得如果要把递归函数改写成非递归的函数，首先要想到用栈。
唉，夜似乎更深了。
数据结构--Avl树的创建，插入的递归版本和非递归版本，删除等操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。