你的时间有限, 所以不要为别人而活, 不要被教条所限, 不要活在别人的观念里, 不要让别人的意见左右自己内心的声音. -- 乔布斯
正文开始
博客主页: 酷酷学!!!
二叉搜素树虽然可以缩短查找的效率, 但如果数据有序或接近有序二叉搜索树将退化为单支树, 查找元素相当于在顺序表中搜索元素, 效率低下, 因此, 两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法: 当向二叉搜索树中插入新节点后, 如果能保证每个节点的左右子树高度之差的绝对值不超过1(需要对树中的节点进行调整), 即可降低树的高度, 从而减少平均搜索长度.
一棵AVL树或者是空树, 或者是具有以下性质的二叉搜素树:
如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在
,搜索时间复杂度O(
)。
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;//balance factor
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _parent(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};
AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步:
// 1. 先按照二叉搜索树的规则将节点插入到AVL树中
// 2. 新节点插入后,AVL树的平衡性可能会遭到破坏,此时就需要更新平衡因子,并检测是否破坏了AVL树的平衡性
/*
pCur插入后,pParent的平衡因子一定需要调整,在插入之前,pParent
的平衡因子分为三种情况:-1,0, 1, 分以下两种情况:
1. 如果pCur插入到pParent的左侧,只需给pParent的平衡因子-1即可
2. 如果pCur插入到pParent的右侧,只需给pParent的平衡因子+1即可
此时:pParent的平衡因子可能有三种情况:0,正负1, 正负2
1. 如果pParent的平衡因子为0,说明插入之前pParent的平衡因子为正负1,插入后被调整成0,此时满足AVL树的性质,插入成功
2. 如果pParent的平衡因子为正负1,说明插入前pParent的平衡因子一定为0,插入后被更新成正负1,此时以pParent为根的树的高度增加,需要继续向上更新
3. 如果pParent的平衡因子为正负2,则pParent的平衡因子违反平衡树的性质,需要对其进行旋转处理
*/
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//更新平衡因子
while (parent)
{
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent == -1)
{
//祖先受到影响
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//不平衡了,旋转处理
}
else
{
assert(false);
}
}
return true;
}
上述过程可以抽象为 左单旋
假设h为大于等于0的AVL子树, 做单旋的情况如下
编写代码:
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
}
核心代码就是让subRL变成parent的左边, parent变成subR的右边. 但是不要忘了, 我们拥有了parent节点和平衡因子带给我们的遍历, 所以更不要忘了进行维护
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
if (subRL)
subRL->_parent = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
parentParent->_left = subR;
else
parentParent->_right = subR;
subR->_parent = parentParent;
}
parent->_bf = subR->_bf = 0;
}
有了左单旋的理解, 不难写出右单旋
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
parentParent->_left = subL;
else
parentParent->_right = subL;
subL->_parent = parentParent;
}
parent->_bf = subL->_bf = 0;
}
对于这种情况, 左单旋使右边节点多, 把左边压下去, 这中可以解决.
对于这种情况, 单纯依靠左单旋是无法进行解决的了,因为左单旋会把新subRL给到parent的右边, 所以左右还是达不到平衡
对于h==1也是一样
如何解决呢? 先以subR作为旋转点进行右旋,然后再左旋.
抽象图如下:
进行一层一层的分析
但是插入之后我们还需要更改平衡因子,关键看subRL的平衡因子, 是在subRL的左边插入还是右边插入, 所以插入之前我们需要先保存subRL的平衡因子, 再以结果为导向进行直接的修改.
如果subRL为0, 说明使h==0的情况, 此时右左旋转之后三者平衡因子都为0, 其它节点不变, h>0时如下:
在c插入时, 插入时, subRL为1, 最后旋转之后, 平衡因子应更新为parent->_bf = -1.
在c插入时, 插入时, subRL为-1, 最后旋转之后, 平衡因子应更新为subR->_bf = 1.
编写代码:
//右左旋转
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
编写代码:
//左右单旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else
{
assert(false);
}
}
#pragma once
#include<assert.h>
#include<iostream>
using namespace std;
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;//balance factor
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()
:_root(nullptr)
{}
AVLTree(const AVLTree<K, V>& t)
{
_root = Copy(t._root);
}
AVLTree<K, V>& operator=(AVLTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
~AVLTree()
{
Destory(_root);
_root = nullptr;
}
//插入
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//更新平衡因子
while (parent)
{
if (cur == parent->_left)
parent->_bf--;
else
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)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else
{
RotateLR(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
}
//查找
Node* Find(const pair<K, V>& kv)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
int Height()
{
return _Height(_root);
}
bool IsBalanceTree()
{
return _IsBalanceTree(_root);
}
private:
bool _IsBalanceTree(Node* pRoot)
{
// 空树也是AVL树
if (nullptr == pRoot) return true;
// 计算pRoot节点的平衡因子:即pRoot左右子树的高度差
int leftHeight = _Height(pRoot->_left);
int rightHeight = _Height(pRoot->_right);
int diff = rightHeight - leftHeight;
// 如果计算出的平衡因子与pRoot的平衡因子不相等,或者
// pRoot平衡因子的绝对值超过1,则一定不是AVL树
if (diff != pRoot->_bf || (diff > 1 || diff < -1))
return false;
// pRoot的左和右如果都是AVL树,则该树一定是AVL树
return _IsBalanceTree(pRoot->_left) && _IsBalanceTree(pRoot->_right);
}
int _Height(Node* pRoot)
{
if (pRoot == nullptr) return 0;
int heightl = _Height(pRoot->_left);
int heightr = _Height(pRoot->_right);
return heightl > heightr ? heightl + 1 : heightr + 1;
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
if (subRL)
subRL->_parent = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
parentParent->_left = subR;
else
parentParent->_right = subR;
subR->_parent = parentParent;
}
parent->_bf = subR->_bf = 0;
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
parentParent->_left = subL;
else
parentParent->_right = subL;
subL->_parent = parentParent;
}
parent->_bf = subL->_bf = 0;
}
//右左旋转
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
//左右单旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else
{
assert(false);
}
}
void Destory(Node* root)
{
if (root == nullptr) return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
AVLTree* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newnode = new Node(root->_kv);
newnode->_left = Copy(root->_left);
newnode->_right = Copy(root->_right);
return newnode;
}
Node* _root;
};
VL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:
bool _IsBalanceTree(Node* pRoot)
{
// 空树也是AVL树
if (nullptr == pRoot) return true;
// 计算pRoot节点的平衡因子:即pRoot左右子树的高度差
int leftHeight = _Height(pRoot->_left);
int rightHeight = _Height(pRoot->_right);
int diff = rightHeight - leftHeight;
// 如果计算出的平衡因子与pRoot的平衡因子不相等,或者
// pRoot平衡因子的绝对值超过1,则一定不是AVL树
if (diff != pRoot->_bf || (diff > 1 || diff < -1))
return false;
// pRoot的左和右如果都是AVL树,则该树一定是AVL树
return _IsBalanceTree(pRoot->_left) && _IsBalanceTree(pRoot->_right);
}
int _Height(Node* pRoot)
{
if (pRoot == nullptr) return 0;
int heightl = _Height(pRoot->_left);
int heightr = _Height(pRoot->_right);
return heightl > heightr ? heightl + 1 : heightr + 1;
}
//avl.h
void TestAVLTree()
{
AVLTree<int, int> t;
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
for (auto e : a)
{
t.Insert({ e, e });
}
//cout << t.Height() << endl;
t.InOrder();
cout << t.IsBalanceTree() << endl;
}
//test.c
#include"avl.h"
int main()
{
TestAVLTree();
return 0;
}
因为AVL树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不错与删除不同的时,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。(面试一般不考察)
具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。
AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即
。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。
假如以pParent为根的子树不平衡,即pParent的平衡因子为2或者-2,分以下情况考虑
旋转完成后,原pParent为根的子树个高度降低,已经平衡,不需要再向上更新。
完