自学内容网 自学内容网
自学内容网 > 正文

【数据结构】AVL树

🕗 发布于 2024-11-15 18:55 算法  c++  数据结构  

        引言：在实际情况中，数据不仅仅要存储起来，还要进行对数据进行搜索，为了方便进行高效搜索(在此之前的数据结构的搜索基本都是暴力搜索)二叉搜索树应运而生。但是在极端情况下(我们按照有序的方式进行插入)，二叉搜索树就会退化成单支树(每个结点最多只有一个孩子结点，其实就是链表)，效率变为O(N),效率低下。

        两位俄罗斯的数学家提出了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。这个时候AVL树这种数据结构就诞生了，增删查改搜索效率非常高，效率可以达到O(logN)。158b587e364247ffa78f42904e8e9969.jpeg

AVL树(平衡二叉树)的概念

        平衡二叉树，全称为平衡二叉搜索树，简称AVL树。英文：Balanced Binary Tree （BBT），注：二叉查找树(BST)

平衡因子的概念

平衡因子（bf）：结点的右子树的深度减去左子树的深度。
即： 结点的平衡因子 = 右子树的高度 - 左子树的高度

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树:

  1. 它的左右子树都是AVL树
  2. 左右子树高度之差(简称平衡因子)的绝对值不超过1

d3a91ac269ca446bb4fdb10c843df75d.png

AVL树 节点的定义

template<class K，class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K, V>& kv)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _kv(kv), _bf(0)
{}
AVLTreeNode<T>* _pLeft; // 该节点的左孩子
AVLTreeNode<T>* _pRight; // 该节点的右孩子
AVLTreeNode<T>* _pParent; // 该节点的双亲
pair<K, V> _kv;
int _bf; // 该节点的平衡因子
};

AVL树的插入

        AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么，AVL树的插入过程可以分为两步：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子(如果调节过程中出现平衡因子2/-2，则根据情况判断进行旋转)

平衡因子的更新

是否继续更新依据：子树的高度是否变化

1、parent->_bf == 0 说明之前parent->_bf== 1 或者 -1

说明之前parent一边高一边低，这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新

2、parent->_bf == 1 或 -1 说明之前parent->_bf == 0

两边一样高，现在插入一边更高了，parent所在子树高度变了，继续往上更新
3、parent->_bf == 2 或 -2，说明之前parent->_bf == 1 或者 -1

插入之后不平衡了，违反规则，需要进行旋转处理

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;
    //调整节点的平衡因子
// 1、更新平衡因子
while (parent) // parent为空，也就更新到根
{
// 新增在右，parent->bf++;
// 新增在左，parent->bf--;
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)
{
                //插入位置在左子树的右子树下的结点
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
                //插入位置在右子树的左子树下的结点
RotateRL(parent);
}
else
{
assert(false);
}

break;
}
else
{
assert(false);
}
}
return true;
}

AVL树的旋转

        如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

  • 新节点插入较高右子树的右侧---右右：左单旋
  • 新节点插入较高左子树的左侧---左左：右单旋
  • 新节点插入较高左子树的右侧---左右：先左单旋再右单旋
  • 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

旋转之后要保证
1、让这颗子树左右高度不超过1
2、旋转过程中继续保持他是搜索树
3、更新调整孩子节点的平衡因子
4、让这颗子树的高度跟插入前保持一致

插入结点的路径如果是直线那么就是单旋，单旋的重点在于旋转的过程的实现。

35f2113581b5403684cca70d47e8fbc5.jpeg

void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;

parent->_right = subRL;
if (subRL)
subRL->_parent = parent;

Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;


if (ppNode == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}

subR->_parent = ppNode;
}

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;
}

Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;

//if (_root == parent)
if (ppNode == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}

subL->_parent = ppNode;
}

subL->_bf = parent->_bf = 0;
}

插入结点的路径如果是折线那么就是双旋，双旋就是进行两次单旋，所以双旋的重点在于平衡因子的更新，要按照旋转前subLR或者subRL结点的平衡因子(0/1/-1)进行分情况讨论

void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;

RotateL(parent->_left);
RotateR(parent);

if (bf == -1) // subLR左子树新增
{
subL->_bf = 0;
parent->_bf = 1;
subLR->_bf = 0;
}
else if (bf == 1) // subLR右子树新增
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == 0) // subLR自己就是新增
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_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 = parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)
{
subRL->_bf = subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == 0)
{
parent->_bf = subRL->_bf = subR->_bf = 0;
}
else
{
assert(false);
}
}

AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

  • 验证其为二叉搜索树：
    • 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
  • 验证其为平衡树：
    • 每个节点子树高度差的绝对值不超过1(注意节点中可能没有平衡因子)
    • 节点的平衡因子是否计算正确
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}

_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}

int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

bool _IsBalanceTree(Node* root)
{
// 空树也是AVL树
if (nullptr == root)
return true;
// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;

// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
// pRoot平衡因子的绝对值超过1，则一定不是AVL树
if (abs(diff) >= 2)
{
cout << root->_kv.first << "高度差异常" << endl;
return false;
}

if (root->_bf != diff)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}

// pRoot的左和右如果都是AVL树，则该树一定是AVL树
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

AVL树的性能

        AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log2(N)。但是如果要对AVL树做一些结构修改的操
作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，
有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数
据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

        下一篇博客我们会介绍条件没那么苛刻且更为常用的红黑树。


原文地址：https://blog.csdn.net/2302_80026357/article/details/143660900

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024