自学内容网 自学内容网
自学内容网 > 正文

c++ AVLTree实现，插入公式

🕗 发布于 2024-07-21 03:13 算法  c++  基础语法  学习  数据结构  

概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1.它的左右子树都是AVL树
2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）
 

节点设计

我们首先要知道avl树它的底层其实是一颗树，所以我们在设计avl树的节点的时候可以设计成类似链表那种类型的封装类。

template<class K,class V>
struct avltnode
{
K _key;                //key值
V _value;              //key对应的value
avltnode* _left;       //左节点
avltnode* _right;      //右节点
avltnode* _parent;     //父节点
int bf = 0;            //平衡因子
avltnode() = default;  //默认构造
avltnode(const K&key, const V& value) :_key(key), _value(value), _left(nullptr), _right(nullptr), _parent(nullptr) {}
};

我们再去搞一个类去封装这些节点

template<class K,class V>
class avlt
{
public:
typedef avltnode<K,V> avltnode;

avlt() = default;

private:
avltnode* _node=nullptr;
};


inset函数基本逻辑


 1. 先按照二叉搜索树的规则将节点插入到AVL树中
 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否
破坏了AVL树 的平衡性root(插入节点)插入后，rootp(插入节点的父节点)的平衡因子一定需要调整，在插入之前，rootp的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
1. 如果root插入到rootp的左侧，只需给rootp的平衡因子-1即可
2. 如果root插入到rootp的右侧，只需给rootp的平衡因子+1即可
此时：rootp的平衡因子可能有三种情况：0，正负1， 正负2
1. 如果rootp的平衡因子为0，说明插入之前rootp的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功
2. 如果rootp的平衡因子为正负1，说明插入前rootp的平衡因子一定为0，插入后被更新成正负1，此时以rootp为根的树的高度增加，需要继续向上更新
3. 如果pParent的平衡因子为正负2，则rootp的平衡因子违反平衡树的性质，需要对其进行旋转处理

代码

bool insert(K key, V value)
{
if (_node == nullptr)
{
_node = new avltnode(key, value);
return true;
}
avltnode* root = _node;
avltnode* rootp = _node;
while(root)
{
if(key<root->_key)
{
rootp = root;
root = root->_left;
}
else if (key > root->_key)
{
rootp = root;
root = root->_right;
}
else
{
return false;
}
}
avltnode *newnode = new avltnode(key, value);
if (newnode->_key < rootp->_key)
{
rootp->_left = newnode;
}
else
{
rootp->_right = newnode;
}
newnode->_parent = rootp;

avltnode* cur = newnode;
//旋转代码
while (rootp)
{
if (rootp->_left == cur)
{
rootp->bf--;
}
else
{
rootp->bf++;
}

if (rootp->bf == 0)
{
break;
}
else if (rootp->bf == 1 || rootp->bf == -1)
{
cur = rootp;
rootp = rootp->_parent;
}
else if (rootp->bf == 2 || rootp->bf == -2)
{
if (rootp->bf == 2 && cur->bf == 1)
{
rotateL(rootp);
}
else if (rootp->bf == -2 && cur->bf == -1)
{
rotateR(rootp);
}
else if (rootp->bf == 2 && cur->bf == -1)
{
rotateRL(rootp);
}
else if (rootp->bf == -2 && cur->bf == 1)
{
rotateLR(rootp);
}
        break;//旋转完之后就不需要进入循环了
}
else
assert(false);

}


return true;
}

右旋

我们大的方向就是这样20是我们平衡因子为2的地方，subr是p(简写parent)的左边，subrl是subl的右边。
最基本的代码：

然后我们需要处理各自父节点的变化，一集更新各自的平衡因子

完整代码：
 

void rotateR(avltnode* rootp)
{
avltnode* subL = rootp->_left;
avltnode* sunLR = subL->_right;

rootp->_left = sunLR;
if (sunLR)
{
sunLR->_parent = rootp;
}


avltnode* rootpp = rootp->_parent;
subL->_right = rootp;
rootp->_parent = subL;

if (rootpp == nullptr)
{
_node = subL;
subL->_parent = nullptr;
}
else
{
if (rootpp->_left == rootp)
{
rootpp->_left = subL;
}
else
{
rootpp->_right = subL;
}
subL->_parent = rootpp;
}
subL->bf = rootp->bf = 0;

}

左旋

左旋类似于右旋

这里是rootp的平衡因子为2，cur平衡因子为1的时候需要左旋
代码：

void rotateL(avltnode*rootp)
{
avltnode* subR = rootp->_right;
avltnode* subRL = subR->_left;

rootp->_right = subRL;
if (subRL)
subRL->_parent = rootp;

subR->_left = rootp;
avltnode* rootpp = rootp->_parent;
rootp->_parent = subR;

if (rootpp == nullptr)
{
_node = subR;
subR->_parent = nullptr;
}
else
{
if (rootpp->_left == rootp)
{
rootpp->_left = subR;
}
else
{
rootpp->_right = subR;
}
subR->_parent = rootpp;
}
subR->bf = rootp->bf = 0;

}

左右双旋

当我们的rootp->bf == -2 && cur->bf == 1这时候我们就需要左右双旋。


将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。
这里的60就是我们subLR，这时候我们需要根据b的平衡因子的情况再来更新其他平衡因子。
具体代码：

void rotateLR(avltnode* rootp)
{
avltnode* subL = rootp->_left;
avltnode* subLR = subL->_right;
int b = subLR->bf;    //我们将subLR赋值给b
rotateL(rootp->_left);
rotateR(rootp);
if (b == 0)//当b==0的时候
{
subL->bf = 0;
subLR->bf = 0;
rootp->bf = 0;
}
else if (b == 1)//当b==1的时候
{
rootp->bf = 0;
subLR->bf = 0;
subL->bf = -1;
}
else if (b == -1)//当b==-1的时候
{
rootp->bf = 1;
subLR->bf = 0;
subL->bf = 0;
}
}

右左双旋

当我们的rootp->bf == 2 && cur->bf == -1这时候我们就需要右左双旋。

原理同上~
具体代码：

void rotateRL(avltnode* rootp)
{
avltnode*subR = rootp->_right;
avltnode* subRL = subR->_left;
int b = subRL->bf;
rotateR(rootp->_right);
rotateL(rootp);
if (b == 0)
{
subR->bf = 0;
subRL->bf = 0;
rootp->bf = 0;
}
else if (b == 1)
{
subR->bf = 0;
subRL->bf = 0;
rootp->bf = -1;
}
else if (b == -1)
{
rootp->bf = 0;
subRL->bf = 0;
subR->bf = 1;
}
else
assert(false);

}

大的基本思路就完成了
 


原文地址：https://blog.csdn.net/zgwnb666/article/details/140542736

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024