当前位置： 首页 > article >正文

【数据结构】平衡二叉树

article 2024/12/23 17:18:08

目录

一、概念

二、平衡二叉树的插入

（一）插入步骤

（二）旋转

1、左旋

2、右旋

3、左右双旋

4、右左双旋

三、特点

四、整体代码

一、概念

        平衡二叉树是在二叉搜索树的改进，二叉搜索树详见：【数据结构】二叉搜索树-CSDN博客

        若使用递增序列持续插入构建二叉搜索树，会导致二叉搜索树严重不平衡，查找效率退化至O（N），即失去了二叉搜索树的优势。

        因此为了提高查找效率，引入了平衡二叉树：在一棵搜索二叉树中每个节点的左右子树的高度差的绝对值不超过1。左右子树的高度差称为平衡因子，平衡因子=右子树高度-左子树高度，当然左子树高度-右子树高度也是能满足需求的。

        本文仅对平衡二叉树的插入部分进行讲解。而对平衡二叉树节点进行删除：先按照二叉搜索树的特性寻找目标节点，删除节点后更新平衡因子时，平衡因子为1或-1便可以停止向上更新。当平衡因子绝对值大于1时，同样需要进行旋转解决。

        平衡二叉树在通过大量的旋转控制整颗树任意一个节点的左右子树高度差不大于1，使树的结构近似完全二叉树，极大地提高了搜索效率。但是因为频繁地旋转会导致其插入删除地效率不高。

二、平衡二叉树的插入

          本文中定义节点的数据结构：

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K, V>& data = K())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<K, V>* _pLeft;
	AVLTreeNode<K, V>* _pRight;
	AVLTreeNode<K, V>* _pParent;
	pair<K, V> _data;
	int _bf;   // 节点的平衡因子
};

（一）插入步骤

        平衡二叉树的插入和二叉搜索树的插入步骤在寻找节点及插入节点时完全相同，只是平衡二叉树书多了平衡因子的更新以及旋转部分。

        首先依靠二叉搜索树的特性寻找插入位置。在找到目标位置后插入元素并维护其与父节点的指针关系。在本文采用 平衡因子=右子树高度-左子树高度 ，因此根据插入节点位置更新父节点的平衡因子并判断是否需要旋转调整平衡。

        以上两种情况，情况一插入更新完节点平衡因子后无需旋转调整，而情况二插入后平衡因子异常需要旋转调整。

        插入的情况其实简单可以分为四种情况：

（二）旋转

         当出现上图情况时，就需要对平衡二叉树的节点进行旋转，旋转的目的是要让这颗树继续维持平衡二叉树的形态，同时调节子树的高度，让其和插入前的高度保持一致，旋转后不要忘记更新那些被旋转的节点的平衡因子。    

        实际对于平衡二叉树插入节点来说，经过旋转后子树的高度没有变化，因此无需向上检查平衡因此是否异常。

1、左旋

        上图是左旋的示意图，节点60不一定为该树的根，也可能是子树，我们将发生平衡因子异常的最小子树的根暂称为根，也就是上图的节点60，将该子树中的节点90暂称为父节点，下文中不进行赘述了。

        上图中插入节点后，节点60的平衡因子异常，因为节点60的平衡因子为2且节点90的平衡因子为1，因此判断插入的位置为节点90的右子树中，故需要左旋调整子树，将节点90的左子树托孤给节点60的右指针，再将节点60作为节点90的左孩子。经过调整后该子树高度不变且满足二叉平衡树的特性。

// 左单旋
void RotateL(Node* pParent)
{
	Node* parent = pParent;
    //记录节点90的父节点
    //旋转后需要维护子树与父节点的连接关系
	Node* pNode = parent->_pParent;
	Node* subR = parent->_pRight;

    //将60的左孩子托孤给90的右指针
	parent->_pRight = subR->_pLeft;

    //60的左孩子可能为空 因此只要不为空时需要维护其与父节点90的连接关系
	if (subR->_pLeft)
		subR->_pLeft->_pParent = parent;

    //节点60的左指针指向节点90
	subR->_pLeft = parent;
	parent->_pParent = subR;
    
    //维护整棵子树与上层父节点的关系
	if (pNode == nullptr)
	{
		_pRoot = subR;
		subR->_pParent = nullptr;
	}
	else
	{
		if (pNode->_pLeft == parent)
		{
			pNode->_pLeft = subR;
		}
		else
		{
			pNode->_pRight = subR;
		}
		subR->_pParent = pNode;
	}
    //更新平衡因子
	parent->_bf = 0;
	subR->_bf = 0;
}

2、右旋

         上图中插入节点后，节点90的平衡因子异常，因为节点90的平衡因子为-2且节点60的平衡因子为-1，因此判断插入的位置为节点60的左子树中，故需要右旋调整子树，将节点60的右子树托孤给节点90的右指针，再将节点90作为节点60的右孩子。经过调整后该子树高度不变且满足二叉平衡树的特性。

void RotateR(Node* pParent)
{
	Node* parent = pParent;
	//记录节点90的父节点
    Node* pNode = parent->_pParent;
	Node* subL = parent->_pLeft;
    
    //将节点60的右孩子托孤给节点90的左指针
	parent->_pLeft = subL->_pRight;
	if (subL->_pRight)
		subL->_pRight->_pParent = parent;

    //节点60的右指针指向节点90
	subL->_pRight = parent;
	parent->_pParent = subL;

    //维护整棵子树与节点的连接关系
	if (pNode == nullptr)
	{
		_pRoot = subL;
		subL->_pParent = nullptr;
	}
	else
	{
		if (pNode->_pLeft == parent)
		{
			pNode->_pLeft = subL;
		}
		else
		{
			pNode->_pRight = subL;
		}
		subL->_pParent = pNode;
	}
    //更新平衡因子
	parent->_bf = 0;
	subL->_bf = 0;
}

3、左右双旋

        上图中插入节点，节点90的平衡因子异常，因为节点90的平衡因子为-2且节点30的平衡因子为1，因此判断插入节点的位置在节点30的右子树中并记录插入后节点60的平衡因子，故需要进行左右双旋调整子树。

        首先进行左旋：将节点60的左子树托孤给节点30的右指针，节点90的左指针指向节点60，而节点60的左指针指向节点30。其次再进行右旋：将节点60的右子树托孤给节点90的左指针，节点60的右指针指向节点90。

        上述过程实际可以直接简化为将节点60的左子树托孤给节点30的右指针，将节点60的右子树托孤给节点90的左指针，将节点60的左指针指向节点30，节点60的右指针指向节点90。完成旋转后根据先前记录的平衡因子再更新节点30和节点90的平衡因子：

        （1）若节点60的平衡因子为1，说明插入节点为节点60的右孩子，进行旋转后节点30的平衡因子为-1，节点90的平衡因子为0；

        （2）若节点60的平衡因子为-1，说明插入节点为节点60的左孩子，进行旋转后节点30的平衡因子为0，节点90的平衡因子为1；

        （3）若节点60的平衡因子为0，说插入的节点就是为节点60，进行旋转后节点30、60和90的平衡因子都为0。

        经过调整后该子树高度不变且满足二叉平衡树的特性。

// 左右双旋
void RotateLR(Node* pParent)
{
    //记录旋转前的节点
	Node* parent = pParent;
	Node* subL = parent->_pLeft;
	Node* subLR = subL->_pRight;
    //记录节点60的平衡因子
	int bf = subLR->_bf;

	RotateL(parent->_pLeft);
	RotateR(parent);
    
    //根据60的平衡因子更新节点30、60和90的平衡因子
	if (bf == 1)
	{
		parent->_bf = 0;
		subLR->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

4、右左双旋

        

        上图中插入节点，节点30的平衡因子异常，因为节点30的平衡因子为2且节点90的平衡因子为-1，因此判断插入节点的位置在节点90的左子树中并记录插入后节点60的平衡因子，故需要进行右左双旋调整子树。

        首先进行右旋：将节点60的右子树托孤给节点90的左指针，节点30的右指针指向节点60，而节点60的右指针指向节点90。其次再进行左旋：将节点60的左子树托孤给节点30的右指针，节点60的左指针指向节点30。

        上述过程实际可以直接简化为将节点60的左子树托孤给节点30的右指针，将节点60的右子树托孤给节点90的左指针，将节点60的左指针指向节点30，节点60的右指针指向节点90。完成旋转后根据先前记录的平衡因子再更新节点30和节点90的平衡因子：

        （1）若节点60的平衡因子为1，说明插入节点为节点60的右孩子，进行旋转后节点30的平衡因子为-1，节点90的平衡因子为0；

        （2）若节点60的平衡因子为-1，说明插入节点为节点60的左孩子，进行旋转后节点30的平衡因子为0，节点90的平衡因子为1；

        （3）若节点60的平衡因子为0，说插入的节点就是为节点60，进行旋转后节点30、60和90的平衡因子都为0。

        经过调整后该子树高度不变且满足二叉平衡树的特性。

// 右左双旋
void RotateRL(Node* pParent)
{
    //记录旋转前的节点
	Node* parent = pParent;
	Node* subR = parent->_pRight;
	Node* subRL = subR->_pLeft;
	//记录节点60的平衡因子
    int bf = subRL->_bf;

    //复用之前的代码
	RotateR(parent->_pRight);
	RotateL(parent);

    //根据60的平衡因子更新节点30、60和90的平衡因子
	if (bf == 1)
	{
		parent->_bf = -1;
		subRL->_bf = 0;
		subR->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 0;
		subRL->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subRL->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
	
}

三、平衡二叉树的检测       

// AVL树的验证
bool IsAVLTree()
{
	return _IsAVLTree(_pRoot);
}
// 根据AVL树的概念验证pRoot是否为有效的AVL树
bool _IsAVLTree(Node* pRoot)
{
	if (pRoot == nullptr)
		return true;
	int left = _Height(pRoot->_pLeft);
	int right = _Height(pRoot->_pRight);
	if (right - left != pRoot->_bf)
	{
		cout << pRoot->_data.first << "平衡因子异常" << endl;
		return false;
	}
	return (abs(right - left) < 2) 
    && _IsAVLTree(pRoot->_pLeft) 
    && _IsAVLTree(pRoot->_pRight);
}
size_t _Height(Node* pRoot)
{
	if (pRoot == nullptr)
		return 0;
	return (_Height(pRoot->_pLeft) > _Height(pRoot->_pRight) ? 
_Height(pRoot->_pLeft) + 1 : _Height(pRoot->_pRight) + 1);
}

        平衡二叉树的检测就是对平衡因子的检查，不仅仅是检查平衡因子的值是否在[-1， 1]的范围内，还要检查平衡因子的值是否有效。采用递归的方式去求得左子树和右子树的高度，二者相减得出实际的平衡因子。将得出的平衡因子和记录的平衡因子作比较，若不符合则返回 false，若成功则递归检查其他节点。

四、整体代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K, V>& data = K())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<K, V>* _pLeft;
	AVLTreeNode<K, V>* _pRight;
	AVLTreeNode<K, V>* _pParent;
	pair<K, V> _data;
	int _bf;   // 节点的平衡因子
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	AVLTree()
		: _pRoot(nullptr)
	{}
	//中序遍历
	void Inorder()
	{
		_Inorder(_pRoot);
	}
	// 在AVL树中插入值为data的节点
	bool Insert(const pair<K, V>& data)
	{
		if (_pRoot == nullptr)
		{
			_pRoot = new Node(data);
			return true;
		}
		Node* cur = _pRoot;
		Node* parent = nullptr;
		//寻找插入位置	
		while (cur)
		{
			if (cur->_data.first < data.first)
			{
				parent = cur;
				cur = cur->_pRight;
			}
			else if (cur->_data.first > data.first)
			{
				parent = cur;
				cur = cur->_pLeft;
			}
			else
				return false;
		}
		cur = new Node(data);
		//插入节点
		if (cur->_data.first < parent->_data.first)
		{
			parent->_pLeft = cur;
		}
		else
		{
			parent->_pRight = cur;
		}
		cur->_pParent = parent;
		while (parent)
		{
			//平衡因子更新
			if (parent->_pRight == cur)
				parent->_bf++;
			else
				parent->_bf--;
			//判断是否需要旋转
			if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_pParent;
			}
			else if (parent->_bf == 0)
			{
				break;
			}
			else
			{
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else
				{
					assert(false);
				}
				break;
			}
		}
		return true;
	}

	// AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}

private:
	// 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsAVLTree(Node* pRoot)
	{
		if (pRoot == nullptr)
			return true;
		int left = _Height(pRoot->_pLeft);
		int right = _Height(pRoot->_pRight);
		if (right - left != pRoot->_bf)
		{
			cout << pRoot->_data.first << "平衡因子异常" << endl;
			return false;
		}
		return (abs(right - left) < 2) && _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
	}
	size_t _Height(Node* pRoot)
	{
		if (pRoot == nullptr)
			return 0;
		return (_Height(pRoot->_pLeft) > _Height(pRoot->_pRight) ? _Height(pRoot->_pLeft) + 1 : _Height(pRoot->_pRight) + 1);
	}
	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* parent = pParent;
		Node* pNode = parent->_pParent;
		Node* subL = parent->_pLeft;

		parent->_pLeft = subL->_pRight;
		if (subL->_pRight)
			subL->_pRight->_pParent = parent;

		subL->_pRight = parent;
		parent->_pParent = subL;

		if (pNode == nullptr)
		{
			_pRoot = subL;
			subL->_pParent = nullptr;
		}
		else
		{
			if (pNode->_pLeft == parent)
			{
				pNode->_pLeft = subL;
			}
			else
			{
				pNode->_pRight = subL;
			}
			subL->_pParent = pNode;
		}
		parent->_bf = 0;
		subL->_bf = 0;
	}
	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* parent = pParent;
		Node* pNode = parent->_pParent;
		Node* subR = parent->_pRight;

		parent->_pRight = subR->_pLeft;
		if (subR->_pLeft)
			subR->_pLeft->_pParent = parent;

		subR->_pLeft = parent;
		parent->_pParent = subR;

		if (pNode == nullptr)
		{
			_pRoot = subR;
			subR->_pParent = nullptr;
		}
		else
		{
			if (pNode->_pLeft == parent)
			{
				pNode->_pLeft = subR;
			}
			else
			{
				pNode->_pRight = subR;
			}
			subR->_pParent = pNode;
		}
		parent->_bf = 0;
		subR->_bf = 0;
	}
	// 右左双旋
	void RotateRL(Node* pParent)
	{
		Node* parent = pParent;
		Node* subR = parent->_pRight;
		Node* subRL = subR->_pLeft;
		int bf = subRL->_bf;

		RotateR(parent->_pRight);
		RotateL(parent);

		if (bf == 1)
		{
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
		
	}
	// 左右双旋
	void RotateLR(Node* pParent)
	{
		Node* parent = pParent;
		Node* subL = parent->_pLeft;
		Node* subLR = subL->_pRight;

		int bf = subLR->_bf;

		RotateL(parent->_pLeft);
		RotateR(parent);

		if (bf == 1)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	//中序遍历
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inorder(root->_pLeft);
		cout << root->_data.first << " ";
		_Inorder(root->_pRight);
	}

private:
	Node* _pRoot;
};

http://www.kler.cn/a/444041.html

相关文章：

  • JavaScript 中的 `parseInt()` 函数详解
  • CSS系列（30）-- 逻辑属性详解
  • 大腾智能CAD：国产云原生三维设计新选择
  • BERT的改进：ModernBERT
  • 如何测量分辨率
  • UE5 移植Editor或Developer模块到Runtime
  • 【Canvas与仪表盘】铝圈蓝底汽车速度仪表盘（可用键盘按键调节速度值）
  • 初学stm32 --- 外部中断
  • C语言与C++与Python与Java的差别
  • TCA9555芯片手册解读（6）
  • 2024年12月陪玩系统-仿东郊到家约玩系统是一种新兴的线上预约线下社交、陪伴系统分享-优雅草央千澈-附带搭建教程
  • upload-labs（1-19关）通关攻略
  • Vue零基础教程|从前端框架到GIS开发系列课程（六）组合式API
  • string
  • 【Web前端】Web API：构建Web应用核心
  • 6UCPCI板卡设计方案：8-基于双TMS320C6678 + XC7K420T的6U CPCI Express高速数据处理平台
  • docker拉取rabbitmq镜像安装延迟队列插件
  • 初学stm32 --- 系统时钟配置
  • 从零搭建CBAM、SENet、STN、transformer、mobile_vit、simple_vit、vit模型（Pytorch代码示例）
  • 多种机器学习模型预测房价
  • 力扣--LCR 129.字母迷宫
  • Go怎么做性能优化工具篇之pprof
  • C# 文件系统I/O操作--File类与FileInfo类
  • 【Tomcat】第三站：注解
  • 两款轻量级数据库SQLite 和 TinyDB，简单！实用！
  • thinkphp5验证码captcha无法显示