【数据结构】AVL树

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

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

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

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

平衡因子的概念

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

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

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

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树的插入过程可以分为两步：

按照二叉搜索树的方式插入新节点
调整节点的平衡因子(如果调节过程中出现平衡因子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、让这颗子树的高度跟插入前保持一致

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

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树，但一个结构经常修改，就不太适合。

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/471694.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！