一起学习交流~

AVL树

算法 laomuji 11个月前 (10-29) 437次浏览 已收录 0个评论

一、AVL树的特点

AVL树本质上还是一棵二叉查找树 ,它的特点是:
1.本身首先是一棵二叉查找树 。
2.带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。
也就是说,AVL树,本质上是带了平衡功能的二叉查找树(二叉排序树,二叉搜索树)。

简单来说,就是和普通二叉排序树很像,但是它是平衡的

因为普通的二叉排序树在极端情况下,会变成一条链表退化为o(n)的复杂度

AVL树在插入的时候进行旋转,达到平衡

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)

理论上和红黑树时间效率一样,但是实际效率要比红黑树差一些

二、什么是不平衡和平衡

不平衡就是左右孩子的高度差值大于1

平衡就是左右孩子的高度差值小于等于1

三、旋转的四种情况

右旋,一直插入比较小的值,需要将左边的孩子旋转上去

左旋 ,一直插入比较大的值,需要将右边的孩子旋转上去

先左旋再右旋 ,

当需要右旋时,左孩子的右孩子-左孩子的左孩子的高度差为1时

需要先左旋变成递减的状态再右旋,如果只是单纯的右旋,结果会导致另一边不平衡

先右旋再左旋

当需要左旋时,右孩子的左孩子-右孩子的右孩子的高度差为1时

需要先右旋变成递增的状态再左旋,如果只是单纯的左旋,结果会导致另一边不平衡

四、其它操作

没什么好注意的 和二叉查找树一样,

找到处理的节点,

若高度差大于1,进行旋转调整

再往上递归更新高度直到根节点

五、代码

AVLTree.h

#pragma once
#include<vector>
#include<queue>
using namespace std;
class AVLTree
{
private:


public:
	struct AVLNode
	{
		int value;
		struct AVLNode* left;
		struct AVLNode* right;
		int height;
	};
	struct AVLNode* root = nullptr;
	AVLTree()
	{
		root = nullptr;
	}

	//广度遍历
	vector<pair<AVLNode*, int>>breadth()
	{
		queue<pair<AVLNode*, int>>queueNode;//用于存放节点
		vector<pair<AVLNode*, int>>rVector;//用于返回先序遍历的数据
		if (root != nullptr)queueNode.push(pair<AVLNode*, int>(root, 0));//压入根节点
		//循环出队
		while (queueNode.size() > 0)
		{
			//先出队
			pair<AVLNode*, int> temp = queueNode.front();
			queueNode.pop();

			rVector.push_back(pair<AVLNode*, int>(temp.first, temp.second));

			//把左孩子右孩子放入队列
			if (temp.first->left != nullptr)queueNode.push(pair<AVLNode*, int>(temp.first->left, temp.second + 1));
			if (temp.first->right != nullptr)queueNode.push(pair<AVLNode*, int>(temp.first->right, temp.second + 1));
		}
		return rVector;
	}


	//向AVL树中插入数据
	void insert(int value)
	{
		root = insertAVLNode(value, root);
	}

	//删除AVL树中的数据,成功返回1 失败返回0
	void remove(int value)
	{
		 root = removeAVLNode(value,root);
	}

private:
	//返回两个高度中最大的高度
	int maxHeight(struct AVLNode* a, struct AVLNode* b)
	{
		int value1 = 0;
		int value2 = 0;
		if (a != nullptr)value1 = a->height;
		if (b != nullptr)value2 = b->height;
		return value1 > value2 ? value1 : value2;
	}
	//获取节点高度
	int getHeight(struct AVLNode* node)
	{
		if (node == nullptr)return 0;
		return node->height;
	}
	//左旋
	struct AVLNode* leftRotate(struct AVLNode* head)
	{
		struct AVLNode* temp = head->right;
		head->right = temp->left;
		temp->left = head;
		//更新高度,因为旋转了,所以高度也变了
		head->height = maxHeight(head->left, head->right) + 1;
		return temp;
	}
	//右旋
	struct AVLNode* rightRotate(struct AVLNode* head)
	{
		struct AVLNode* temp = head->left;
		head->left = temp->right;
		temp->right = head;
		//更新高度,因为旋转了,所以高度也变了
		head->height = maxHeight(head->left, head->right) + 1;
		return temp;
	}
	//对二叉树进行平衡操作
	struct AVLNode* adjust(struct AVLNode* node)
	{
		if (node == nullptr)return node;
		//如果右边-左边等于2表示右边的子树需要左旋
		if (getHeight(node->right) - getHeight(node->left) == 2)
		{
			//需要先右旋的情况
			if (getHeight(node->right->left) - getHeight(node->right->right) == 1)node->right = rightRotate(node->right);
			//进行左旋
			return leftRotate(node);
		}
		//如果左边-右边等于2表示右边的子树需要右旋
		if (getHeight(node->left) - getHeight(node->right) == 2)
		{
			//需要先左旋的情况
			if (getHeight(node->left->right) - getHeight(node->left->left) == 1)node->left = leftRotate(node->left);
			//右旋
			return  rightRotate(node);
		}
		return node;
	}
	//插入数据,递归旋转,递归更新高度
	struct AVLNode* insertAVLNode(int value, struct AVLNode* temp)
	{
		//节点不存在则新建节点并返回
		if (temp == nullptr)return new AVLNode{ value,nullptr,nullptr,1 };
		//找到需要插入的位置
		if (value < temp->value)
		{
			//往左找
			temp->left = insertAVLNode(value, temp->left);
		}
		else if (value > temp->value)
		{
			//往右找
			temp->right = insertAVLNode(value, temp->right);
		}
		else
		{
			//相等,不允许插入,直接返回
			return temp;
		}
		//调整旋转
		temp = adjust(temp);
		//更新高度
		temp->height = maxHeight(temp->left, temp->right) + 1;
		return temp;
	}


	//二叉树删除,成功返回1失败返回0
	struct AVLNode* removeAVLNode(int value, struct AVLNode* node)
	{
		if (node == nullptr)return node;
		struct AVLNode* rNode = node;
		//如果当前节点是需要删除的节点
		if (node->value == value)
		{
			//1.若要删除的是叶子节点
			if (node->left == nullptr && node->right == nullptr)
			{
				delete node;
				rNode = nullptr;
			}
			//2.若要删除的节点只有左孩子或右孩子
			//只有左孩子
			else if (node->left != nullptr && node->right == nullptr)
			{
				rNode = node->left;
				delete node;
			}
			//只有右孩子
			else if (node->left == nullptr && node->right != nullptr)
			{
				rNode = node->right;
				delete node;
			}
			//3.既有左孩子也有右孩子
			else if (node->left != nullptr && node->right != nullptr)
			{
				AVLNode* leftMax = node->left;
				while (leftMax->right != nullptr)
				{
					leftMax = leftMax->right;
				}
				//现在 leftMax为左孩子中最大的
				//把leftMax复制到当前
				node->value = leftMax->value;

				//再把leftMax删掉即可
				node->left = removeAVLNode(leftMax->value,node->left);
				if(node->left!=nullptr)node->left->height = maxHeight(node->left->left, node->left->right) + 1;
				rNode = node;
			}
			adjust(rNode);
			return rNode;
		}
		//除了等于 那么就只有小于和大于了
		if (value < node->value) node->left = removeAVLNode(value, node->left);
		else node->right = removeAVLNode(value, node->right);
		return node;
	}
	public:
	int getMaxDepth(AVLNode* node) {
		if (node == nullptr)return 0;
		if (node->left == nullptr && node->right == nullptr)return 1;
		int leftDepth = getMaxDepth(node->left);
		int rightDepth = getMaxDepth(node->right);
		if (leftDepth > rightDepth)return leftDepth + 1;
		else return rightDepth + 1;
	}


};

main.cpp

/*
AVL树是最先发明的自平衡二叉搜索树
AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)
*/

#include<iostream>
#include"AVLNode.h"
using namespace std;

int nums[] = { 3,1,7,6,5,4 };
int numSize = sizeof(nums) / sizeof(int);

void main()
{
	AVLTree tree;
	for (int i = 0; i < numSize; i++)
	{
		cout << "insert:" << nums[i] << endl;
		tree.insert(nums[i]);
	}

	vector<pair<AVLTree::AVLNode*, int>>v=tree.breadth();
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << "value:" << v[i].first->value<<" "<< v[i].first->left<<" "<<v[i].first->right << " height:" << v[i].first->height << " depth:" << v[i].second << endl;
	}
	tree.remove(5);
	cout << endl;
	v = tree.breadth();
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << "value:" << v[i].first->value << " " << v[i].first->left << " " << v[i].first->right << " height:" << v[i].first->height << " depth:" << v[i].second << endl;
	}

	for (int i = 0; i < 100000; i++)tree.insert(i);
	cout << "value:" << tree.root->value << " " << tree.root->left << " " << tree.root->right << " height:" << tree.root->height<<" "<< tree.getMaxDepth(tree.root) << endl;
	
	//当最大层数和根节点的高度相同时,表明删除没有问题,是平衡的
	while (1)
	{
		cout << "开始删除" << endl;
		for (int i = 0; i < 100000/5; i++) {
			if(tree.root!=nullptr)
			tree.remove(tree.root->value);
		}
		v = tree.breadth();
		cout << "当前最大层数:" << tree.getMaxDepth(tree.root) << endl;
		if (v.size()) {
			cout << "value:" << tree.root->value << " " << tree.root->left << " " << tree.root->right << " height:" << tree.root->height << " " << tree.getMaxDepth(tree.root) << endl;
		}
		else
		{
			cout << "删除完毕" << endl;
			break;
		}
	}


}
喜欢 (1)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论