目录
一、引言
1.1 二叉搜索树
1.2 二叉搜索树的缺陷
1.3 AVL数的引入
二、AVL树结点的定义
三、AVL树的操作
3.1 插入
3.1.1 基本步骤
3.1.2 平衡因子的调整
3.2 旋转操作(重点!)
3.2.1 右单旋
3.2.2 左单旋
3.2.3 左右双旋
3.2.4 右左双旋
3.3 插入
3.4 计算高度
3.5 计算结点数量
3.6 检查是否平衡
3.7 树的遍历(中序)
3.8 树的查找
四、树的检验
一、引言
1.1 二叉搜索树
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
1.若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树
二叉搜索树严格上不可以出现两个或以上相等的数字。
平均来说,二叉搜索树能极大地加速我们的搜索过程,如果需要检索n个数,理论上,二叉搜索树可能只需要检索log(n+1)次,如果 n=1000,二叉搜索树只需要检索9次即可。
1.2 二叉搜索树的缺陷
当插入数据完美递增或递减时,二叉搜索树会出现其不可避免的问题:
一旦出现这种情况,二叉搜索树能发挥的价值就很小了。
1.3 AVL数的引入
考虑到上述因素,数学家想到了使用平衡因子的做法,当左右子树的高度差超过某个值时,就进行某种操作,使他们重新平衡,这样就出现了AVL树:
在开始写AVL树的代码时,我们要明确一点,平衡因子的值是我们人为规定的,其等于右子树的高度减左子树的高度!
二、AVL树结点的定义
template<class T>
struct AVLTreeNode
{
T val;
AVLTreeNode<T>* _pRight;//右结点
AVLTreeNode<T>* _pLeft;//左结点
AVLTreeNode<T>* _pParent;//父亲结点
int _bf;//平衡因子
AVLTreeNode(T data)
:val(data), _right(nullptr),
_left(nullptr), _parent(nullptr), _bf(0)
{};
};
三、AVL树的操作
3.1 插入
3.1.1 基本步骤
因为AVL树是BS树的改进,所以插入数据时还是使用二叉搜索树的插入:
template<class T>
struct AVLTreeNode
{
T val;
AVLTreeNode<T>* _right;//右结点
AVLTreeNode<T>* _left;//左结点
AVLTreeNode<T>* _parent;//父亲结点
int _bf;//平衡因子
AVLTreeNode(T data)
:val(data), _right(nullptr),
_left(nullptr), _parent(nullptr), _bf(0)
{};
};
template<class T>
class AVLTree
{
typedef AVLTreeNode<T> Node;
public:
bool Insert(T data)
{
if (_root == nullptr)//如果树为空,直接插入
{
_root = new Node(data);
return true;
}
Node* parent = nullptr;//记录父结点
Node* cur = _root;//记录当前结点,该结点要遍历整棵树
while (cur)
{
if (data < cur->val)//如果插入的值小于根结点,向左走
{
parent = cur;//更新父结点
cur = cur->_left;
}
else if (data > cur->val)//如果插入的值大于根结点,向右走
{
parent = cur;
cur = cur->_right;
}
else return false;//如果走到这里一定出现了相等的数据,不可以插入
}
//new新结点插入到树中
cur = new Node<int>(data);
if (data < parent->val)
parent->_left = cur;
else
parent->_right = cur;
}
private:
Node* _root = nullptr;
};
然后再调整平衡因子。
3.1.2 平衡因子的调整
在每次插入数据时,
if 新结点插入在父结点左侧 ——> _bf--;
if 新结点插入在父结点右侧 ——> _bf++;
又因为插入数据前的树就是一棵AVL树,所以树的平衡因子只能是下述三种情况:
首先要明确插入数据后父结点平衡因子的三种情况:
1. _bf == 0 ——> 父结点左右刚好达到平衡,无需继续向上调整2. _bf == +-1 ——> 父结点左右高度差为1,需要继续向上调整
3. _bf == +-2 ——> 父结点的左右高度差为2,需要进行旋转(后面会说)
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// _bf == 2 || _bf == -2
{
}
}
3.2 旋转操作(重点!)
3.2.1 右单旋
此外,需要注意的是,在更新父结点(简称parent)的父结点(简称pparent)时,要特别注意parent在pparent的左结点还是右结点,不要把左孩子结点链接错误:
再次梳理一下需要更新的点:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//subLR
parent->_left = subLR;//左结点的右变成父结点的左
if (subLR) // 检查subL的右子节点是否存在
subLR->_parent = parent;//左结点的右的父结点变为父结点
//subL
subL->_right = parent;//父结点变成左结点的右
Node* ppNode = parent->_parent;
parent->_parent = subL;//更新父结点的父结点
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
subL->_parent = ppNode;//更新左结点的父结点
if (parent == ppNode->_left)
ppNode->_left = subL;
else
ppNode->_right = subL;
}
parent->_bf = 0;//更新父结点的平衡因子
subL->_bf = 0;//更新左结点的平衡因子
}
3.2.2 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//subRL
parent->_right = subRL;//右结点的左变成父结点的右
if (subRL) // 检查subR的左子节点是否存在
subRL->_parent = parent;//右结点的左的父变为父结点
//subR
subR->_left = parent;//父结点变成右结点的左
Node* ppNode = parent->_parent;
parent->_parent = subR;//更新父结点的父结点
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
subR->_parent = ppNode;//更新右结点的父结点
if (parent == ppNode->_left)
ppNode->_left = subR;
else
ppNode->_right = subR;
}
parent->_bf = 0;//更新父结点的平衡因子
subR->_bf = 0;//更新右结点的平衡因子
}
3.2.3 左右双旋
把左结点subL当成_root,进行左旋,使得subLR与parent链接并把subLRL旋到subL
把parent当成_root,进行右旋,把新得到的subL变成parent并把自己旋到新parent的subR上。
以下是暂时的简单代码:
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
RotateL(subL);
RotateR(parent);
}
这样可能认为左右单旋仅仅是代码的复用,但是有至关重要的一步:调节平衡因子!
因为单旋会调节平衡因子,所以在单旋前先要记录一下平衡因子以确定新插入数据的插入位置:
所以对代码进行进一步修正得:
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int _bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (_bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
3.2.4 右左双旋
原理类似于左右双旋,这里不做过多赘述。
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int _bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (_bf == -1)
{
subRL->_bf = 0;
subR->_bf = -1;
parent->_bf = 0;
}
else if (_bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else if (_bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
把旋转的知识都了解完了以后,就可以继续改插入的代码了。
3.3 插入
template<class T>
struct AVLTreeNode
{
T val;
AVLTreeNode<T>* _right;//右结点
AVLTreeNode<T>* _left;//左结点
AVLTreeNode<T>* _parent;//父亲结点
int _bf;//平衡因子
AVLTreeNode(T data)
:val(data), _right(nullptr),
_left(nullptr), _parent(nullptr), _bf(0)
{};
};
template<class T>
class AVLTree
{
typedef AVLTreeNode<T> Node;
public:
bool Insert(T data)
{
if (_root == nullptr)//如果树为空,直接插入
{
_root = new Node(data);
return true;
}
Node* parent = nullptr;//记录父结点
Node* cur = _root;//记录当前结点,该结点要遍历整棵树
while (cur)
{
if (data < cur->val)//如果插入的值小于根结点,向左走
{
parent = cur;//更新父结点
cur = cur->_left;
}
else if (data > cur->val)//如果插入的值大于根结点,向右走
{
parent = cur;
cur = cur->_right;
}
else return false;//如果走到这里一定出现了相等的数据,不可以插入
}
//new新结点插入到树中
cur = new Node<int>(data);
if (data < parent->val)
parent->_left = cur;
else
parent->_right = cur;
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)// _bf == 2 || _bf == -2
{
if (parent->_bf == -2 && parent->_left->_bf == -1)
RotateR(parent);
else if (parent->_bf == 2 && parent->_right->_bf == 1)
RotateL(parent);
else if (parent->_bf == -2 && parent->_right->_bf == 1)
RotateLR(parent);
else
RotateLR(parent);
break;
}
else
assert(false);
return true;
}
}
private:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//subLR
parent->_left = subLR;//左结点的右变成父结点的左
if (subLR) // 检查subL的右子节点是否存在
subLR->_parent = parent;//左结点的右的父结点变为父结点
//subL
subL->_right = parent;//父结点变成左结点的右
Node* ppNode = parent->_parent;
parent->_parent = subL;//更新父结点的父结点
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
subL->_parent = ppNode;//更新左结点的父结点
if (parent == ppNode->_left)
ppNode->_left = subL;
else
ppNode->_right = subL;
}
parent->_bf = 0;//更新父结点的平衡因子
subL->_bf = 0;//更新左结点的平衡因子
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//subRL
parent->_right = subRL;//右结点的左变成父结点的右
if (subRL) // 检查subR的左子节点是否存在
subRL->_parent = parent;//右结点的左的父变为父结点
//subR
subR->_left = parent;//父结点变成右结点的左
Node* ppNode = parent->_parent;
parent->_parent = subR;//更新父结点的父结点
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
subR->_parent = ppNode;//更新右结点的父结点
if (parent == ppNode->_left)
ppNode->_left = subR;
else
ppNode->_right = subR;
}
parent->_bf = 0;//更新父结点的平衡因子
subR->_bf = 0;//更新右结点的平衡因子
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int _bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (_bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int _bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (_bf == -1)
{
subRL->_bf = 0;
subR->_bf = -1;
parent->_bf = 0;
}
else if (_bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else if (_bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
private:
Node* _root = nullptr;
};
3.4 计算高度
public:
int Height()
{
return _Height(_root);
}
private:
int _Height(Node* root)
{
if (root == nullptr)
return 0;
return max(_Height(root->_left), _Height(root->_right)) + 1;
}
3.5 计算结点数量
public:
int Size()
{
return _Size(_root);
}
private:
int _Size(Node* root)
{
return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}
3.6 检查是否平衡
public:
bool isBlance()
{
return _IsBalance(_root);
}
private:
bool _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
// 不平衡
if (abs(leftHeight - rightHeight) >= 2)
{
cout << root->val << endl;
return false;
}
// 顺便检查一下平衡因子是否正确
if (rightHeight - leftHeight != root->_bf)
{
cout << root->val << endl;
return false;
}
return _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
3.7 树的遍历(中序)
public:
void InOrder()
{
_InOrder(_root);
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->val << endl;
_InOrder(root->_right);
}
3.8 树的查找
public:
Node* Find(const T x)
{
Node* cur = _root;
while (cur)
{
if (cur->_val < x)
cur = cur->_right;
else if (cur->_val > x)
cur = cur->_left;
else
return cur;
}
return nullptr;
}
四、树的检验
void TestAVLTree1()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
AVLTree<int> t1;
for (auto e : a)
{
t1.Insert({ e });
cout << "Insert:" << e << "->" << t1.IsBalance() << endl;
}
t1.InOrder();
cout << t1.IsBalance() << endl;
}