028-86922220
根据您的个性需求进行定制 先人一步 抢占小程序红利时代
前情回顾：二叉搜索树 👉传送门
本章我们将学习AVL树，来解决上一章节二叉搜索树的查找时二叉树不平衡的问题，搬好小板凳准备开讲啦~~~ 🙋 🙋 🙋 🙋 🙋
两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis（AVL树就是以这两位科学家的名字命名的）
在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
1.2 AVL树的性质：首先AVL树是一棵二叉搜索树，一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
平衡不是相等，与满二叉树和完全二叉树比较一下：（节点外数字代表平衡因子）
AVL树又叫高度平衡二叉搜索树。
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 〇（logN）搜索时间复杂度 〇（logN）。
具体代码如下：
templatestruct AVLTreeNode
{pair_kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf;
AVLTreeNode(const pair& kv)
: _kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
}; 2.2 AVL树的插入：（重点）AVL树并没有规定必须要设计平衡因子，只是一个实现的选择，方便控制平衡。
这里链接是比较容易的，但是链接之后对各个结点中的平衡因子的调整则是比较费劲的。
2.2.1 插入结点后平衡因子的变化1. 首先我们来一段简单的逻辑 —— 只考虑父子之间关系：
如图所示：
2. 插入一个结点对整个树的影响：
如图所示：
3. 在链接新的结点的时候要满足AVL树的规则
(1)向上更新：
(2)如何向上更新：
具体过程如下：
- 子树高度变了，就要继续往上更新
- 子树的高度不变, 则更新完成
- 子树违反平衡规则，则停止更新, 旋转子树
情况一：
情况二：
情况三：
我们讨论问题要将各个方面的都要考虑到位才行，即使前面都正确是不会走到这一步的，但是为了万无一失还是要将这一步写上。
情况四：
具体代码如下：
bool Insert(const pair& kv)
{if (_root == nullptr)
{_root = new Node(kv);
_root->_bf = 0;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{if (cur->_kv.first< kv.first)
{ parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first >kv.first)
{ parent = cur;
cur = cur->_left;
}
else
{ return false;
}
}
//找到符合规则的位置之后再插入
cur = new Node(kv);
if (parent->_kv.first< kv.first)
{parent->_right = cur;
}
else
{parent->_left = cur;
}
//三叉链的链接 -- 链上父节点
cur->_parent = parent;
while (parent)
{if (cur == parent->_right)
{ parent->_bf++;
}
else if (cur == parent->_left)
{ parent->_bf--;
}
//是否继续更新
if (parent->_bf == 0) //原来是 1 or -1 -->0 （插入结点填在了矮的那一边）
{ //高度不变，更新结束
break;
}
else if(parent->_bf == 1 || parent->_bf == -1)
//原来是 0 -->1 or -1 （插入结点导致一边变高了）
{ //子树的高度变了，继续更新祖先
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
//原来是 1 or -1 -->2 or -2 （插入结点导致本来高的一边又变高了）
{ //子树不平衡了 -- 需要旋转处理（左单旋的特征 -- 右边高）
if (parent->_bf == 2 && cur->_bf == 1)//左单旋
{ RatateL(parent);
}
//子树不平衡了 -- 需要旋转处理（右单旋的特征 -- 左边高）
else if (parent->_bf == -2 && cur->_bf == -1)//右单旋
{ RatateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋
{ RatateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋
{ RatateRL(parent);
}
//旋转完之后ppNode为根的子树高度不变 -- 所以对ppNode的平衡因子没有影响
break;
}
else // 一定要检查 -- 不保证其他地方不会出现错误
{ //插入之前AVL数就存在平衡子树，|平衡因子| >= 2结点
assert(false);
}
}
return true;
} 上述我们已经阐述了，在什么情况下需要对AVL树进行旋转操，接下来我们就来讲一下具体的旋转步骤。
旋转原则：
旋转一共分为四种旋转方式：
当右子树高的时候，这时就要向左旋转。
旋转过程：
旋转详情图：
原理：
代表所有情况的抽象图长方形条表示的是子树
下面来讨论一下h
此时有两种情况，新增的节点有可能是链接在这棵树最右边结点的，左边也有可能是链接在右边
此时一共有36种情况
解释：
具体代码如下：
//右边高就要左旋转
//左单旋
void RatateL(Node* parent)
{Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL != nullptr)
{subRL->_parent = parent;
}
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{_root = subR;
_root->_parent = nullptr;
}
else
{if (parent == ppNode->_left)
{ ppNode->_left = subR;
}
else if(parent == ppNode->_right)
{ ppNode->_right = subR;
}
subR->_parent = ppNode;
}
//更新平衡因子
parent->_bf = 0;
subR->_bf = 0;
}同时代码的一些细节也是需要把控的
当左子树高的时候，这时就要向右旋转。
旋转详情图：
旋转过程：
与左单旋一样当讨论h时，也能分出很多种，h = 1时是2种，h = 2时36种。
具体代码如下：
//左边高就要右旋转
//右单旋
void RatateR(Node* parent)
{Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR != nullptr)
{subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{_root = subL;
subL->_parent = nullptr;
}
else
{if (ppNode->_left == parent)
{ ppNode->_left = subL;
}
else if (ppNode->_right == parent)
{ ppNode->_right = subL;
}
subL->_parent = ppNode;
}
//更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}细节把控也与左单旋类似可以参考左单旋。
光有左右单旋是解决不了所有问题的，如图所示就是特殊情况：
如图所示，很显然右单旋并没有解决问题，旋转之后仍然不是AVL树，此时我们就引入了双旋：
旋转详情图：
同样可以对h进行讨论，也会对应很多种情况，不再一 一赘述。
具体代码如下：
//左右双旋
void RatateLR(Node* parent)
{Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RatateL(parent->_left);
RatateR(parent);
//更新平衡因子 -- 全是0的情况也要单独写，不要依赖单旋
if (bf == 0)
{parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == -1)
{parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{//subLR->_bf旋转前就有问题
assert(false);
}
}两种解决方案：
我们采用第一种方法，单独将平衡因子拿出来处理。
旋转详情图：
同样的右左双旋和左右双旋差不多，可以参考上文。
具体代码如下：
//右左双旋
void RatateRL(Node* parent)
{Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RatateR(parent->_right);
RatateL(parent);
if (bf == 0)
{subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else if (bf == 1)
{subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else
{//subLR->_bf旋转前就有问题
assert(false);
}
}我们先增加几个成员函数：
1.层序遍历打印树
void levelOrder()
{vector>vv;
if (_root == nullptr)
{return;
}
queueq;
int levelSize = 1;
q.push(_root);
while (!q.empty())
{//levelSize控制一层一层出
vectorlevelV;
while (levelSize--)
{ Node* front = q.front();
q.pop();
levelV.push_back(front->_kv.first);
if (front->_left != nullptr)
{ q.push(front->_left);
}
if (front->_right != nullptr)
{ q.push(front->_right);
}
}
vv.push_back(levelV);
for (auto e : levelV)
{ cout<< e<< " ";
}
cout<< endl;
//上一层出完，下一层就都进队列
levelSize = q.size();
}
} 2.中序遍历二叉树：
void _InOrder(Node* root)
{if (root == nullptr)
return;
_InOrder(root->_left);
cout<< root->_kv.first<< " ";
_InOrder(root->_right);
}
void InOrder()
{_InOrder(_root);
cout<< endl;
}3.求二叉树高度：
int _Height(Node* root)
{if (root == nullptr)
{return 0;
}
//后续的方式
int lh = _Height(root->_left);
int rh = _Height(root->_right);
return lh >rh ? lh + 1 : rh + 1;
}
int Height()
{return _Height(_root);
}验证一：
void TestAVLTree()
{//升序 -- 右边高左单旋
//int arr[] = { 1,2,3,4,5,6,7,8 };
//降序 -- 左边高右单旋
int arr[] = {8,7,6,5,4,3,2,1 };
AVLTreet;
for (auto e : arr)
{t.Insert(make_pair(e, e));
}
t.levelOrder();
} 
如图所示的两棵树均是满足AVL树，但是这这种验证还是不太严谨。
bool _IsBalanceTree(Node* root)
{//空树也是AVL树
if (nullptr == root)
return true;
//计算pRoot节点的平衡因子：即pRoot左右子树的高度差
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
//求差值
int diff = rightHeight - leftHeight;
//如果计算出的平衡因子与pRoot的平衡因子不相等，或者
//pRoot平衡因子的绝对值超过1，则一定不是AVL树
if (abs(diff) >= 2)
{cout<< root->_kv.first<< "结点平衡因子异常"<< endl;
return false;
}
//平衡因子没有异常但是和结点的对不上
if (diff != root->_bf)
{//说明更新有问题
cout<< root->_kv.first<< "结点平衡因子不符合实际"<< endl;
return false;
}
//pRoot的左和右如果都是AVL树，则该树一定是AVL树
//把自己和自己的左右子树都检查了，递归检查
return _IsBalanceTree(root->_left)
&& _IsBalanceTree(root->_right);
}
bool IsBalanceTree()
{return _IsBalanceTree(_root);
}验证二：
void TestAVLTree()
{const size_t N = 1024 * 1024 * 10;
vectorarr;
arr.reserve(N);//避免频繁扩容
srand(time(0));
for (size_t i = 0; i< N; i++)
{arr.push_back(rand());
//arr.push_back(i);
}
AVLTreet;
for (auto e : arr)
{t.Insert(make_pair(e, e));
}
cout<< "是否平衡？"<< t.IsBalanceTree()<< endl;
cout<< "高度："<< t.Height()<< endl;
//t.InOrder();
} 
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
