一、AVL树的概念
二叉搜索树虽然可以缩短查找效率,但如果数据的插入顺序是有序或接近有序的,二叉搜索树将退化为单支树,查找元素的效率相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当二叉搜索树中插入新节点后,如果能保证每个节点的左右子树高度差的绝对值不超过1(否则需要对树中的节点进行调整),既可降低树的高度,从而减少平均搜索长度。
一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
- 它的左右子树都是AVL树。
- 左右子树高度之差(简称平衡因子)的绝对值不超过1,平衡因子为右树的高度-左树的高度。
如果一棵二叉搜索树是平衡的,他就是AVL树,如果它有n个节点,其高度可保持在O(log2n),搜索时间复杂度O(log2n)
二、AVL树的节点
struct AVLTreeNode//AVL树节点
{
AVLTreeNode* _left;//左指针
AVLTreeNode* _right;//右指针
AVLTreeNode* _parent;//父指针
pair _kv;//键值对
int _bf;//平衡因子(右树高度-左树高度)
AVLTreeNode(const pair& kv)
:_left(nullptr)
, _right(nullptr)
, parent(nullptr)
, _kv(kv)
, bf(0)
{}
};
三、AVL树的插入
AVL树就是在二叉搜索树基础上引入了平衡因子,因此AVL树也可以看做是二叉搜索树。
AVL树的插入过程可以分为两步:
- 按照二叉搜索树的方式插入节点。
- 调整节点的平衡因子。
假设cur是新插入的节点,parent是新插入节点的父节点。
cur的平衡因子肯定是0,但是它会影响parent的平衡因子,所以在cur插入后,一定要调整parent的平衡因子,在插入cur之前,parent的平衡因子有三种可能情况:1,0,-1。分以下两种情况:
- 如果cur插入到parent的左侧,让parent的平衡因子-1即可。
- 如果cur插入到parent的右侧,让parent的平衡因子+1即可。
插入后,parent的平衡因子有三种情况:0,正负1,正负2。
- 如果parent的平衡因子为0,说明插入之前parent的平衡因子为正负1,插入后被调整成0,此时满足AVL树的性质,插入成功,不需要再向上调整。
- 如果parent的平衡因子为正负1,说明插入之前parent的平衡因子一定为0,插入后被更新成正负1,此时以parent为根的树的高度增加,上面可能还有节点平衡因子受到影响,还需要继续向上调整。
- 如果parent的平衡因子为正负2,则parent的平衡因子违反了平衡树的性质,需要对其进行旋转处理。
bool insert(const pair& kv)//插入
{
if (_root == nullptr)//如果此时树为空
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)//找到插入位置
{
parent = cur;
if (kv.first _kv.first)//比当前节点小
{
cur = cur->_left;//往左走
}
else if (kv.first > cur->_kv.first)//比当前节点大
{
cur = cur->_right;//往右走
}
else//有重复的
{
return false;
}
}
//找到插入的位置了
cur = new Node(kv);//创建新节点
if (parent->_kv.first _right = cur;
cur->_parent = parent;
}
else if(parent->_kv.first > kv.first)//插入父节点的左边
{
parent->_left = cur;
cur->_parent = parent;
}
//调整平衡因子
while (parent)
{
//调整父节点的平衡因子
if (parent->_left == cur)
{
parent->_bf--;
}
else if (parent->_right == cur)
{
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)//当前节点需要旋转
{
//旋转
}
}
return true;
}
四、AVL树的旋转
如果在一棵原本平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡。根据节点插入位置的不同,AVL树的旋转分为四种
1、右单旋
新节点插入较高左子树的左侧
上图在插入前,AVL树是平衡的,新节点插入到30的左子树(注意,不是左孩子)中,30左子树增加了一层,导致以60为根的二叉树不平衡,只能将60左子树的高度减少一层,右子树增加一层,即将30往上提,再把60往下转。因为60比30大,只能将其放在30的右子树,而如果30有右子树,右子树的值一定大于30、小于60,只能将30的右子树放在60的左子树。旋转完成后,更新节点的平衡因子即可。在旋转过程中,需要注意:
- 30的右子树可能存在也可能不存在
- 60可能是根节点,如果是根节点,旋转完成后,需要更新根节点。如果不是根节点只是一棵子树,可能是某个节点的左子树,也可能是右子树。
void RotateR(Node* parent)//右单旋
{
Node* parentParent = parent->_parent;//祖父节点
Node* subL = parent->_left;//左孩子节点
Node* subLR = subL->_right;//左孩子的右孩子节点
parent->_parent = subL;
parent->_left = subLR;
if (subLR)//如果该节点存在
{
subLR->_parent = parent;//让它的父指针指向父节点
}
if (parent == _root)//父节点就是根节点
{
_root = subL;//更新根节点
}
else//父节点是某个节点的子树
{
if (parentParent->_left == parent)//是某个节点的左子树
{
parentParent->_left = subL;
}
else//是某个节点的左子树
{
parentParent->_right = subL;
}
}
subL->_parent = parentParent;
subL->_right = parent;
parent->_bf = subL->_bf = 0;//更新平衡因子
}
h>=0,代表了许多种情况,下面列举两种
2、左单旋
新节点插入较高右子树的右侧
左单旋的逻辑和右单旋的逻辑是一样的,只是换了个方向而已
void RotateL(Node* parent)//左单旋
{
Node* parentParent = parent->_parent;//祖父节点
Node* subR = parent->_right;//左孩子节点
Node* subRL = subR->_left;//左孩子的右孩子节点
parent->_parent = subR;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
if (parent == _root)//父节点就是根节点
{
_root = subR;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
}
subR->_parent = parentParent;
subR->_left = parent;
parent->_bf = subR->_bf = 0;
}
3、左右双旋
新节点插入较高左子树的右侧
双旋的平衡因子调整相比单旋较为复杂,需要分情况讨论。
假设90为parent,60为subL,30为subLR。
- 如果新节点插入到parent的左边,那么最后的平衡因子为:
parent->_bf = 1;
subL->_bf = subLR->_bf = 0;
- 如果新节点插入到parent的右边,那么最后的平衡因子为:
subL->_bf = -1;
parent->_bf = subLR->_bf = 0;
- 如果subLR就是新插入的节点(即h==0),那么最后的平衡因子为:
parent->_bf = subL->_bf = subLR->_bf = 0;
要如何判断这三种情况呢?只需要判断旋转前subLR的平衡因子即可
如果为-1,就是第一种情况;如果为1,就是第二种情况;如果为0,就是第三种情况。
void RotateLR(Node* parent)//左右双旋
{
Node* subL = parent->_left;//父节点的左孩子节点
Node* subLR = subL->_right;//左孩子的右孩子节点
int BF = subLR->_bf;//记录平衡因子,方便后面判断
RotateL(subL);//先左旋
RotateR(parent);//再右旋
//双旋完成后调整平衡因子
if (BF == 0)
{
par服务器托管网ent->_bf = subL->_bf = subLR->_bf = 0;
}
else if (BF == -1)
{
parent->_bf = 1;
subL->_bf = subLR->_bf = 0;
}
else if (BF == 1)
{
subL->_bf = -1;
parent->_bf = subLR->_bf = 0;
}
}
4、右左双旋
新节点插入较高右子树的左侧
右左双旋的逻辑和左右双旋的逻辑是一样的,只是换了个方向而已
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int BF = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (BF == 0)
{
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (BF == -1)
{
subR->_bf = 1;
parent->_bf = subRL->_bf = 0;
}
else if (BF == 1)
{
parent->_bf = -1;
subR->_bf = subRL->_bf = 0;
}
}
5、完整的insert代码
bool insert(const pair& kv)//插入
{
if (_root == nullptr)//如果此时树为空
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)//找到插入位置
{
parent = cur;
if (kv.first _kv.first)//比当前节点小
{
cur = cur->_left;//往左走
}
else if (kv.first > cur->_kv.first)//比当前节点大
{
cur = cur->_right;//往右走
}
else//有重复的
{
return false;
}
}
//找到插入的位置了
cur = new Node(kv);//创建新节点
if (parent->_kv.first _right = cur;
cur->_parent = parent;
}
else if(parent->_kv.first > kv.first)//插入父节点的左边
{
parent->_left = cur;
cur->_parent = parent;
}
//调整平衡因子
while (parent)
{
//调整父节点的平衡因子
if (parent->_left == cur)
{
parent->_bf--;
}
else if (parent->_right == cur)
{
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)//当前节点需要旋转
{
if (parent->_bf == -2 && cur->_bf == -1)//新节点插入较高左子树的左侧
{
RotateR(parent);//右单旋
}
else if (parent->_bf == 2 && cur->_bf == 1)//新节点插入较高右子树的右侧
{
RotateL(parent);//左单旋
}
else if (parent->_bf == -2 && cur->_bf == 1)新节点插入较高左子树的右侧
{
RotateLR(parent);//左右双旋
}
else if (parent->_bf == 2 && cur->_bf == -1)新节点插入较高右子树的左侧
{
RotateRL(parent);//右左双旋
}
break;//服务器托管网旋转后就不需要继续调整了
}
else//平衡因子异常
{
cout
结束。。。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: 基于ubuntu tun虚拟网卡设备完成ping的发送与模拟接收
前言 前面我们初步认识了什么是tun设备及基础的工作原理与接收文件的设备文件(节点)、虚拟网卡的启动、添加路由表等操作,为什么进一步理解tun设备与协议栈的通信理解,这次我们将应用层控制tun设备发送ping,通过read读取到,后经过手动组装icmp网络包w…