数据结构 --- c语言实现AVL平衡二叉搜索树_数据类型 charinfo

平衡二叉搜索树的作用

我们知道，对于一棵的二叉搜索树，其查找的时间复杂度是O(log2n)，所以查找效率还是很舒服的。但是在某些极端的情况下，比如在插入的序列是有序的时，二叉搜索树将退化成近似线性数据结构，既类似斜树。此时该树查询的时间复杂度将退化O(n)。此时，我们要怎么办？

平衡二叉搜索树就派上用场了，它在二叉搜索树的基础上，加上了自平衡的功能。让二叉搜索树可以经受住各种的插入和删除，依然保持左右子树的平衡，近似完全二叉树化，让查找的时间复杂度稳定在O(log2n)

二叉搜索树：有序二叉树

平衡二叉树：相对二叉搜索树，搜索效率提高，插入删除效率降低

衡量一个数据结构的查找效率是整体来衡量的

什么是树的高？

树有度和高的概念，结点有度和层级的概念，那什么是树的高呢？

对于高度的理解，我们不管它数据结构的什么知识，就拿楼房来说，假如一个人提问：楼房的高度有多高？我们会下意识的从底层开始往上数，假如楼有6层，则我们会说，这个楼有6层楼那么高，则提问者就会大概知道楼有多高了。所以高度就是以从下往上对比，这是我们的习惯。而在树中，树的高度也是从下往上数，如图所示，代码中假设第1层的高度是 0

K节点在树的底层，是一个叶子节点，则一般定义为K的高度在最低为1，以此类推，O的高度也是为1，P的节点也是为1。M节点是叶子节点O的父节点，从下往上数，M节点高度为2。那么G节点的高度是多少呢？从G-L的高度为2，从G-M-O节点高度为3，到底G节点高度为多少呢，正确答案是3，请看定义：

高度的定义为：从结点x向下到某个叶结点最长简单路径中边的条数

什么是树的深度？

理解了高度，深度的理解就很容易了，深度是从根节点往下，例如如上图：B的深度为2

对于整棵树来说，最深的叶结点的深度就是树的深度；树根的高度就是树的高度。这样树的高度和深度是相等的。
对于树中相同深度的每个结点来说，它们的高度不一定相同，这取决于每个结点下面的叶结点的深度

什么是结点的平衡因子？

平衡二叉搜索树的定义中，有一条是说二叉搜索树的每个结点的平衡因子需要满足在[-1,1]范围之内。所以当我们了解了什么是结点的高之后，我们再来了解一下什么是结点的平衡因子：

• 平衡因子是AVL树中为了防止二叉搜索树退化成链表而提出的概念
• 通过平衡因子，我们可以判断该二叉搜索树是否达到平衡，是否满足AVL树的定义

结点的平衡因子怎么去计算呢？

• 一个结点的平衡因子就是该结点左右孩子结点的高之差
• 或者说是一个结点的左右子树的高之差

默认情况下，我们使用左孩子节点的高 - 右孩子节点的高 的顺序去计算结点的平衡因子

所以，结点的平衡因子可以由如下计算的得出：

• 所以结点A的平衡因子 = 结点B的高 - 结点C的高 = 2

• 所以结点G的平衡因子 = 结点I的高 - 0 = 1

• 所以结点I的平衡因子 = 0 - 0 = 0

怎么判断一棵二叉搜索树是不是AVL树？

• 首先该树的前提肯定是一个棵二叉搜索树(二叉搜索树的中序遍历必定是一个升序序列)

• 然后标注这个树所有结点的高度

• 然后计算每个结点的平衡因子

• 看看是否有结点的平衡因子超过了[-1,1]取值区间

• 只要有结点的平衡因子超过了取值范围，就不满足AVL树，而没有超过则满足AVL树

• 如上图中，我们将一颗二叉搜索树的所有结点的高用红色字体标记出来，同时也算出了所有结点的平衡因子，用蓝色字体标记出来。可以看出，该二叉搜索树有两个结点的平衡因子是不再AVL树所要求的[-1,1]范围之内的，所以图中的二叉搜索树并不满足AVL树的要求

• AVL树中的结点跟平时二叉搜索树结点有个很大的不同点需要注意的是，AVL树的每个结点需要记住 结点的高 , 这个很重要，结点的高涉及到判断结点的平衡因子，而平衡因子则涉及到判断该树是否平衡，如何维护平衡等操作

• 创建结点的函数中，将某个结点的高默认为1。为什么呢？因为二叉搜索树中的新增结点，必定是该树的新叶子结点。而叶子结点的高必然是1

• 如果新插入一个节点是平衡的，就不用管，如果是不平衡，只有这四种可能，通过这四种旋转方式让它从不平衡变为平衡

构建数据类型    

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef struct 
{
	int key;        //键
	char info[20];  //数据类型--->字符串类型
}DATA,*LPDATA;

 辅助宏 - - -> 宏函数，获取当前节点 p节点的高度

#define HEIGHT(p) ((p==NULL)?-1:(p->height))    //p为NULL高度为-1否则等于p->height
#define MAX(a,b) ((a)>(b)?(a):(b))              //求a和b的最大值

 树的节点结构体描述

typedef struct AVLTreeNode 
{
	DATA data;                    //数据
	int height;                   //每个节点的高度
	struct AVLTreeNode* LChild;   //左子树节点
	struct AVLTreeNode* RChild;   //右子树节点
}NODE,*LPNODE,*AVLTree;

 创建节点 - - -> 把用户的数据变成一个节点

LPNODE  createNode(DATA data) 
{
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));  //动态内存申请
	assert(newNode);
    //给数据做初始化
	newNode->data = data;
	newNode->height = 0;    //只有一个节点的情况[只有根节点]高度为0
	newNode->LChild = NULL; //新节点的左右子树为NULL
	newNode->RChild = NULL;
	return newNode;
}

 二叉搜索树的遍历 - - -> 递归法遍历 

//打印当前节点中的数据
void printCurNode(LPNODE curNode) 
{
	printf("%d:%s\t高度:%d\n", curNode->data.key, 
		curNode->data.info, curNode->height);       //打印数据
}
//前序遍历
void preOrder(AVLTree root) 
{
	if (root != NULL) 
	{
		printCurNode(root);
		preOrder(root->LChild);
		preOrder(root->RChild);
	}
}

 四种旋转操作

 LL型：右旋

本来 k2-k1 是平衡的，多来了一个x，导致不平衡，通过旋转让它平衡

先考虑第一、第二种，再考虑三、四种，因为 第三、第四种需要借助于第一、第二种

• 想要让 k2 成为 k1 的右子树，由于 k2 的左子树本来指向 k1，1.临时保存 k1 ，因为后面的步骤还会用到 k1断开 k2---k1 ，2.设置 k2 的左子树，如果 k1 有右子树，让 k1 的右子树成为 k2 的左子树，如果 k1 没有右子树为 NULL，k2 的左子树设置为 NULL 也没有问题 3.让 k2 成为 k1 的右子树

• 4.最后让 k1 成为 k2 的父节点 tree 的左子树 - - -> 返回k1，  5.重新设置高度，k2和k1的高度发生了改变，k1的高度升高了，k2的高度降低了     k3 连接 k1，让 k3 移动到 k1 的位置即可，通过赋值的方式改变 tree，因为判断树是否平衡的情况：tree是重新回到根节点开始找的  tree = LL_Rotation(tree)；k3 = k1

//对于k2节点进行右旋
LPNODE LL_Rotation(LPNODE k2)
{
	LPNODE k1 = k2->LChild;    //对k2做旋转 需要记录k2的左子树:k1的位置
    //右旋
	k2->LChild = k1->RChild;   //k2的左子树变成k1的右子树 k2的右边不变
	k1->RChild = k2;           //k1的右子树变成k2
 
	//重新设置高度 判断k2有没有左边右边、有的话深度+1层 没有的话深度就是1层
    //k1占了原来k2的位置 高度要和原来k2的高度去比较
	k2->height = MAX(HEIGHT(k2->LChild), HEIGHT(k2->RChild)) + 1;
	k1->height = MAX(HEIGHT(k1->LChild), k2->height) + 1;
	return k1;                //原本k3连接k2,现在k1替换k2的位置,改为k3连接k1,k1要与原来k2的位置比较
                              //返回k1的目的是插入时要对k1和k3的连接操作
}

 RR型：左旋 

LPNODE RR_Rotation(LPNODE k1) 
{
	LPNODE  k2=k1->RChild;
	k1->RChild = k2->LChild;    //k1的右边变成原来k2的左边
	k2->LChild = k1;            //k2的左边变成k1
    //k1的左边和右边做比较
	k1->height = MAX(HEIGHT(k1->LChild), HEIGHT(k1->RChild)) + 1;
	k2->height = MAX(HEIGHT(k2->RChild), k1->height) + 1;
	return k2;
}

 LR：左旋 + 右旋

LPNODE LR_Rotation(LPNODE k3) 
{
    //先做左旋--->调用左旋函数把[k3的左子树]变成左旋后的结果
	k3->LChild = RR_Rotation(k3->LChild);
    //再做右旋--->针对k3做右旋
	return LL_Rotation(k3);
}

 RL：右旋 + 左旋

LPNODE RL_Rotation(LPNODE k3) 
{
	k3->RChild = LL_Rotation(k3->RChild);
	return RR_Rotation(k3);
}

AVL的插入操作

在AVL树中新插入一个元素，我们有三个要思考的点：

• 新元素插在树那个位置上
• 新插入的元素可能会导致原有结点的高发生变化
• 是否出现不平衡,怎么去维护平衡
• 对一棵树的右子树做插入：刚刚是平衡的，往右边插入一个元素，只要检查右子树高度是否大于左子树加1 HEIGHT(tree->RChild) - HEIGHT(tree->LChild) >1 或者 HEIGHT(tree->RChild) - HEIGHT(tree->LChild) == 2 ，肯定是右边比左边高，不可能左边比右边高  往右边做插入只有两种情况：RR型、RL型
• 对一棵树的左子树做插入，交换 tree->LChild 和tree->RChild 的位置即可 往右边做插入只有两种情况：LL型、LR型

//要插入的树 要插入的数据
AVLTree insertNode(AVLTree tree, DATA data) 
{
	if (tree == NULL) 
	{
		tree = createNode(data);          //树为空插入的节点成为根节点
	}
    //判断数据是往左边走还是往右边走 
	else if (data.key < tree->data.key)   //插在左边
	{
		tree->LChild = insertNode(tree->LChild, data);
		//根据节点高度去调整 相减等于2说明是一种要调整的状态 [高度差只能是1] 左边高于右边
		if (HEIGHT(tree->LChild) - HEIGHT(tree->RChild) == 2)
		{
            //判断是插在tree->LChild的左边还是右边 是需要右旋还是需要左旋+右旋?
			if (data.key < tree->LChild->data.key)    //插在左边LL型
			{
				tree = LL_Rotation(tree);             //右旋
			}
			else                                      //当前节点是放在在右边LR型
			{
				tree = LR_Rotation(tree);
			}
		}
	}
	else if (data.key > tree->data.key)   //插在右边
	{
		tree->RChild = insertNode(tree->RChild, data);
		//根据节点高度去调整 右边高于左边
		if (HEIGHT(tree->RChild) - HEIGHT(tree->LChild) == 2) 
		{
            //判断是插在tree->RChild的左边还是右边 是需要左旋还是需要右旋+左旋?
			if (data.key > tree->RChild->data.key)    //RR型
			{
				tree = RR_Rotation(tree);
			}
			else                                      //RL型
			{
				tree = RL_Rotation(tree);             //右旋+左旋
			}
		}
	}
	else								  //如果存在相同的键提示键唯一
	{
		printf("关键字唯一!\n");
	}
    //设置高度--->直接获取当前节点左子树的高度和右子树的高度,当前节点的高度就是它左右子树高度中比较大的那个+1
	tree->height = MAX(HEIGHT(tree->LChild), HEIGHT(tree->RChild)) + 1;
	return tree;
}

 测试代码

int  main() 
{
	DATA data[10] = { 3,"张三",2,"李四",1,"王五",4,"赵六",
	5,"小黑",6,"狗蛋",7,"老王",16,"小白",15,"五三",14,"小刚" };
	AVLTree root = NULL;                    //创建平衡二叉树
	for (int i = 0; i < 10; i++)            
	{
		root = insertNode(root, data[i]);   //插入数据
	}
	preOrder(root);                         //前序遍历树
	return 0;
}
/*输出*/
4:赵六    高度:3    //从第0层开始
2:李四    高度:1
1:王五    高度:0
3:张三    高度:0
7:老王    高度:2
6:狗蛋    高度:1
5:小黑    高度:0
15:五三   高度:1
14:小刚   高度:0
16:小白   高度:0

 AVL的递归查找操作

//要找的树 通过关键字做查找
LPNODE searchTree(AVLTree tree, int key) 
{
	if (tree == NULL || tree->data.key == key) //唯一退出性条件 1.等于NULL 2.键相等
	{
		return tree;
	}
	if (key < tree->data.key)                  //小于的情况往左边走
	{
		return searchTree(tree->LChild, key);
	}
	else 
	{
		return searchTree(tree->RChild, key);  //大于的情况往右边走
	}
}
//测试代码
	LPNODE result = searchTree(root, 15);
    printf("--------------\n");
    printCurNode(result);
	printf("--------------\n");
--------------
15:五三  高度:1
--------------

 找最小节点 - - - > 右边找最左边

LPNODE minKeyNode(LPNODE tree) 
{
	if (tree == NULL)
		return NULL;
	while (tree->LChild != NULL) 
	{
		tree = tree->RChild;
	}
	return tree;
}

 找最大节点- - - > 左边找最右边

LPNODE maxKeyNode(LPNODE tree) 
{
	if (tree == NULL)
		return NULL;
	while (tree->RChild != NULL)    
   		tree = tree->LChild;
	return tree;
}

AVL的删除操作

1.首先要知道当删除某个结点，我们需要用什么结点去替换删除结点的位置？

• 删除结点没有左右孩子
  相当于删除结点是叶子结点，直接删除，没有任何影响
• 删除结点没有左孩子 | 只有右孩子
  使用其右孩子去替代原删除结点的位置
• 删除结点没有右孩子 | 只有左孩子
  使用其左孩子去代替原删除结点的位置
• 删除结点左右孩子都有
  使用其前趋结点或后继结点代替删除结点的位置
• 删除 tree 节点，只要在剩下节点中找一个最大的当做它的替身，没有创建新的节点而是把数据挪上来覆盖要删除的节点
• AVL树中任何节点的两个子树的高度最大差别为1，一旦判断高度差为2就需要调整高度

2.什么是前趋结点，什么是后继结点？

• 当删除结点左右孩子都有的时候，用于替代删除结的替代结点，可以是删除结点的后继结点, 也可以是前趋结点
• 后继结点是删除结点的右子树的最小值结点
• 前趋结点是删除结点的左子树的最大值结点

3.整个删除大致步骤：

• 1.传入要删除的数据，从根结点开始递归遍历匹配结点
• 2.找到匹配结点之后，分为四种情况去删除
• 删除结点没有左右孩子 => 直接删除
• 删除结点没有左孩子 | 只有右孩子 => 用右孩子去代替
• 删除结点没有右孩子 | 只有左孩子 => 用左孩子去代替
• 删除结点左右孩子都有 =>用后继结点去代替
• 3.删除结点之后，需要更新删除所有相关结点的高
• 4.还需要判断删除结点之后，是否发生不平衡现象,如果发生不平衡现象，就要根据LL,LR,RR,RL四种情况去解决问题

//要删除的树 通过键去做删除
LPNODE deleteNode(AVLTree tree, int key)
{
	if (tree == NULL)            //树为空无法做删除
	{
		return NULL;
	}
    //找指定节点 判断是往左边走还是往右边走 递归调用 一旦递归调用结束代表找到了指定节点
	if (key < tree->data.key)
	{
		tree->LChild = deleteNode(tree->LChild, key);    //接着往左边走
		if (HEIGHT(tree->RChild) - HEIGHT(tree->LChild) == 2) //考虑是RL还是RR
		{
			LPNODE rightNode = tree->RChild;             //右边的节点
			if (HEIGHT(rightNode->LChild)>HEIGHT(rightNode->RChild)) 
			{
				tree = RL_Rotation(tree);
			}
			else 
			{
				tree = RR_Rotation(tree);
			}
		}
 
	}
	else if (key > tree->data.key)
	{
		tree->RChild = deleteNode(tree->RChild, key);
		if (HEIGHT(tree->LChild) - HEIGHT(tree->RChild) == 2) //考虑是LR还是LL
		{
			LPNODE leftNode = tree->LChild;
			if (HEIGHT(leftNode->RChild) > HEIGHT(leftNode->LChild)) 
			{
				tree = LR_Rotation(tree);
			}
			else 
			{
				tree = LL_Rotation(tree);
			}
		}
	}
	else //删除后的调整--->分两种情况去替换节点 1.只有单边的情况 2.左右子树健全的情况
	{
		if (tree->LChild != NULL && tree->RChild != NULL) 
		{
            //树的高度的作用:当前节点是否存在左右子树
			if (HEIGHT(tree->LChild) > HEIGHT(tree->RChild)) 
			{    
                //从左边找最大的节点
				LPNODE max = maxKeyNode(tree->LChild);
				tree->data = max->data; //把左边元素最大的值直接覆盖要删除节点的数据
                //针对max->data做递归删除 
				tree->LChild = deleteNode(tree->LChild, max->data.key);
			}
			else //往右边拿右边最小的
			{
				LPNODE min = minKeyNode(tree->RChild);
				tree->data = min->data;
                //递归删除
				tree->RChild = deleteNode(tree->RChild, min->data.key);
			}
		}
		else    //只有一边的情况 判断是左边还是右边
		{
			LPNODE temp = tree;
			tree = tree->LChild ? tree->LChild : tree->RChild; //连接
			free(temp);
			temp = NULL;
		}
	}
	return tree;
}
//测试代码
    deleteNode(root, 7);
	preOrder(root);
4:赵六    高度:3    //从第0层开始
2:李四    高度:1
1:王五    高度:0
3:张三    高度:0
14:小刚   高度:0
6:狗蛋    高度:1
5:小黑    高度:0
15:五三   高度:1
16:小白   高度:0

部分内容参考自：

【数据结构】初入数据结构中的平衡二叉搜索树(AVL树)及Java实现_长路漫漫的歇脚处-CSDN博客

 树的高度和深度概念_行者有疆哉-CSDN博客_树的深度是什么