AVL树的概念与实现
1.AVL树的概念
AVL树是建立在搜索树的基础之上的,AVL树的出现,是为了解决搜索树在多次插入一个接近有序数据时候会退化成单支树的问题,AVL树的解决方法就是引入一个平衡因子,通过检测平衡因子,来调整整棵树的高度.
1.平衡因子
平衡因子在AVL树中的作用是及其重要的,平衡因子会有三种情况,0和-1/1,和-2/2,当平衡因子是0的时候,这整棵树就是一个非常健康的状态;当平衡因子是-1/1的时候,整棵树就是一个亚健康的状态,但是此时的左右子树的高度差不超过1,也不会进行调整;当平衡因子是-2/2的时候,这个时候就需要根据实际情况来进行相应的调整了.
2.平衡因子的计算
平衡因子总的来说,有两种计算方法,要么是左子树高度-右子树高度,要么就是右子树高度-左子树高度,在代码的实现中,通常只用一种,这里我们将采取右子树高度-左子树高度的方案.
则在子树的插入中,如果新节点插入在了左子树,则父节点的平衡因子--;如果新节点插入在父节点的右子树,则父节点的平衡因子++.而插入规则则跟搜索树是一样的.
2.AVL树的实现
1.AVL树节点定义
首先,跟之前的搜索树的是一大体上相同,定义一个节点,使用类模板来定义.
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _key;
int _bf;
AVLTreeNode(const pair<K, V>& key)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _key(key)
{}
};
这里解释一下,这个_key就是插入的是一个pair的值,而pair是一个键值对,里面的键值就是K和V.
初始化列表里面的_bf就是这个节点的平衡因子.当一个新节点生成的时候,这个时候的平衡因子就是0.
2.AVL树节点的插入
这个节点插入分成两部分来写,一部分是寻找到合适的插入位置进行插入,另一部分则是更新平衡因子.
1.寻找插入位置进行插入
寻找插入位置的话,就是看看当前的key适合插入在搜索树的哪个地方,当前key如果小于当前parent,就往左走,继续更新parent来寻找最佳插入位置;如果当前key大于当前parent,就往右走,更新parent来寻找这个最佳插入位置.
因此这个寻找插入位置的思路就是,如果当前的搜索树为空,则让插入的第一个key来当这棵树的root,如果不是空,则定义一个cur,这个cur初始化成root,然后跟key作比较,如果key < cur->key, 这个cur就往左边更新;如果key > cur->key , 这个cur就往右边更新.知道cur的位置是空的时候,就是最佳的插入位置.
当cur为空的时候,此时用new来搞一个key节点,还需要跟parent来进行比较,如果是比parent小,就插入在parent的左边,如果比他大,就插入在parent的右边
if (_root == nullptr)
{
Node* newnode = new Node(key);
_root = newnode;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (key.first > cur->_key.first)
{
parent = cur;
cur = cur->_right;
}
else if (key.first < cur->_key.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if (cur->_key.first > parent->_key.first)
{
parent->_right = cur;
}
if (cur->_key.first < parent->_key.first)
{
parent->_left = cur;
}
cur->_parent = parent;2.更新平衡因子
更新平衡因子的方法就是,如果这个新节点插入在左子树,那么当前的parent->_bf就进行--,如果插入在右子树,则为就是++.但是,如果改变一个节点的bf,则很大概率上会影响到他的parent,因此,如果当前位置节点的bf更新完之后,如果他的parent是1或者-1,则就继续更新;如果是2或者-2,则这个而时候就需要通过旋转来使得这棵树进行最大程度上的平衡,如果是0,则这棵树就是平衡的,不需要调整.
//更新平衡因子
//默认是右-左,因此这个地方插入左节点,平衡因此--;插入右节点,平衡因子++
while (parent)
{
if (cur == parent->_left)
{
parent->_bf--;
}
else if(cur == parent->_right)
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
//如果平衡因子是1或者-1,则继续更新
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//右单旋
if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
//左单旋
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
//左右双旋
if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
//右左双旋
if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
}
else
{
return false;
}
}
}3.AVL树的旋转
发生旋转的条件是当parent的平衡因子超过了1或者-1的时候,也就是平衡因子是2/-2的时候,就需要旋转,而旋转有四种旋转,左单旋,右单旋,左右双旋,左左双旋.
1.左单旋(当新节点插入在较高右子树的右侧)
当根节点的左右子树(右子树高度 - 左子树高度) == 2 && cur->_bf == 1(这个是1,就说明在cur的右边新增了一个节点)的时候,就是发生左单旋的时候.
代码的实现思路,得按着图来,首先是把subRL给到parent->_right,在此之前还需要判断subRL是否为空节点,如果是空节点,那就不用给过去,然后把parent给到subR的左边,此时还需要考虑原来的parent是否会又再继续会有一个parent,如果有,那就需要用一个ppNode来把他记录下来,然后判断原来的parent是在ppNode的左还是右,如果是在左,那就ppNode的左链接到subR , 如果是在右,那就ppNode的右边链接到subR
void RotateL(Node* parent)
{
Node* cur = parent;
Node* subR = cur->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
Node* ppNode = parent->_parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
}
subR->_parent = ppNode;
parent->_bf = subR->_bf = 0;
}
2.右单旋(当新节点插入较高左子树的左侧)
当根节点的左右子树(左子树高度-右子树高度) == -2 && cur->_bf == -1(这个是-1,就说明在当前cur的左边新增了一个节点)的时候,就是发生右单旋的时候.
而发生右单旋,则是让parent->_left指向了subLR,然后subL->_right指向了parent,同样的,也是需要判断subLR是否为空,还有parent之前是否有parent.这个跟左单旋基本一模一样,只是方向相反
void RotateR(Node* parent)
{
Node* cur = parent;
Node* subL = cur->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
subL->_right = parent;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (ppNode->_right == parent)
{
ppNode->_right = subL;
}
else
{
ppNode->_left = subL;
}
subL->_parent = ppNode;
}
subL->_bf = parent->_bf = 0;
}
3.左右双旋(新节点插入较高左子树的右侧)
要搞清楚发生左右双旋的条件,我们首先来看一颗最简单的树
当一棵树变成这种形状的时候,我们就需要进行一下左右双旋了,由此我们也可以知道,左右双旋的条件就是 当parent->_bf == 2 && cur->_bf == -1的时候,就发生了左右双旋
而对于左右双旋则会有三种情况
1.subLR是-1(新节点插入在subLR的左边)
我们此时用一个抽象图来表示,圆表示节点,方框表示树,h表示高度.前面说了,左右双旋就是新节点插入到较高左子树的右侧,那这个时候,我们就有两种可能性,第一种是插入在b,第二种是插入在c,那我们首先就拿插入在b来举例子.
当新节点插入在b后面的时候,此时平衡将被打破,这个时候的subLR的平衡因子就是-1,此时相对subL来说则是他的右边插入了一个新节点,这个时候他的平衡因子则是2,满足发生左右双旋的条件.
首先,subL->_right = b , 然后 parent->_left = c ,最后,subLR做subL和parent的根节点,这个就是左右双旋的过程
完成双旋后,就需要调整这个平衡因子了,就拿这个情况来说,当前的subLR的-1,旋转之后,subLR的平衡因子肯定会被改变,因此旋转前需要用一个变量来进行记录.那么我们直接修改的则是旋转后的subL和parent的平衡因子就可以了.因此subL和parent的平衡因子分别是0和-1
2.subLR是1(新节点插入在subLR的右边)
看这个图,如果说subLR的平衡因子是1,则说明新节点插入在subLR的右边
此时的subL->_right= b , parent->_left = c , subLR则变成了subL和parent的根
跟上面那种情况大同小异.
3.subLR是0
这个时候他是0,就说明了这整棵树都是平衡的,因此,其它两个地方的平衡因子全部都是0.
代码:
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == -1)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == 0)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
4.右左双旋(新节点插入在较右子树的左侧)
跟左右双旋相反,他的基本树是这样的
此时很明显的就可以看到,parent的平衡因子是-2,cur的平衡因子是1,因此我们可以得出右左双旋的条件,他刚好跟左右双旋的条件是相反的,就是parent->_bf == -2 && cur->_bf == 1
他的操作跟上面的双旋也是一样的,只不过是方向反了,先是右旋,后是左旋.
然后在修改平衡因子的时候,就是根据subRL来,把parent->_bf 改成1,subR改成0就可以了.
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
subRL->_bf = 0;
if (bf == 1)
{
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
else
{
parent->_bf = 0;
subR->_bf = 0;
}
}4.AVL树的判断平衡,寻找,计算高度,计算节点
//计算二叉树高度
int _Height(Node* root)
{
if (root == nullptr)
return 0;
return max(height(root->_left), height(root->_right)) + 1;
}
//节点个数
int _Size(Node* root)
{
if (root == nullptr)
{
return 0;
}
return _Size(root->_left) + _Size(root->_right) + 1;
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
if (abs(leftHeight - rightHeight) >= 2)
{
cout << root->_key.first << endl;
return false;
}
if (rightHeight - leftHeight != root->_bf)
{
cout << root->_key.first << endl;
}
return _IsBalance(root->_left) &&
_IsBalance(root->_right);
}
//计算节点数
int Node_num(Node* root)
{
if (root == nullptr)
{
return 0;
}
return height(root->_left) + height(root->_right) + 1;
}