AVL树详解：平衡因子、插入与旋转操作

AVL树

1. 概念

与红黑树的目标一样，都是控制二叉搜索树的平衡

他是由前苏联两个科学家弄出来的，分别叫​G.M.Adelson-Velsky​和​E.M.Landis，这也是AVL名称的由来

也叫自平衡二叉查找树

AVL树实现这里我们引入一个平衡因子（balancefactor）的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。

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

AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在logN，那么增删查改的效率也可以控制在O（logN），相比二叉搜索树有了本质的提升。

‍

基本功能

插入逻辑基本跟搜索二叉树保持一致

每插入一个元素，就要从该节点向上查找节点平衡因子是否满足-1/0/1，根据情况选择旋转方式来平衡平衡因子

‍

根据平衡因子的计算规则，我们可以知道

插入左边父亲平衡因子要减减，插入右边平衡因子要加加

‍

插入

template <class K, class V>
struct AVLTreeNode {
pair(K, V) _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf;

AVLTreeNode(const pair<K, V> kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}

}；
template<class K,class V>
class My_avl {
typedef AVLTreeNode<K, V> Node;
bool insert(const pair(K, V)& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
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 < cur)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//更新平衡因子
while (parent)
{
if (cur == parent->_left)
{
–parent->_bf;
}
else
{
++parent->_bf;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
//继续更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//旋转处理
break;
}
else
{
assert(false);
}
}
return true;
}

private:
Node* _root = nullptr;
};

旋转

旋转的规则

‍

右单旋

‍

#pragma once
#include<assert.h>
#include<iostream>
#include<set>
#include<map>
using namespace std;

namespace My_AVL {
template <class K, class V>
struct AVLTreeNode {
pair(K, V) _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf;

AVLTreeNode(const pair<K, V> kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};
template<class K,class V>
class My_avl {
typedef AVLTreeNode<K, V> Node;
void RotateR(Node* parent)//右旋
{
Node* subL = parent->_left;
Node* subLR = parent->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent->_left;
Node* Parentparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
// parent有可能是整棵树的根，也可能是局部的⼦树
// 如果是整棵树的根，要修改_root
// 如果是局部的指针要跟上⼀层链接
if (Parentparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (Parentparent->_left == parent)
{
Parentparent->_left = subL;
}
else if (Parentparent->_right == parent)
{
Parentparent->_right = subl;
}
subL->_parent = Parentparent;
}
return;
}

private:
Node* _root = nullptr;
};
}

左单旋

#pragma once
#include<assert.h>
#include<iostream>
#include<set>
#include<map>
using namespace std;

namespace My_AVL {
template <class K, class V>
struct AVLTreeNode {
pair(K, V) _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf;

AVLTreeNode(const pair<K, V> kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};
template<class K,class V>
class My_avl {
typedef AVLTreeNode<K, V> Node;
void RotateL(const Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_left = subRL;
if (subRL)
subRL->_parent = parent->_left;
Node* Parentparet = parent->_parent;
subR->_right = parent;
parent->_parent = subR;
if (Parentparet == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (Parentparet->_left == parent)
{
Parentparet->_left = subR;
}
else if (Parentparet->_right == parent)
{
Parentparet->_right = subR;
}
subR->_parent = Parentparet;
}
return;
}

private:
Node* _root = nullptr;
};
}

左右双旋

不需要再重头开始写，在相应部分复用左旋和右旋代码

不是纯粹的右边高或者左边高

‍

//为了更清晰的显示，这里直接给关键代码，头文件和相关成员变量可以参考上面代码

void RotateLR(const Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;

RotateL(parent->_left);
RotateLR(parent);

if (bf == 0)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = ;
}
else if (bf == -1)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else
{
assert(false);
}
}

右左双旋

与左右双旋高度类似

注意一点，与上面的左右双旋相反的一点，需要双旋的那一坨由根节点的左子树那一块，变成了根节点的右子树那一块。那么在完成双旋后，​parent​节点变成了左边，​subR节点变成了右边

//为了更清晰的显示，这里直接给关键代码，头文件和相关成员变量可以参考上面代码
void RotateRL(const Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_right;
int bf = subR->_bf;
RotateR(parent->_right);
Rotate(parent);

if (bf == 0)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
else 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
{
assert(false);
}
}

AVL树的查找

AVL树的查找与二叉搜索树的查找是一样的搜索效率是O(log N)，比它大就往右走，比他小就往左走

‍

完