AVL树 相关函数实现

AVL树

AVL树是在平衡二叉树的基础上，保持左右子树高度差不超过1。用参数_bf控制。

我们可以定义如果在节点cur的右边新增节点，_bf++。左边就_bf--。当_bf==2/-2时说明左右子树高度差超过1，就需要进行处理保持高度差在1内。

节点结构

template<class K,class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _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 AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree() = default;

AVLTree(const AVLTree<K,V>& t)
{
_root = Copy(t._root);
}
private:
Node*_root = nullptr;
Node* Copy(Node* root)
{

if (root == nullptr) return nullptr;
Node* cur = new Node(root->_kv);
cur->_left = Copy(root->_left);
cur->_right = Copy(root->_right);

if (cur->_left) cur->_left->_parent = cur;
if (cur->_right) cur->_right->_parent = cur;
return cur;
}
};

链接父母节点，也可以把父母节点当作第二个参数传过来。这样就不用进行判断了。

Node* Copy(Node* root,Node*parnet)
{

if (root == nullptr) return nullptr;
Node* cur = new Node(root->_kv);
cur->_parent = parent;
cur->_left = Copy(root->_left,cur);
cur->_right = Copy(root->_right,cur);
return cur;
}

析构函数

~AVLTree()
{
Destroy(_root);
_root = nullptr;
}

void Destroy(Node* root)
{
if (root == nullptr) return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}

赋值

AVLTree<K, V>& operator=(AVLTree<K,V> t)
{
swap(_root, t._root);
return *this;
}

插入

bool Insert(const pair<K, V> kv)
{
//没有节点直接插入
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//找对应的位置 有相同的值返回false
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else return false;
}
//判断该位置是左孩子还是右孩子
cur = new Node(kv);
if (kv.first > parent->_kv.first) parent->_right = cur;
else parent->_left = cur;

cur->_parent = parent;
//调节平衡因子_bf
while (parent)
{
//在左子树插入-- 右子树插入++
if (cur == parent->_left) parent->_bf--;
else parent->_bf++;
//左右子树平衡 break
if (parent->_bf == 0) break;
//半平衡 向上调整_bf 直到parent->_bf==2/-2时进行旋转
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)
RotateL(parent);
//右单旋
else if (parent->_bf == -2 && cur->_bf == -1)
RotateR(parent);
//先对parent的右子树右旋 再对parent整体左旋
else if (parent->_bf == 2 || parent->_bf == -1)
RotateRL(parent);
//先对parent的左子树右旋 再对parent整体右旋
else 
RotateLR(parent);
}
//出错终止
else assert(parent->_bf > -2 && cur->_bf < 2);
}
return true;
}

左旋转

新节点插入较高右子树的右侧 左单旋

我们把_bf为2/-2的节点（30）设为parent，parent->_right（60）设为subR，subR->_left(也就是b)设为subRL。此时parent->_bf== 2 subR->_bf== 1

1.b成为30的右孩子（当h=0时，b为空节点）

2.30成为60的左孩子

3.60继承30的父母节点。如果30为根，那么60成为新的根节点。反之，于30的父母节点相连接。

此时30，60节点的左右子树高度差均为0。

void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentP = parent->_parent;
//1.b成为30的右孩子
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
//2.30成为60的左孩子
subR->_left = parent;
parent->_parent = subR;
//3.60继承30的父母节点。
if (parentP == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
subR->_parent = parentP;
if (parentP->_left == parent) parentP->_left = subR;
else parentP->_right = subR;
}
//调节_bf
parent->_bf = subR->_bf = 0;
}

右旋转

新节点插入较高左子树的左侧 右单旋。此时parent->_bf==-2 subL->_bf==-1

右单旋和左单旋逻辑一致。

60：parent     30:subL    b:subLR

void RotateR(Node* parent)
{
Node* subL =parent->_left;
Node* subLR = subL->_right;
Node* parentP = parent->_parent;

parent->_left = subLR;
if (subLR) subLR->_parent = parent;

subL->_right = parent;
parent->_parent = subL;

if (parentP == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
subL->_parent = parentP;
if (parentP->_left == parent) parentP->_left = subL;
else parentP->_right = subL;
}
parent->_bf = subL->_bf = 0;
}

左右双旋

新节点插入较高左子树的右侧---左右：先左单旋再右单旋

此时parent->_bf==-2 subL->_bf==1

遇到这种情况仅靠一次右旋是不能完成平衡的。

90:parent      30:subL     60:subLR     

1.先对30的右子树进行一次左旋。

2.再对以90为根的树进行右旋。

3.对节点_bf进行调整。因为经过两次旋转，parnet,subL,subLR的_bf都改成了0，很明显与实际不符，所以要对_bf再进行调整。

分为h=0和h>0，h>0又可以分2种情况。共3种情况

当节点插入后

1.(subLR->_bf==0) h=0,60:subLR自己就是新增节点。在_bf=0时，只有当h=0，才会导致树不平衡。

2.(subLR->_bf==-1)新增节点在b子树上，此时30:subL的左右子树正好相等,_bf为0。90:parent左子树比右子树小1，右子树减左子树，_bf为1。 60:subLR的_bf一定为0。

3.(subLR->_bf==1)新增节点在c子树上，30:subL->_bf==-1   90:parent->_bf==0   60:subLR的_bf一定为0。

这个过程你可以看作60:subLR把左右子树分别给两边，自己成为根。

void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subL->_bf;
//1.先对30的右子树进行一次左旋。
RotateL(subL);
//2.再对以90为根的树进行右旋。
RotateR(parent);
//3.对节点_bf进行调整。
//h=0 自己就是新增节点
if (bf == 0)
{

subLR->_bf = 0;
parent->_bf = 0;
subL->_bf = 0;
}
//h>0
//插入右子树
else if (bf == 1)
{
subLR->_bf = -1;
parent->_bf = 0;
subL->_bf = 0;
}
//插入左子树
else if (bf == -1)
{
subLR->_bf = 0;
parent->_bf = 1;
subL->_bf = 0;
}
else assert(bf > -2 && bf < 2);
}
};

右左双旋

新节点插入较高右子树的左侧---右左：先右单旋再左单旋

此时parent->_bf==2 subL->_bf==-1

void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subR->_bf;
RotateR(subR);
RotateL(parent);
if (bf == 0)
{

subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else if (bf == 1)
{
subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else assert(bf > -2 && bf < 2);
}

总结：

假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
当pSubR的平衡因子为1时，执行左单旋
当pSubR的平衡因子为-1时，执行右左双旋
2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
当pSubL的平衡因子为-1是，执行右单旋
当pSubL的平衡因子为1时，执行左右双旋
旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。

中序遍历

void Inorder()
{
_Inorder(_root);
return;
}

void _Inorder(Node* root)
{
if (root == nullptr) return;
_Inorder(root->_left);
cout << root->_kv.first << "->" << root->_kv.second << ' ';
_Inorder(root->_right);
}

原文地址：https://blog.csdn.net/wws7920/article/details/140574613

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