文章目录
前言
本文章将会模拟实现一棵AVL树。
以下是本篇文章正文内容
一、什么是AVL树？
AVL树也是一个二叉搜索树，只不过是在二叉搜索树的基础上，增加了一个条件：
任意一棵子树的左右高度差的绝对值不大于1。
设计AVL树的原因
在二叉平衡搜索树中，在正常情况下，对该树的任意节点进行查找，最多查找OlogN次，但如果在极端情况下，该树退化成了单只树，则会极大降低搜索效率，变成O(n)，所以为了避免让二叉搜索树出现极端情况，设计出一棵具有平衡性质的二叉搜索树：AVL树
二、AVL树的性质
- 1）它的左右子树都是AVL树
- 2）左右子树高度之差（平衡因子）的绝对值不超过1（-1/0/1）
平衡因子：右子树高度 - 左子树的高度（注意是右 - 左）
由此可知，一棵AVL树是高度平衡的，它的高度可保持在logN，所以搜索效率可以保持在logN
三、二叉树节点的定义
template<class K, class V>
class AVLTreeNode
{
public:
AVLTreeNode(const pair<K, V> kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;
};
- 1）需要有一个平衡因子存在，即
_bf - 2）_data值可以是一个键值对，也可以是其他类型，这里我选择了
pair。 - 3）在后面的其他操作中，会频繁用到一个节点的父亲，所以直接在节点中添加一个
_parent成员。
四、AVL树的插入
插入大致分为几个步骤：
如果根节点为空，则直接插入到根节点的位置
1）先找到插入位置，因为这是一棵搜索树，如果该节点的值比根小，则往左走，如果比根大，往右边走。
2）找到待插入位置后，插入该节点，然后调整平衡因子。
如果插入的是左边，则parent的平衡因子–，如果插入的是右边，则parent的平衡因子++。
如果parent的平衡因子是1或-1，说明父亲的子树有一边高了，则需要继续向上调整。(最坏情况就是调整平衡因子到根的位置)
如果parent的parent的平衡因子大于1或者小于-1了，则不满足AVL树的特性，需要进行旋转。
旋转
1）右单旋
新插入的节点在根节点的左侧，导致根节点的平衡因子变成-2。
则需要将根节点进行右旋。
规则如下：
- 1）cur的right给parent的left
- 2）parent变成了cur的right
调整后，cur变成了新的根，parent变成cur的right
此时需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后cur变成新的根，需要替代parent的位置，变成那个节点的孩子。
如果旋转前parent就是根，则直接让旋转后的cur的parent为空即可。
调整后cur和parent的平衡因子变成0。
2）左单旋
新插入的节点在根节点的右侧，导致根节点的平衡因子变成2。
则需要将根节点进行左旋。
规则如下：
- 1）cur的left给parent的right
- 2）parent变成了cur的left
调整后，cur变成了新的根，parent变成curr的left
此时需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后cur变成新的根，需要替代parent的位置，变成那个节点的孩子。
如果旋转前parent就是根，则直接让旋转后的cur的parent为空即可。
调整后cur和parent的平衡因子变成0。
3）左右双旋
插入新节点后，如果cur的平衡因子为1，parent的平衡因子为-2
说明整颗树的结构大概是这样的：
这就说明，此时这棵树不再是AVL树，所以我们需要对其进行旋转。
旋转操作如下：
- 1）让cur的右指向curright的左，然后cur成为curright的左。此时curright的父亲就变成了原来的cur的父亲，cur的父亲变成了curright
以上操作是左旋的操作过程
- 2）让parent的左指向curright的右，然后parent变成了curright的右，此时parent的父亲变成了curright。
以上操作是右旋的操作过程
这里还需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后curright变成新的根，需要替代parent的位置，变成那个节点的孩子。
平衡因子的处理：
-
- 1）如果旋转之前，curright的平衡因子是0，则说明，curright这个节点，一定是新插入的节点。
（因为如果不是新插入的节点，在插入该节点前，这棵树就不是AVL树了）。
在进行左右双旋后，cur，curright，parent三个节点的平衡因子都是0。
-
- 2）如果旋转之前，curright这个节点的平衡因子是-1，该情况就是上图画出的情况，说明新插入节点在curright的左子树，在左右双旋后，cur和curright的平衡因子变成0，parent的平衡因子是1
-
- 3）如果旋转之前，curright这个节点的平衡因子是1，说明新插入节点在curright的右子树，在左右双旋后，parent和curright的平衡因子变成0，cur的平衡因子是-1
4）右左双旋
插入新节点后，如果cur的平衡因子为-1，parent的平衡因子为2
说明整颗树的结构大概是这样的：
这就说明，此时这棵树不再是AVL树，所以我们需要对其进行右左旋转。
旋转操作如下：
- 1）让cur的左指向curleft的右，然后cur成为curleft的右。此时culeft的父亲就变成了原来的cur的父亲，cur的父亲变成了curleft
以上操作是右旋的操作过程
- 2）让parent的右指向curleft的左，然后parent变成了curleft的左，此时parent的父亲变成了curleft。
以上操作是左旋的操作过程
这里还需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后currleft变成新的根，需要替代parent的位置，变成那个节点的孩子。
平衡因子的处理：
-
- 1）如果旋转之前，curleft的平衡因子是0，则说明，curleft这个节点，一定是新插入的节点。
（因为如果不是新插入的节点，在插入该节点前，这棵树就不是AVL树了）。
在进行左右双旋后，cur，curleft，parent三个节点的平衡因子都是0。
-
- 2）如果旋转之前，curleft这个节点的平衡因子是1，该情况就是上图画出的情况，说明新插入节点在curleft的右子树，在右左双旋后，cur和curleft的平衡因子变成0，parent的平衡因子是-1
-
- 3）如果旋转之前，curleft这个节点的平衡因子是-1，说明新插入节点在curleft的左子树，在右左双旋后，parent和curleft的平衡因子变成0，cur的平衡因子是1
以上就是旋转的四种情况。
AVL树插入完整代码
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(nullptr)
{}
bool Insert(const pair<K,V> kv)
{
if(_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* cur_parent = _root;
//1.找到待插入位置
while (cur)
{
if (cur->_kv.first < kv.first)
{
cur_parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
cur_parent = cur;
cur = cur->_left;
}
else
return false;
}
//2.先判断待插入节点是在parent的左边还是右边
cur = new Node(kv);
if (cur_parent->_kv.first > kv.first)
{
cur_parent->_left = cur;
}
else
{
cur_parent->_right = cur;
}
cur->_parent = cur_parent;
//下面为调整二叉树的平衡
//1.更新平衡因子
//
while (cur_parent)
{
//左子树--
if (cur_parent->_left == cur)
{
cur_parent->_bf--;
}
//右子树++
else
{
cur_parent->_bf++;
}
//平衡因子=0，不再影响祖先
if (cur_parent->_bf == 0)
{
break;
}
//不平衡了，影响祖先，要向上也调整
else if (cur_parent->_bf == 1 || cur_parent->_bf == -1)
{
cur = cur_parent;
cur_parent = cur_parent->_parent;
}
//此时该树出问题了，需要旋转进行平衡
else if (cur_parent->_bf == 2 || cur_parent->_bf == -2)
{
//右边高，向左旋转
if (cur_parent->_bf == 2 && cur->_bf == 1)
{
RotateL(cur_parent);
}
//左边高，向右旋转
else if (cur_parent->_bf == -2 && cur->_bf == -1)
{
RotateR(cur_parent);
}
//折线型，右边高，右左双旋
else if (cur_parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(cur_parent);
}
//折线形，左边高，左右双旋
else if (cur_parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(cur_parent);
}
//旋转完成后一定平衡了，则break
break;
}
else
{
assert(false);
}
}
cout << kv.first << endl;
return true;
}
//左单旋
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
Node* ppNode = parent->_parent;
parent->_right = curleft;
if (curleft)
curleft->_parent = parent;
cur->_left = parent;
parent->_parent = cur;
if (!ppNode)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppNode->_right == parent)
{
ppNode->_right = cur;
}
else
{
ppNode->_left = cur;
}
cur->_parent = ppNode;
}
cur->_bf = parent->_bf = 0;
}
//右单旋
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
Node* ppNode = parent->_parent;
parent->_left = curright;
//如果cur的右子树是空
if(curright)
curright->_parent = parent;
cur->_right = parent;
parent->_parent = cur;
if (!ppNode)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
cur->_parent = ppNode;
//要知道根的左边是cur还是右边是cur
if (ppNode->_left == parent)
{
ppNode->_left = cur;
}
else
{
ppNode->_right = cur;
}
}
cur->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
int bf = curright->_bf;
RotateL(parent->_left);
RotateR(parent);
//该节点为新插入的节点
if (bf == 0)
{
curright->_bf = 0;
cur->_bf = 0;
parent->_bf = 0;
}
//新插入节点在curright的右边，右边高了
// p
// c
// cr
else if (bf == 1)
{
curright->_bf = 0;
cur->_bf = -1;
parent->_bf = 0;
}
//新插入节点在curright的左边，左边高了
else if (bf == -1)
{
curright->_bf = 0;
cur->_bf = 0;
parent->_bf = 1;
}
}
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf;
RotateR(parent->_right);
RotateL(parent);
//该节点为新插入的节点
if (bf == 0)
{
curleft->_bf = 0;
cur->_bf = 0;
parent->_bf = 0;
}
//新插入节点在curleft的右边，右边高了
// p
// c
// cl
else if (bf == 1)
{
curleft->_bf = 0;
cur->_bf = 0;
parent->_bf = -1;
}
//新插入节点在curleft的左边，左边高了
else if (bf == -1)
{
curleft->_bf = 0;
cur->_bf = 1;
parent->_bf = 0;
}
}
private:
Node* _root = nullptr;
};
验证一棵树为AVL树
- 1）验证这棵树的中序遍历是有序的。
- 2）验证每一棵树的左右子树高度差不大于1
int Height(Node* root)
{
if (root == nullptr)
return 0;
int left = Height(root->_left);
int right = Height(root->_right);
return left > right ? left + 1 : right + 1;
}
bool IsBalanceTree()
{
cout << "IsBalanceTree():";
return _IsBalanceTree(_root);
}
//通过高度判断是否为AVL树
//1.通过高度计算出真实的平衡因子，再与AVL树本身的平衡因子进行比较
bool _IsBalanceTree(Node* root)
{
if (root == nullptr)
return true;
int lefth = Height(root->_left);
int righth = Height(root->_right);
int bf = righth - lefth;
if (bf != root->_bf || bf > 1 || bf < -1)
{
return false;
}
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
AVL树的性能分析
由于AVL树的绝对平衡（每棵树高度差不大于1），每次在插入数据时，难免会遇到多次旋转，最坏情况需要旋转到根部。虽然旋转时间复杂度O(1)，但如果旋转次数过多，也会造成效率下降。在本文中没有提到AVL树的删除，删除操作更加复杂，我没有研究过hh，不过同样每删除一个数据，都必须保证整棵树是AVL树，这又需要大量旋转来维持它的平衡。
所以在面对大量数据，并且不再有新数据的插入时，可以使用AVL树进行查找，效率为O(logN).
总结
本文主要讲述了AVL树的插入过程及其效率分析。