文章目录

• 1.AVL树概念
• 2. AVL树性质
• 3.AVL树的实现
• • insert
  • • 插入情况分析
    • 更新平衡因子
    • 旋转处理
    • • 左单旋
      • 右单旋
      • 在insert中判断左右单旋的条件
      • 双旋转
      • • 左右双旋
        • 右左双旋
        • • 插入引发双旋的场景
          • 中序遍历
          • 判断一颗二叉树是否为平衡树
          • 整体代码

            1.AVL树概念

            二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查

            找元素相当于在顺序表中搜索元素，效率低下,

            所以在此基础上提出解决办法：

            当向二叉搜索树中插入新节结点时，如果能保证每个节点的左右子树高度之差的绝对值不超过1即可降低树的高度，从而减少平均搜索长度

            AVL树又称平衡二叉搜索树

            2. AVL树性质

            AVL树的性质：

            1.它的左右子树都是AVL树

            2.左右子树高度之差(平衡因子)的绝对值不超过1(1/0/-1)

            平衡因子=右子树高度-左子树高度

            

            3.AVL树的实现

            在实现结构与插入功能时，与二叉搜索树有很多相似的地方 ：二叉搜索树

            所以一部分关于二叉搜索树的地方就不详细说了

            ---

            

            与二叉搜索树定义结构不同的是，多了一个父节点parent以及平衡因子bf

            insert

            

            insert的实现前半部分与二叉搜索树的insert实现大部分相同

            ---

            

            parent的右子树连接新节点为例，出while循环后，需要反向链接父节点，而此时的父节点就为刚才记录cur前一个节点的parent

            ---

            插入情况分析

            ---

            1.

            

            若新增节点作为parent的右子树即cur==parent->right

            parent的平衡因子+1 即 parent->bf++

            ---

            

            若新增节点作为parent的左子树即cur==parent->left

            parent的平衡因子 -1 即 parent->bf–

            ---

            3.

            

            若新增节点作为parent的左子树即cur==parent->left

            parent的平衡因子-1 即 parent->bf–

            ---

            若parent的平衡因子等于1或者-1 即第一种与第二种情况，说明parent所在子树变了，需要继续向上更新爷爷节点

            为什么需要继续更新？

            说明插入前parent的平衡因子为0，插入前左右高度相等，现在一边高1，高度变了

            若parent的平衡因子等于2或者-2 ， 说明parent所在子树不平衡，需要以旋转的方式处理子树

            若parent的平衡因子等于0， parent所在子树高度不变，就不需要向上更新，插入结束了

            为什么插入结束了呢？

            插入前parent的平衡因子是-1或者1，插入前一边高一边低，插入节点到矮的那边，高度不变

            更新平衡因子

            

            插入新增节点后，更新平衡因子

            如果更新之后，平衡因子没有问题(绝对值<=1)，说明插入对树的平衡机构没有影响，不需要处理

            如果更新之后，平衡出现问题，平衡结构受到影响(平衡因子为2/-2)，需要旋转

            插入新增节点，会影响部分/整体祖先

            旋转处理

            旋转的原则：保持继续是搜索树

            旋转的目的：左右均衡，降低高度

            ---

            

            a/b/c分别代表高度为h的AVL子树

            平衡因子=右子树深度-左子树深度

            ---

            情况1——h=0

            

            当h=0时，60的平衡因子：0-1=-1

            30的平衡因子：2-0=2

            由于平衡因子出现2，所以需要旋转

            ---

            情况2——h=1

            

            当h=2时，60的平衡因子:2-1=1，30的平衡因子:3-1=2

            由于平衡因子出现2，所以需要旋转

            在parent节点左右插入，都会引发平衡因子变为2

            ---

            情况3——h=2

            

            ---

            对于c来说，必定是x形状

            假设c为y形状

            

            在左子树新插入一个节点，那这颗子树的平衡因子变为-2，需要旋转，而不会去往上更新到30

            ---

            

            若右子树插入一个节点，parent的平衡因子变为0，不需要往上更新到30

            ---

            对于a和b，必定是x、y、z中的一种形状

            假设abc都是x形状，则在c中插入节点，无论插入左边还是右边，都会导致parent的平衡因子为2或者-2

            

            c的高度变化，必定引发旋转

            ---

            

            在红框中的四个位置任意一边插入，30的平衡因子都会变为2/-2

            虽然分为三种情况，但是旋转的规则是相同

            左单旋

            以h=1为例

            

            左单旋的旋转方式：

            把B变成30的右边，30变成60的左边，60变成整棵树的根

            ---

            左单旋抽象图

            

            

            父节点问题

            把subR作为30的右子树时，需要更新sub的父节点为parent

            把parent作为subR的左子树时，更新parent的父节点为subR

            有可能当前旋转的是整棵树或者整棵树的一部分

            设置一个ppnode，用于存放parent的父节点

            若旋转一部分时，跟ppnode相连接，同时也要判断连接到左子树还是右子树

            若旋转整棵树时，父节点置NULL，subR作为新的根

            ---

            右单旋

            

            在a处新增节点，使其高度变为h+1，造成旋转

            右单旋的旋转方式：

            b作为60的左边，60作为30的右边，30变成整棵树的根

            右单旋h与左单旋一样，都有h为1、2、3的三种情况，只不过右单旋的插入节点在a处，其他的条件都是相同的

            ---

            

            

            右单旋跟左单旋思想相同，

            只不过把b作为60的左子树，再把60作为30的右子树

            同样考虑父节点问题以及旋转整棵树或者部分子树旋转问题

            ---

            在insert中判断左右单旋的条件

            

            当parent的平衡因子为2并且cur的平衡因子为1时，为左单旋

            ---

            

            当parent的平衡因子为-2并且cur的平衡因子为-1时，为右单旋

            ---

            

            双旋转

            抽象图

            

            ---

            当h=0时，60作为新增节点

            

            ---

            当h==1时，60的左右子树新增都会引用旋转

            

            ---

            假设在左子树处新增节点

            

            ---

            若h==2时

            

            a/d是x/y/z中的任意一种

            b/c的孩子位置的任意一点插入节点，都会引发旋转

            左右双旋

            当h==2时， 假设在b的右子树插入节点

            

            将30进行左旋：30是parent的左子树

            将b作为30的右子树，将30作为60的左子树，将60作为90的左子树

            ---

            

            将60进行右旋：60作为整棵树新的根

            将60的右子树作为90的左子树，将90作为60的右子树

            ---

            假设在c的右子树插入新增节点

            

            新增节点插入在b和c节点，各个位置的平衡因子是不一样的

            ---

            

            当h=0时，左右双旋后，平衡因子与上述两个也是不同的

            ---

            

            

            当subLR即60节点处的平衡因子为-1时，说明在b处插入新增节点，

            双旋后 subl的平衡因子为0，subLR的平衡因子为0，parent的平衡因子为1

            当subLR即60节点处的平衡因子为1时，说明在c处插入新增节点，

            双旋后 subl的平衡因子为-1，subLR的平衡因子为0，parent的平衡因子为0

            当subLR即60节点处的平衡因子为0时，说明在60即为新增节点，

            双旋后 subl的平衡因子为0，subLR的平衡因子为0，parent的平衡因子为0

            右左双旋

            

            当h==0时，60作为新增节点

            ---

            

            当h==1时，60的左右新增节点都会引发旋转

            ---

            

            a/d是x/y/z中任意一个

            b和c是一个节点的子树

            ---

            

            b/c的四个孩子位置的任意一个位置新增节点，都会引发旋转

            ---

            假设在c处新增节点

            

            ---

            

            对于90进行右单旋，将c作为90的左子树，将90作为60的右子树

            ---

            

            对30进行左单旋，将b作为30的右子树，将30作为60的左子树

            插入引发双旋的场景

            1.h==2时，c插入，c的高度变化为h

            

            刚开始60的平衡因子为1

            ---

            2…h==2时，b插入，b的高度变化为h

            

            刚开始60的平衡因子为-1

            ---

            3. h==1时，60本身就是新增节点

            

            刚开始60的平衡因子为0

            ---

            

            当subLR即60节点处的平衡因子为1时，说明在c处插入新增节点，

            双旋后 subR的平衡因子为0，subRL的平衡因子为0，parent的平衡因子为-1

            当subLR即60节点处的平衡因子为-1时，说明在b处插入新增节点，

            双旋后 subR的平衡因子为1，subRL的平衡因子为0，parent的平衡因子为0

            当subLR即60节点处的平衡因子为0时，说明在60即为新增节点，

            双旋后 subR的平衡因子为0，subRL的平衡因子为0，parent的平衡因子为0

            ---

            

            当parent的平衡因子为2，并且cur的平衡因子为-1时，为右左双旋

            

            中序遍历

            

            平衡树的中序遍历与搜索树的中序遍历基本一致，root->_kv.first 实际上代表的是kv中key值

            如果不懂可以查看：二叉搜索树

            判断一颗二叉树是否为平衡树

            因为平衡因子是自己更新的，如果更新错了，那检查将无意义

            所以通过高度差去判断

            ---

            在height函数中，求出其左右子树高度，并返回左右子树高度大的加1 即当前树的高度

            

            ---

            在_isbalance函数中，通过左右子树高度差的绝对值 ，判断是否为平衡树 ，即 高度差不超过2

            

            ---

            

            在当前情况下，虽然左子树与右子树的高度差为1，

            但是并不是平衡树，因为它的右子树节点6的高度差为2

            所以还要判断子树是否符合平衡树

            

            ---

            若平衡因子异常，虽然在当前判断平衡树是没有影响的，但是在后续插入判断时，使不该旋转的进行旋转了

            所以需要判断下当前root的平衡因子是否与左右子树高度差相等，若不想等则平衡因子异常

            

            ---

            整体代码

            #include
            #include
            using namespace std;
            template
            struct  AVLTreeNode
            {
            	AVLTreeNode* _left;
            	AVLTreeNode* _right;
            	AVLTreeNode* _parent;
            	pair _kv;//当前节点值
            	int _bf;//平衡因子
            	AVLTreeNode(const pair& kv)
            		:_left(nullptr),
            		_right(nullptr),
            		_parent(nullptr),
            		_kv(kv),
            		_bf(0)
            	{
            	}
            };
            template
            class AVLTree
            {
            	typedef AVLTreeNode Node;
               public:
            	bool insert(const pair& kv)
            	{
            		if (_root == nullptr)
            		{
            			_root = new Node(kv);
            			return true;
            		}
            		Node* parent = nullptr;//用于记录cur的前一个节点
            		Node* cur = _root;
            		while (cur)
            		{
            			//若插入的值比当前树的值小 插入左边
            			if (cur->_kv.first > kv.first)
            			{
            				parent = cur;
            				cur = cur->_left;
            			}
            			//若插入的值比当前树的值大 插入右边
            			else if (cur->_kv.first < kv.first)
            			{
            				parent = cur;
            				cur = cur->_right;
            			}
            			else
            			{
            				//若插入的值，在树中有相同的值 ，则插入失败
            				return false;
            			}
            		}
            		cur = new Node(kv);
            		//再次判断parent当前节点值与插入值大小
            		if (parent->_kv.first > kv.first)
            		{
            			parent->_left = cur;
            		}
            		else
            		{
            			parent->_right = cur;
            		}
            		//cur的上一个节点即为 刚才的记录cur前一个节点的parent
            		cur->_parent = parent;
            		//更新平衡因子
            		while (parent)
            		{
            			//若插入节点在parent的右子树
            			if (cur == parent->_right)
            			{
            				parent->_bf++;
            			}
            			//若插入节点在parent的左子树
            			else
            			{
            				parent->_bf--;
            			}
            			if (parent->_bf == 1 || parent->_bf == -1)
            			{
            				//继续向上更新
            				parent = parent->_parent;
            				cur = cur->_parent;
            			}
            			//平衡因子为0，不需要向上更新
            			else if (parent->_bf == 0)
            			{
            				break;
            			}
            			else if (parent->_bf == 2 || parent->_bf == -2)
            			{
            				//旋转
            				//1.让这颗子树平衡 2.降低子树高度
            				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)//左右双旋
            				{
            					RotateLR(parent);
            				}
            				else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋
            				{
            					RotateRL(parent);
            				}
            				else
            				{
            					assert(false);
            				}
            				//旋转后整颗树已经平衡了，就不需要在继续了
            				break;
            			}
            		}
            		return true;
            	}
            	void inorder()//中序遍历
            	{
            		_inorder(_root);
            		cout << endl;
            	}
            	//判断一颗二叉树是否为平衡树
            	bool isbalance()
            	{
            		return _isbalance(_root);
            	}
            private:
            	
            	int height(Node* root)
            	{
            		if (root == nullptr)
            		{
            			return 0;
            		}
            		int leftH = height(root->_left);//左子树高度
            		int rightH = height(root->_right);//右子树高度
            		//返回左右子树高度大的加1
            		return leftH > rightH ? leftH + 1 : rightH + 1;
            	}
            	bool _isbalance(Node* root)
            	{
            		if (root == nullptr)
            		{
            			return true;
            		}
            		int leftH = height(root->_left);
            		int rightH = height(root->_right);
            		if (rightH - leftH != root->_bf)
            		{
            			cout << root->_kv.first << "节点平衡因子异常" << endl;
            			return false;
            		 }
            		//判断最终绝对值是否小于2
            		return abs(leftH - rightH) < 2&&_isbalance(root->_left)&&_isbalance(root->_right);
            	}
            	 
            	void _inorder(Node* root)
            	{
            		if (root == nullptr)
            		{
            			return;
            		}
            		_inorder(root->_left);
            		cout << root->_kv.first << " ";
            		_inorder(root->_right);
            	}
            	void RotateL(Node* parent)//左单旋
            	{
            		Node* subR = parent->_right;
            		Node* subRL = subR->_left;
            		parent->_right = subRL;
            		if (subRL != nullptr)
            		{
            			subRL->_parent = parent;
            		}
            		Node* ppnode = parent->_parent;//记录parent的前一个节点
            		subR->_left = parent;
            		parent->_parent = subR;
            		if (ppnode == nullptr)//说明parent是根即代表整棵树
            		{
            			_root = subR;//subR作为新的根
            			_root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
            		}
            		else//说明旋转的是一部分，所以要跟ppnode相连接
            		{
            			if (ppnode->_left == parent)//若连接在左子树上
            			{
            				ppnode->_left = subR;
            			}
            			else//若连接在右子树上
            			{
            				ppnode->_right = subR;
            			}
            			subR->_parent = ppnode;//将subR父节点置为ppnode
            		}
            		parent->_bf = subR->_bf = 0;//平衡因子都为0
            	}
            	void RotateR(Node* parent)//右单旋
            	{
            		Node* subL = parent->_left;
            		Node* subLR = subL->_right;
            		parent->_left = subLR;
            		if (subLR != nullptr)
            		{
            			subLR->_parent = parent;
            		}
            		Node* ppnode = parent->_parent;//记录parent的父节点
            		subL->_right = parent;
            		parent->_parent = subL;
            		if (ppnode == nullptr)//若旋转整棵树
            		{
            			_root = subL;
            			_root->_parent = nullptr;
            		}
            		else//若旋转整棵树的部分子树
            		{
            			if (ppnode->_left == parent)
            			{
            				ppnode->_left = subL;
            			}
            			else
            			{
            				ppnode->_right = subL;
            			}
            			subL->_parent = ppnode;//使subL的父节点为ppnode
            		}
            		parent->_bf = subL->_bf = 0;
            	}
            	void RotateLR(Node* parent)//左右双旋
            	{
            		Node* subL = parent->_left;
            		Node* subLR = subL->_right;
            		int bf = subLR->_bf;//记录平衡因子，在后续单旋会置为0
            		
            		//先对parent的左子树进行左单旋
            		RotateL(parent->_left);
            		//再对当前根进行右单旋
            		RotateR(parent);
            		if (bf == -1)//h==2时，在b处插入节点
            		{
            			subL->_bf = 0;
            			subLR->_bf = 0;
            			parent->_bf = 1;
            		}
            		else if (bf == 1)//h==2时，在c处插入节点
            		{
            			subL ->_bf = -1;
            			subLR ->_bf= 0;
            			parent->_bf = 0;
            		}
            		else if (bf == 0)//当h==0时，60作为新增节点
            		{
            			subL->_bf = 0;
            			subLR->_bf = 0;
            			parent->_bf = 0;
            		}
            	}
            	void RotateRL(Node* parent)//右左双旋
            	{
            		Node* subR = parent->_right;
            		Node* subRL = subR->_left;
            		int bf = subRL->_bf;//记录平衡因子，在后续单旋会置为0
            		RotateR(parent->_right);
            		RotateL(parent);
            		//h==2时，c插入，c的高度变化为h
            		if (bf == 1)
            		{
            			subR->_bf = 0;
            			parent->_bf = -1;
            			subRL->_bf = 0;
            		}
            		//h==2时，b插入，b的高度变化为h
            		else if (bf ==-1)
            		{
            			subR->_bf = 1;
            			parent->_bf = 0;
            			subRL->_bf = 0;
            		}
            		// h==1时，60本身就是新增节点
            		else if(bf == 0 )
            		{
            			subR->_bf = 0;
            			parent->_bf = 0;
            			subRL->_bf = 0;
            		}
            		else
            		{
            			//不存在情况，若进入则出问题了
            			assert(false);
            		}
            	}
            private:
            	Node* _root = nullptr;
            };
            void test_AVLTree1()
            {
                //int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
            	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14};
            	AVLTreev1;
            	for (auto e : a)
            	{
            		v1.insert(make_pair(e,e));
            	}
            	v1.inorder();
            	cout << v1.isbalance() << endl;//返回值为布尔值
            }
            

             
             b2c电商平台  手机网站制作教程  网页设计与网站建设课程设计  汕头网站制作公司  网站公司给做的网站被起诉  网络营销的方法有哪些