AVL平衡二叉树C++代码实现

总结

  1. 什么是平衡二叉树

    • 基于二叉排序树
    • 左右子树的深度之差的绝对值不超过1
    • 左右子树都是平衡二叉树
  2. 为什么要修改二叉排序树为平衡二叉树:因为查找二叉树的比较次数和层数有关

  3. 在构造二叉排序树的过程中,会出现四种失衡现象
    AVL平衡二叉树C++代码实现

  4. 如何进行调整:找到最小不平衡子树,将其调平衡

    • 最小不平衡子树:离插入节点最近且平衡因子绝对值超过1的结点,以这个结点为根节点的子树
  5. LL型:右旋,原本橙点是root,右旋后,绿点是root,橙点为绿点的right

    • 注意:绿点的right可能有结点,所以要用橙点的left接上
    • 以上图第三个为例
      AVL平衡二叉树C++代码实现
  6. RR型:左旋,原本橙点是root,左旋后,绿点是root,橙点为绿点的left

    • 注意:绿点的left可能有结点,所以要用橙点的right接上
    • 以上图第三个为例
      AVL平衡二叉树C++代码实现
  7. LR型:双旋,先对绿点(LL中的橙点)和蓝点(LL中的绿点)进行RR左旋,在对橙点进行LL右旋

    • 解释:左旋使LR型变为LL型,右旋使LL型平衡
    • 注意:对两个点也能进行RR左旋
      AVL平衡二叉树C++代码实现
      AVL平衡二叉树C++代码实现
  8. RL型:和LR型对称操作

代码思路

  1. 注意过程中要对树进行操作的函数的参数一定要传入指针的引用
  2. 递归插入结点insert
    • 如果curr为空,即找到最终位置,申请内存新建节点
    • 如果传入参数num小于当前结点的data,递归进入左子树
    • 如果传入参数num大于当前节点的data,递归进入右子树
  3. 插入结点后,就要退出递归,进行平衡因子的更新
    • 通过getHeight即可得到左子树和右子树的高度
    • 若平衡因子<1,继续退出递归
    • 若平衡因子>1,即不平衡,就要判断不平衡的类型了
      • 由第一张图可得,RX型橙点-2,LX型橙点2
      • RL型绿点1,RR型绿点-1,LR型绿点-1,LL型绿点1
      • 每个类型都有自己的特征,进入if判断
  4. 右旋要注意绿点的right,左旋要注意绿点的left
  5. 插入节点后和调平衡后,要更新改变过的结点的高度,绿点和橙点

代码

#include <iostream>
#include <vector>
using namespace std;
struct treeNode {
	int data;
	int height;
	treeNode* left, * right;
};
//中序遍历
void inorderTra(treeNode* curr) {
	if (!curr) return;
	inorderTra(curr->left);
	cout << curr->data << " ";
	inorderTra(curr->right);
}
//递归获取高度
int getHeight(treeNode* curr) {
	if (!curr) return -1;
	return curr->height;
}
//LL型,右旋单旋
treeNode* LL(treeNode*& curr) {
	treeNode* leftNode = curr->left;
	curr->left = leftNode->right;
	leftNode->right = curr;
	curr = leftNode;
	curr->height = max(getHeight(curr->left), getHeight(curr->right)) + 1;
	//可能为空,但不为空要重新判断高度
	if(curr->left) curr->left->height = max(getHeight(curr->left->left), getHeight(curr->left->right)) + 1;
	return curr;
}
//RR型,左旋单旋
treeNode* RR(treeNode*& curr) {
	treeNode* rightNode = curr->right;
	curr->right = rightNode->left;
	rightNode->left = curr;
	curr = rightNode;
	curr->height = max(getHeight(curr->left), getHeight(curr->right)) + 1;
	//可能为空,但不为空要重新判断高度
	if(curr->right) curr->right->height = max(getHeight(curr->right->left), getHeight(curr->right->right)) + 1;
	return curr;
}
//LR型,先对左子树右旋再左旋
treeNode* LR(treeNode*& curr) {
	RR(curr->left);
	return LL(curr);
}
//RL型,先对右子树左旋再右旋
treeNode* RL(treeNode*& curr) {
	LL(curr->right);
	return RR(curr);
}
//插入叶子结点,递归
//注意使用指针的引用
void insert(int num, treeNode*& curr) {
	//如果为空,即找到了叶子结点的位置,分配空间
	if (!curr) {
		curr = new treeNode();
		curr->data = num;
		curr->left = NULL;
		curr->right = NULL;
	}
	//如果数字比当前结点的值小,即进入当前结点的左子树继续判断
	else if (num < curr->data) {
		insert(num, curr->left);
		//递归出来后,要判断平衡因子,决定是否调平衡
		if (getHeight(curr->left) - getHeight(curr->right) == 2) {
			//如果上面递归是进入了左子树的左子树,则是LL型
			if (num < curr->left->data) curr = LL(curr);
			//如果进入左子树的右子树,则是LR型
			else curr = LR(curr);
		}
	}
	//如果数字比当前节点的值大,即进入当前节点的右子树继续判断
	else if (num > curr->data) {
		insert(num, curr->right);
		//递归出来后,要判断平衡因子,决定是否调平衡
		if (getHeight(curr->left) - getHeight(curr->right) == -2) {
			//如果上面递归是进入了右子树的右子树,则是RR型
			if (num > curr->right->data) curr = RR(curr);
			//如果进入右子树的左子树,则是RL型
			else curr = RL(curr);
		}
	}
	curr->height = max(getHeight(curr->left), getHeight(curr->right)) + 1;
}
void createTree(vector<int> v, treeNode*&pRoot) {
	for (int i = 0; i < v.size(); i++) {
		insert(v[i], pRoot);
	}
	//中序遍历,平衡二叉树是特殊的二叉排序树
	inorderTra(pRoot);
}
int main() {
	vector<int> v = { 49,38,65,97,76,13,27 };
	treeNode* pRoot = NULL;
	createTree(v,pRoot);
	return 0;
}

结果

AVL平衡二叉树C++代码实现

上一篇:AVL树


下一篇:AVL添加(c语言)