文章目录
1. 搜索树
1.1. 理解二叉搜索树
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
如图所示
- 当进行数据搜索时
- 进行数据插入时过程与数据搜索相同, 找到一个适合自己的空节点
- 数据删除
1.2. 搜索树性能分析
- 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能.
- 理想情况下, 插入的树是完全二叉树
- 最坏情况下, 插入的树成了单链树
- 最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logn
- 最差情况下，二叉搜索树退化为单支树，其平均比较次数为：n / 2
2. AVL树
2.1. 理解AVL树
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下. 因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
-
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 ，搜索时间复杂度O(logn)
2.2. AVL树节点的数据结构
template <class T>
class AVLTreeNode
{
public:
AVLTreeNode(T data)
: _data(data)
, _pLeft(nullptr)
, _pRight(nullptr)
, _pParent(nullptr)
, _bf(0)
{ }
T _data;
AVLTreeNode<T>* _pLeft;
AVLTreeNode<T>* _pRight;
AVLTreeNode<T>* _pParent;
int _bf; // 该节点平衡因子
};
2.3. AVL树的插入
AVL树的插入过程可以分为两步：
1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子
- 新增节点的平衡因子是0, 新增节点的祖先平衡因子可能受影响
1. 新增在parent的右子树, parent->bf + = 1
2. 新增在parent的左子树, parent->bf - = 1 - 通过cur的位置更新parent的平衡因子, 更新完成后
1. 如果parent->bf == 1 / -1, 说明parent为根的子树的高度变了, 继续向上更新
2. 如果parent->bf == 2 / -2, 说明parent为根的子树已经不平衡, 需要旋转处理
3. 如果parent->bf == 0, 说明parent所在的子树原来高度是 1/-1,现在把矮的补齐, parent所在的子树高度不变, 停止更新
bool insert(const T& data)
{
// 如果树内无节点
if (_pRoot == nullptr)
{
_pRoot = new Node(data);
return true;
}
// 1. 按照二叉搜索树的方式插入新节点
Node* pCur = _pRoot;
Node* parent = nullptr;
while (pCur)
{
parent = pCur;
if (data < pCur->_data)
{
pCur = pCur->_pLeft;
}
else if (data > pCur->_data)
{
pCur = pCur->_pRight;
}
else
{
// 插入相同节点, 返回失败
return false;
}
}
pCur = new Node(data);
if (parent->_data < data)
{
parent->_pRight = pCur;
}
else
{
parent->_pLeft = pCur;
}
pCur->_pParent = parent;
// 2. 调整节点的平衡因子
while (parent != nullptr)
{
if (parent->_pLeft == pCur)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
pCur = parent;
parent = pCur->_pParent;
}
else if (parent->_bf == -2 || parent->_bf == 2)
{
// 旋转操作
}
}
return true;
}
2.4. AVL树的旋转*
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种:
- 新节点插入较高左子树的左侧—左左：右单旋
- 注意判断parent的父节点和subLR是否存在
void RotateR(Node* parent)
{
Node* pSubL = parent->_pLeft;
Node* pSubLR = pSubL->_pRight;
pSubL->_pRight = parent;
Node* pParent = parent->_pParent;
parent->_pParent = pSubL;
if (pSubLR != nullptr)
{
pSubLR->_pParent = parent;
}
parent->_pLeft = pSubLR;
if (parent == _pRoot)
{
_pRoot = pSubL;
pSubL->_pParent = nullptr;
}
else
{
if (pParent->_pLeft == parent)
{
pParent->_pLeft = pSubL;
}
else
{
pParent->_pRight = pSubL;
}
pSubL->_pParent = pParent;
}
parent->_bf = pSubL->_bf = 0;
}
- 新节点插入较高右子树的右侧—右右：左单旋
void RotateL(Node* parent)
{
Node* pSubR = parent->_pRight;
Node* pSubRL = pSubR->_pLeft;
pSubR->_pLeft = parent;
Node* pParent = parent->_pParent;
parent->_pParent = pSubR;
parent->_pRight = pSubRL;
if (pSubRL != nullptr)
pSubR->_pParent = parent;
if (parent == _pRoot)
{
_pRoot = pSubR;
pSubR->_pParent = nullptr;
}
else
{
if (pParent->_pRight == parent)
{
pParent->_pRight = pSubR;
}
else
{
pParent->_pLeft = pSubR;
}
pSubR->_pParent = pParent;
}
parent->_bf = pSubR->_bf = 0;
}
- 新节点插入较高左子树的右侧—左右：先左单旋再右单旋
- 共会出现三种可能的情况
注意观察闪电标志的平衡因子, 可以分析得到这三个点不同插入情况下平衡因子的值- 完善上方代码可得
void RotateLR(Node* parent)
{
Node* pSubL = parent->_pRight;
Node* pSubLR = pSubR->_pLeft;
int bf = pSubLR->_bf;
RotateL(parent->_pLeft);
RotateR(parent);
if (bf == 1)
{
parent->_bf = 0;
pSubL->_bf = 1;
pSubLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
pSubL->_bf = 0;
pSubLR->_bf = 0;
}
else
{
parent->_bf = 0;
pSubL->_bf = 0;
pSubLR->_bf = 0;
}
}
- 新节点插入较高右子树的左侧—右左：先右单旋再左单旋
同情况三代码如下:
void RotateRL(Node* parent)
{
Node* pSubR = parent->_pRight;
Node* pSubRL = pSubR->_pLeft;
int bf = pSubRL->_bf;
RotateR(parent->_pRight);
RotateL(parent);
if (bf == 1)
{
parent->_bf = -1;
pSubR->_bf = 0;
pSubRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
pSubR->_bf = 1;
pSubRL->_bf = 0;
}
else
{
parent->_bf = 0;
pSubR->_bf = 0;
pSubRL->_bf = 0;
}
}
2.5. AVL树的删除
因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置.
2.6. AVL树性能分析
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合. 此时, 红黑树就出场了!
完.