文章目录
平衡二叉树：旋转：最简单的四种旋转情况LL旋转RR旋转LR旋转RL旋转
较复杂的四种旋转情况LL旋转RR旋转LR旋转RL旋转
完整代码
平衡二叉树：
高度的概念：距离根节点有多少层
左右子树的高度差不超过1的有序二叉树。
平衡的概念：结点的平衡因子 = 结点的左子树深度 — 结点的右子树深度。
若平衡因子的取值为-1、0或1时，该节点是平衡的，否则是不平衡的。
旋转：
由于平衡因子不平衡，所以引入了旋转的概念，来使得二叉树平衡
最简单的四种旋转情况
LL旋转
由于10的左孩子的高度为2，右孩子高度为0，平衡因子为2，二叉树不平衡，需要进行旋转操作，如何旋转？
将10节点进行左旋操作，类似于将10节点顺时针旋转。
RR旋转
由于10的右孩子的高度为2，左孩子高度为0，平衡因子为 -2，二叉树不平衡，需要进行旋转操作
将10节点进行右旋操作，类似于将10节点逆时针旋转。
LR旋转
先将9节点进行左旋操作，让8节点成为9的左孩子；再进行一次右旋操作，9成为根节点
RL旋转
先将9节点进行右旋操作，10节点成为9的右孩子；再进行一次左旋操作，9成为根节点
较复杂的四种旋转情况
LL旋转
当添加的新节点成为最小不平衡树的左孩子的左子树时产生：
规划可知8节点应为根节点；
旋转过程：
根节点12右旋转（顺时针）成为8节点的右孩子。8节点的右孩子成为12的左孩子。8节点成为新的根节点。
RR旋转
当添加的新节点成为最小不平衡树的右孩子的右子树时产生：
规划可知8应为新的根节点：
旋转过程：
根节点6左旋转（逆时针），成为8的左孩子。8的左孩子成为6节点的右孩子。8成为新的根节点。
LR旋转
当添加的新节点成为最小不平衡树的左孩子的右子树时产生：
规划可知，7应该成为新的根节点
旋转过程：
7节点左旋成为10的相邻左孩子。6节点成为7节点的左孩子。根节点右旋成为7节点的相邻右孩子。7节点的右孩子成为10节点的左孩子。7节点成为新的根节点
RL旋转
当添加的新元素成为最小不平衡树的右孩子的左子树时产生：
7应该成为根节点
旋转过程：
7节点右旋成为根节点的相邻右孩子。8节点成为7节点的右孩子。根节点左旋成为7的相邻左孩子。7节点的左孩子成为4节点的右孩子。7成为新的根节点。
完整代码
#pragma once
#include
using namespace std;
template
struct TreeNode
{
T data;
TreeNode* pLeft; //左孩子
TreeNode* pRight; //右孩子
int height; //高度
TreeNode(const T& data)
{
this->data = data;
pLeft = pRight = nullptr;
height = 0;
}
};
template
class ACL_Tree
{
public:
ACL_Tree() { pRoot = nullptr; }
~ACL_Tree() {}
//插入节点
void Insert_Node(const T& newdata)
{
_insert(pRoot, newdata);
}
//获取某个节点的高度
int _getHeight(TreeNode
//情况一 右旋
TreeNode
//情况二 左旋
TreeNode
//情况三 左右旋
TreeNode
//情况四 右左旋
TreeNode
private:
void _insert(TreeNode
private:
TreeNode
};
template
void ACL_Tree
{
if (pRoot == nullptr)
{
//如果当前节点为空，则直接插入
pRoot = new TreeNode
}
else if (data < pRoot->data)
{
//左插
_insert(pRoot->pLeft, data);
//判断是否需要旋转
if (_getHeight(pRoot->pLeft) - _getHeight(pRoot->pRight) > 1)
{
if (data < pRoot->pLeft->data)
{
//RR 左旋
pRoot = RR(pRoot);
}
else
{
//LR 左右旋
pRoot = LR(pRoot);
}
}
}
else
{
//右插
_insert(pRoot->pRight, data);
if (_getHeight(pRoot->pRight) - _getHeight(pRoot->pLeft) > 1)
{
if (data >= pRoot->pRight->data)
{
//LL 右旋
pRoot = LL(pRoot);
}
else
{
//RL 右左旋
pRoot = RL(pRoot);
}
}
}
//3 设置高度
int leftHeight = _getHeight(pRoot->pLeft);
int rightHeight = _getHeight(pRoot->pRight);
pRoot->height = 1 + (
(leftHeight > rightHeight) ? leftHeight : rightHeight
);
}
template
//获取某个节点的高度
inline int ACL_Tree
{
if (root)
{
return root->height;
}
return 0;
}
//右旋
template
inline TreeNode
{
//1. pTemp临时存储pRoot的pLeft
TreeNode
//2. pTemp的右孩子成为pRoot的左孩子
pRoot->pLeft = pTemp->pRight;
//3. pRoot成为pTemp的右孩子
pTemp->pRight = pRoot;
//4. 高度设置
pRoot->height = 1 + ((_getHeight(pRoot->pLeft) > _getHeight(pRoot->pRight)) ?
_getHeight(pRoot->pLeft) : _getHeight(pRoot->pRight));
pTemp->height=1+ ((_getHeight(pTemp->pLeft) > _getHeight(pTemp->pRight)) ?
_getHeight(pTemp->pLeft) : _getHeight(pTemp->pRight));
return pTemp;
}
//左旋
template
inline TreeNode
{
//1. pTemp临时存储pRoot的pRight
TreeNode
//2. pTemp的左孩子成为pRoot的右孩子
pRoot->pRight = pTemp->pLeft;
//3. pRoot成为pTemp的左孩子
pTemp->pLeft = pRoot;
//4. 高度设置
pRoot->height = 1 + ((_getHeight(pRoot->pLeft) > _getHeight(pRoot->pRight)) ?
_getHeight(pRoot->pLeft) : _getHeight(pRoot->pRight));
pTemp->height = 1 + ((_getHeight(pTemp->pLeft) > _getHeight(pTemp->pRight)) ?
_getHeight(pTemp->pLeft) : _getHeight(pTemp->pRight));
return pTemp;
}
template
inline TreeNode
{
//以pRoot的pLeft为轴左旋
pRoot->pLeft = LL(pRoot->pLeft);
//再右旋
return RR(pRoot);
}
template
inline TreeNode
{
//以pRoot的pRight为轴右旋
pRoot->pRight = RR(pRoot->pRight);
//再左旋
return LL(pRoot);
}
#include "ACLTree.h"
#define NUM 10
int main()
{
int arr[NUM] = { 55,99,24,66,11,10,77,13,38,91 };
ACL_Tree
for (int i = 0; i < NUM; i++)
{
a.Insert_Node(arr[i]);
}
return 0;
}