AVL树的旋转剖析、插入实现、以及判断是不是一棵平衡树或二叉搜索树
程序员文章站
2022-06-07 08:15:23
...
AVL树(平衡树)是绝对平衡的。
1.概念:
左右子树的高度之差的绝对值不超过1。
一棵AVL树可以为空树,或者具有以下性质的树:
(1)左右子树都为AVL树。
(2)左右子树的高度之差的绝对值不超过1。
2.旋转
旋转 | 场景 |
---|---|
左单旋 | 较高右子树的右侧 |
右单旋 | 较高左子树的左侧 |
先右旋后左旋 | 插入结点在较高左子树的右侧 |
先左旋后右旋 | 插入结点在较高右子树的左侧 |
左单旋:较高右子树的右侧
//左单旋(插入在较高右子树的右侧)
void RotateL(PNode pParent)
{
PNode subR = pParent->_pRight;
PNode subRL = subR->_pLeft;
PNode ppParent = pParent->_parent;
pParent->_pRight = subRL;
subR->_pLeft = pParent;
if (subRL)//subRL存在
subRL->_parent = pParent;
if (pParent == _pRoot)
_pRoot = subR;
else if (ppParent->_pLeft ==pParent)
{
subR->_parent = ppParent;
ppParent->_pLeft = subR;
}
else
{
subR->_parent = ppParent;
ppParent->_pRight = subR;
}
//更新平衡因子
pParent->bf = subR->bf = 0;
}
右单旋:较高左子树的左侧
//右单旋(插入在较高左子树的左侧)
void RotateR(PNode pParent)
{
PNode subL = pParent->_pLeft;
PNode subLR = subL->_pRight;
PNode ppParent = pParent->_parent;
pParent->_pLeft = subLR;
subL->_pRight = pParent;
if (subLR)
subLR->_parent = pParent;
if (pParent == _pRoot)
_pRoot = subL;
else if (ppParent->_pLeft == pParent)
{
subLR->_parent = ppParent;
ppParent->_pLeft = subL;
}
else
{
subLR->_parent = ppParent;
ppParent->_pRight = subL;
}
//更新平衡因子
pParent->bf = subL->bf = 0;
}
先右旋后左旋:插入结点在较高左子树的右侧
//先右单旋后左单旋(插入在较高左子树的右侧)
void RotateRL(PNode pParent)
{
PNode subR = pParent->_pRight;
PNode subRL = subR->_pLeft;
int bf = 0;
if (subRL)
bf = subRL->bf;
RotateR(subR);
RotateL(pParent);
//更新平衡因子
if (bf == 1 || bf == -1)
subR->bf = pParent->bf = 0;
}
先左旋后右旋:插入结点在较高右子树的左侧
//先左单旋后右单旋(插入在较高右子树的左侧)
void RotateLR(PNode pParent)
{
PNode subL = pParent->_pLeft;
PNode subLR = subL->_pRight;
int bf = 0;
if(subLR)
bf = subLR->bf;
RotateL(subL);
RotateR(pParent);
//更新平衡因子
if (bf == 1)
subL->bf = -1;
else if (bf == -1)
pParent->bf = 1;
}
3.插入
①空树—->直接插入
②非空—->找待插入的位置—>更新(平衡因子)
双亲的平衡因子 | 插入左子树 | 插入右子树 |
---|---|---|
-1 | -2 | 0 |
0 | -1 | 1 |
1 | 0 | 2 |
调整双亲的平衡因子后如果为0,不需更新。
如果为-1/1,向上更新,不满足平衡因子,分情况旋转
//插入结点
bool Insert(const K& key, const V& value)
{
PNode pCur = _pRoot;
PNode pParent = NULL;
//树为空
if (_pRoot == NULL)
{
_pRoot = new Node(key, value);
return true;
}
//树非空
//1.找到待插入的结点的位置
while (pCur)
{
if (key == pCur->_key)
return false;
else if (key < pCur->_key)
{
pParent = pCur;
pCur = pCur->_pLeft;
}
else
{
pParent = pCur;
pCur = pCur->_pRight;
}
if (pCur)
pCur->_parent = pParent;
}
//2.插入
pCur =new Node(key, value);
if (key<pParent->_key)
pParent->_pLeft = pCur;
if (key>pParent->_key)
pParent->_pRight = pCur;
//3.更新平衡因子
while (pParent)
{
if (key < pParent->_key)
pParent->bf--;
else
pParent->bf++;
if (pParent->bf == 0)//结束平衡化处理
break;
else if (pParent->bf == -1 || pParent->bf == 1)
{
//向上更新
pCur = pParent;
pParent = pCur->_parent;
}
else
{
//分情况旋转
if (pParent->bf == 2)//右子树高
{
if (pCur->bf == 1)
RotateL(pParent);//左单旋转
else
RotateRL(pParent);//先右后左旋转
}
else//左子树高
{
if (pCur->bf == -1)
RotateR(pParent);//右单旋转
else
RotateLR(pParent);//先左后右旋转
}
break;
}
}
return true;
}
4.判断是否为一棵平衡树或二叉搜索树
判断一个树是否为二叉搜索树:中序遍历—>有序
判断二叉搜索树是否为平衡树:IsBalanced
空树—>平衡
树存在—->求左右子树的高度,判断是否平衡(abs(左,右)<2)
public:
//中序遍历,检查是否为二叉搜索树
void InOrder()
{
if (_pRoot)
_InOrder(_pRoot);
}
//判断是否平衡
void IsBalance()
{
if (_pRoot)
_IsBalance(_pRoot);
}
private:
bool _IsBalance(PNode pRoot)
{
if (pRoot == NULL)
return true;
else
{
int hL = Height(pRoot);
int hR = Height(pRoot);
int a = hR - hL;
if (abs(a) >= 2)
return false;
return _IsBalance(pRoot->_pLeft) && _IsBalance(pRoot->_pRight);
}
}
//求二叉树的高度
size_t Height(PNode& pRoot)
{
if (pRoot == NULL)
return 0;
else if (pRoot->_pLeft == NULL&&pRoot->_pRight == NULL)
return 1;
else
return Height(pRoot->_pLeft) > Height(pRoot->_pRight) ? (Height(pRoot->_pLeft) + 1): (Height(pRoot->_pRight) + 1);
}
5.删除
空树—->跳出
双亲的平衡因子 | 删除左子树 | 删除右子树 |
---|---|---|
-1 | 0 | -2 |
0 | 1 | -1 |
1 | 2 | 0 |
完整代码:
#pragma once
#include <iostream>
using namespace std;
#include <math.h>
template <class K, class V>
struct AVLNode
{
AVLNode(const K& key, const V& value)
: _pLeft(NULL)
, _pRight(NULL)
, _parent(NULL)
, _key(key)
, _value(value)
, bf(0)
{}
AVLNode<K, V>* _pLeft;
AVLNode<K, V>* _pRight;
AVLNode<K, V>* _parent;
K _key;
V _value;
int bf;
};
template <class K, class V>
class AVLTree
{
public:
typedef AVLNode<K, V> Node;
typedef Node* PNode;
//构造函数
AVLTree()
:_pRoot(NULL)
{}
//插入结点
bool Insert(const K& key, const V& value)
{
PNode pCur = _pRoot;
PNode pParent = NULL;
//树为空
if (_pRoot == NULL)
{
_pRoot = new Node(key, value);
return true;
}
//树非空
//1.找到待插入的结点的位置
while (pCur)
{
if (key == pCur->_key)
return false;
else if (key < pCur->_key)
{
pParent = pCur;
pCur = pCur->_pLeft;
}
else
{
pParent = pCur;
pCur = pCur->_pRight;
}
if (pCur)
pCur->_parent = pParent;
}
//2.插入
pCur =new Node(key, value);
if (key<pParent->_key)
pParent->_pLeft = pCur;
if (key>pParent->_key)
pParent->_pRight = pCur;
//3.更新平衡因子
while (pParent)
{
if (key < pParent->_key)
pParent->bf--;
else
pParent->bf++;
if (pParent->bf == 0)//结束平衡化处理
break;
else if (pParent->bf == -1 || pParent->bf == 1)
{
//向上更新
pCur = pParent;
pParent = pCur->_parent;
}
else
{
//分情况旋转
if (pParent->bf == 2)//右子树高
{
if (pCur->bf == 1)
RotateL(pParent);//左单旋转
else
RotateRL(pParent);//先右后左旋转
}
else//左子树高
{
if (pCur->bf == -1)
RotateR(pParent);//右单旋转
else
RotateLR(pParent);//先左后右旋转
}
break;
}
}
return true;
}
//中序遍历,检查是否为二叉搜索树
void InOrder()
{
if (_pRoot)
_InOrder(_pRoot);
}
//判断是否平衡
void IsBalance()
{
if (_pRoot)
_IsBalance(_pRoot);
}
private:
//左单旋(插入在较高右子树的右侧)
void RotateL(PNode pParent)
{
PNode subR = pParent->_pRight;
PNode subRL = subR->_pLeft;
PNode ppParent = pParent->_parent;
pParent->_pRight = subRL;
subR->_pLeft = pParent;
if (subRL)//subRL存在
subRL->_parent = pParent;
if (pParent == _pRoot)
_pRoot = subR;
else if (ppParent->_pLeft ==pParent)
{
subR->_parent = ppParent;
ppParent->_pLeft = subR;
}
else
{
subR->_parent = ppParent;
ppParent->_pRight = subR;
}
//更新平衡因子
pParent->bf = subR->bf = 0;
}
//右单旋(插入在较高左子树的左侧)
void RotateR(PNode pParent)
{
PNode subL = pParent->_pLeft;
PNode subLR = subL->_pRight;
PNode ppParent = pParent->_parent;
pParent->_pLeft = subLR;
subL->_pRight = pParent;
if (subLR)
subLR->_parent = pParent;
if (pParent == _pRoot)
_pRoot = subL;
else if (ppParent->_pLeft == pParent)
{
subLR->_parent = ppParent;
ppParent->_pLeft = subL;
}
else
{
subLR->_parent = ppParent;
ppParent->_pRight = subL;
}
//更新平衡因子
pParent->bf = subL->bf = 0;
}
//先右单旋后左单旋(插入在较高左子树的右侧)
void RotateRL(PNode pParent)
{
PNode subR = pParent->_pRight;
PNode subRL = subR->_pLeft;
int bf = 0;
if (subRL)
bf = subRL->bf;
RotateR(subR);
RotateL(pParent);
//更新平衡因子
if (bf == 1 || bf == -1)
subR->bf = pParent->bf = 0;
}
//先左单旋后右单旋(插入在较高右子树的左侧)
void RotateLR(PNode pParent)
{
PNode subL = pParent->_pLeft;
PNode subLR = subL->_pRight;
int bf = 0;
if(subLR)
bf = subLR->bf;
RotateL(subL);
RotateR(pParent);
//更新平衡因子
if (bf == 1)
subL->bf = -1;
else if (bf == -1)
pParent->bf = 1;
}
//中序遍历
void _InOrder(PNode pRoot)
{
if (!pRoot)
return;
_InOrder(pRoot->_pLeft);
cout << "<" << pRoot->_key << "," << pRoot->_value << ">" << endl;
_InOrder(pRoot->_pRight);
}
bool _IsBalance(PNode pRoot)
{
if (pRoot == NULL)
return true;
else
{
int hL = Height(pRoot);
int hR = Height(pRoot);
int a = hR - hL;
if (abs(a) >= 2)
return false;
return _IsBalance(pRoot->_pLeft) && _IsBalance(pRoot->_pRight);
}
}
//求二叉树的高度
size_t Height(PNode& pRoot)
{
if (pRoot == NULL)
return 0;
else if (pRoot->_pLeft == NULL&&pRoot->_pRight == NULL)
return 1;
else
return Height(pRoot->_pLeft) > Height(pRoot->_pRight) ? (Height(pRoot->_pLeft) + 1): (Height(pRoot->_pRight) + 1);
}
private:
PNode _pRoot;
};
void AVLTreeTest()
{
int array[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
AVLTree<int, int> tree;
for (size_t i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
tree.Insert(array[i], array[i]);
tree.InOrder();
tree.IsBalance();
}
上一篇: 积树成林 --- 平衡二叉树到底平不平衡,他说了算!树旋转
下一篇: 午餐肉的危害