文章目录
- AVL树
- 节点类
- 节点类的构造函数
- AVL
- insert()插入
- RotateL(左单旋)
- RotateR(右单旋)
- RotateLR(右双旋)
- RotateRL(左双旋)
- Find(查找)
- IsBalance(检查是否是avl树)
AVL树
AVL树:又名高度平衡树，在二叉搜索树的基础上加上了一个条件，条件是左右子树高度差不超过1。
节点类
节点类：更好的管理节点
这里我选择的是右子树-左子树作为平衡因子，有平衡因子更方便实现
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;//balance factor 平衡因子:右子树-左子树的值 不超过1
pair<K, V> _kv;
};
节点类的构造函数
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
,_kv(kv)
{
}
AVL
因为是高度平衡所以我们要一直控制他的高度，使其达到平衡
template<class K, class V>
class AVLTree
{
public:
typedef AVLTreeNode<K, V> Node;
private:
Node* _root;
};
insert()插入
插入规则:
1、按照搜索树的规则
2、更新平衡因子
3、更新因子规则 : c是p的左边 bf-- c是p的右边 ++
4、更新因子后， p的bf == 0 那么不会影响爷爷,说明更新前 p的bf为1 or -1 ，p的矮的那一边插入了节点.
如果更新后 p的bf == 1 or -1 那么就会影响爷爷.并且往上更新
更新后p的bf==2 那么旋转处理
bool Insert(const pair<K,V>& kv)
{
if (_root == nullptr)//树为空的情况
{
_root = new Node(kv);//直接做根节点
return true;
}
Node* parent = nullptr;//因为cur是局部变量函数走完会销毁，所以增加一个指针 链接cur
Node* cur = _root;//赋值为根代替根操作
while (cur)
{
//插入的值的key值比较
//大往右 小往左
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else//如果有这个值了返回false 因为avl树中不能有同样的值
{
return false;
}
}
cur = new Node(kv);//new一个新节点赋值给cur
if (parent->_kv.first < kv.first)//大就链右边 小链左边
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;//让新节点指向其父节点
//因为插入了
//所以要修改parent的平衡因子
while (parent)
{
if (cur == parent->_left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0)
//更新 前为 1或者-1 更新后树就平衡了
//结束
{
break;
}
else if (parent->_bf == 1 || parent->_bf - 1)
//之前为 0 更新会影响祖先
//继续往上
{
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
//需要发生旋转
//旋转是为了满足搜索树的规则
//减少当前树的高度到达平衡
//旋转后结束
{
if (parent->_bf == 2 && cur->_bf == 1)//左单旋
{
RotateL(parent);
}
else if(parent->_bf == -2 && cur->_bf == -1)//右单旋
{
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)//左双旋
{
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)//右双旋
{
RotateLR(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
}
RotateL(左单旋)
以图来介绍
25是传过来的parent
我们定义parent的右为subR(也就是cur)，定义cur的左为subRL(也就是cur->left)
我们旋转的时候把subRL给到parent的左边
然后把parent给到subR的左边
这样子就完成了左单旋
最后修改一下平衡因子就可以了
void RotateL(Node* parent)//左旋转
{
//定义p的右边为 subR p的右节点的左节点为 subRL
//subRL可能是一个子树的根节点
Node* subR = parent->_right;//cur
Node* subRL = subR->_left;//cur->_left
//把p的右边给 p的右边的左边 因为他一点比p大比p的右边小
parent->_right = subRL;
//把p的右边 链接p 让p的右边成为根
if(subRL)//可能为空
subRL->_parent = parent;
subR->_left = parent;
//保存一份p的父节点 因为原来的p要改父节点了
Node* ppnode = parent->_parent;
//p的父节点指向他原来的右子树
parent->_parent = subR;
//判断p是不是树根节点
//如果是的话 让root改一下 他的父节点设置为空
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else//如果不是树根节点
{
//如果原来的p是p父节点的左边 那么让他的左边链接现在的sub(原p右节点)
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
//如果是右边 那么同理
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
//最后改好后让他的平衡因子变一下
//因为已经平衡了所以p 的因子成为了0 subr 左右树高平衡了所以也要改成0
parent->_bf = 0;
subR->_bf = 0;
}
RotateR(右单旋)
以图来介绍
20是传过来的parent
我们定义parent的左为subL(也就是cur)，定义cur的右为subLR(也就是cur->left)
我们旋转的时候把subRL给到parent的左边
然后把parent给到subL的右边
这样子就完成了右单旋
最后修改一下平衡因子就可以了
void RotateR(Node* parent)//右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)//可能为空
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else//如果不是树根节点
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
parent->_bf = 0;
subL->_bf = 0;
}
RotateLR(右双旋)
以图解释
右双旋就是先左单旋，后右单旋
对subL进行左单旋,获得图2
然后parent进行右单旋
获得图3
最后后平衡一下平平衡因子
void RotateLR(Node* parent)//先左单旋 后右单旋 右双旋
{
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
RotateL(parent->_left);
RotateR(parent);
//用 _bf来查看是谁插入
if (subLR->_bf == -1)
{
//b位置插入
subLR->_bf = 0;
subL->_bf = 1;
parent->_bf = 0;
}
else if (subLR->_bf == 1)
{
//c位置插入
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (subLR->_bf == 0)
{
//新增
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
RotateRL(左双旋)
以图解释
左双旋就是先右单旋，后左单旋
对subR进行右单旋,获得图2
然后对parent进行左单旋
获得图3
最后后平衡一下平平衡因子
Find(查找)
查找一个数
大了往左找，小了往右找
bool _Find(Node* _root,const K& x)
{
if (_root == nullptr)
{
return false;
}
if (_root->_kv.first == x)
{
return true;
}
return _Find(_root->_left,x) || _Find(_root->_right,x);
}
bool Find(const K& x)
{
return _Find(_root, x);
}
IsBalance(检查是否是avl树)
检查是否是AVL树
从规则入手
int _Height(Node* root)
{
if (root == nullptr)
return 0;
return _Height(root->_left) + _Height(root->_right) + 1;
}
bool _IsBalance(Node* Root)
{
// 空树也是AVL树
if (nullptr == Root) return true;
// 计算Root节点的平衡因子：即Root左右子树的高度差
int leftHeight = _Height(Root->_left);
int rightHeight = _Height(Root->_right);
int diff = rightHeight - leftHeight;
// 如果计算出的平衡因子与Root的平衡因子不相等，或者
// Root平衡因子的绝对值超过1，则一定不是AVL树
if (diff != Root->_bf || (diff > 1 || diff < -1))
return false;
// Root的左和右如果都是AVL树，则该树一定是AVL树
return _IsBalance(Root->_left) && _IsBalance(Root -> _right);
}
bool IsBalance()
{
_IsBalance(_root);
}
