1. 概念
平衡二叉树 (AVL Tree) 首先要满足二叉树的定义, 如下
二叉排序树或者是一棵空树, 或者是具有下列性质的二叉树:
若左子树不空, 则左子树上所有结点的值均小于它的根结点的值;
若右子树不空, 则右子树上所有结点的值均大于它的根结点的值;
左, 右子树也分别为二叉排序树;
没有键值相等的节点.
平衡度是左子树高度减去右子树高度, 平衡度只能是 - 1,+1,0
下图给出了一个非平衡二叉排序树和平衡二叉排序树
说明: 结点上方的数字是平衡度(平衡因子),a 图 9 结点左子树比右子树高 2, 不满足 AVL Tree 的定义, 所以是非平衡树
b 图所有结点度数绝对值没有超过 1, 所以满足平衡树的定义, 是平衡树
危机结点是指平衡度为 1, 有可能破坏平衡树的结点
左改组是指新结点插入到危机结点的左树下
右改组是指新新结点插入到危机结点的右子树下
LL 是新结点插入在危机节点的左子树的左子树上
LR 是新结点插入在危机节点的左子树的右子树上
RR 是新结点插入在危机节点的右子树的右子树上
RL 是新结点插入在危机节点的右子树的左子树上
2. 代码实现
当前树的结构
- 11
- / \
- 7 15
- / \ / \
- 3 9 14 18
- / \ / / \
- 1 5 12 16 20
- /
- 26
2.1 定义平衡树结点:
平衡因子可以是右子树高度减去左子树高度, 不同的教材定义不一样, 我这里按照左树 - 右树来做
- template<class K, class V>
- struct AVLTreeNode
- {
- K _key; // 树权值
- V _value;
- int _bf; // 平衡因子 -1,0,1 (每个节点的平衡因子等于左子树的高度减去右子树的高度)
- // 有的教材定义平衡度是左子树高度减去右子树, 都是可以的
- AVLTreeNode<K, V>* _parent; // 指向父节点的指针
- AVLTreeNode<K, V>* _left; // 指向左孩子的指针
- AVLTreeNode<K, V>* _right; // 指向右孩子的指针
- AVLTreeNode(const K& key = K(), const V& value = V())
- :_key(key)
- , _value(value)
- , _bf(0)
- , _parent(NULL)
- , _left(NULL)
- , _right(NULL)
- {}
- };
2.2 左改组图解
左右改组是为了方便我们插入删除的时候保持二叉树平衡而引入的概念
左改组 LL 型和 LR(a),LR(b),LR(c)型图解
2.3 左改组 LL 型
首先声明一个构造的左子树, subL 其实就是危机结点, subLR 是危机节点的右子树, ppNode 是祖先节点
构建 parent 子树, 将 parent 和 subL 连接起来
如果祖先结点为空, 将当前结点 subL 置为根节点, 请参见上图 (a') 的情况, B 是危机结点, 调整过后变成了根节点
否则祖父结点赋给 subL 的父结点, 判断父节点是否是祖先结点的左子树, 是的话, 用构造的左子树替代之
不是就用 subL 替代祖先节点的右子树
- // 左改组 LL 型
- template<class K, class V>
- void AVLTree<K, V>::_RotateLL(AVLTreeNode<K, V>*& parent)
- {
- AVLTreeNode<K, V>* subL = parent->_left; // 构造的左子树
- AVLTreeNode<K, V>* subLR = subL->_right;//subL 的右子树
- AVLTreeNode<K, V>* ppNode = parent->_parent;// 标记祖先节点
- //1. 构建 parent 子树 将 parent 和 subLR 链接起来
- parent->_left = subLR;
- if (subLR) subLR->_parent = parent;
- //2. 构建 subL 子树 将 subL 与 parent 链接起来
- subL->_right = parent;
- parent->_parent = subL;
- //3. 将祖先节点与 subL 链接起来
- if (ppNode == NULL)
- { // 如果祖先为 NULL, 说明当前 subL 节点为根节点
- subL->_parent = NULL;
- _root = subL;
- }
- else
- {
- subL->_parent = ppNode;
- if (ppNode->_left == parent)
- ppNode->_left = subL;
- else if (ppNode->_right == parent)
- ppNode->_right = subL;
- }
- //4. 重置平衡因子
- parent->_bf = 0;
- subL->_bf = 0;
- //5. 更新 subL 为当前父节点
- parent = subL;
- }
2.4 左改组 LR(a),LR(b)和 LR(c)型
pNode 是当前父节点, subR 是构造的右子树, subLR 是 subR 的左子树
对当前父节点 LL 左改组, 再右改组
根据平衡因子判断是 LR 什么类型, 请参见上图图解 (b),(c),(d) 的情况
- // 左改组 LR 型
- template<class K, class V>
- void AVLTree<K, V>::_RotateLR(AVLTreeNode<K, V>*& parent)
- {
- AVLTreeNode<K, V>* pNode = parent;
- AVLTreeNode<K, V>* subR = parent->_right;
- AVLTreeNode<K, V>* subLR = subR->_left;
- int bf = subLR->_bf;
- _RotateLL(parent->_right);
- _RotateRR(parent);
- //LR(b)型
- if (bf == -1)
- {
- pNode->_bf = 0;
- subR->_bf = 1;
- }
- //LR(a)型
- else if (bf == 1)
- {
- pNode->_bf = -1;
- subR->_bf = 0;
- }
- //LR(c)型
- else
- {
- pNode->_bf = 0;
- subR->_bf = 0;
- }
- }
右改组和左改组镜像对称, 反过来就行了
2.5 插入函数
AVL 树是空, 将当前结点直接置为根节点
AVL 树在满足平衡度的要求下, 和二叉排序树一致, key 小于当前结点, 转到当前结点左子树, key 大于当前结点, 转到当前结点右子树
将 parent 的左子树赋予当前结点, 更新平衡因子,_bf++
将 parent 的右子树赋予当前结点, 更新平衡因子,_bf--
如果合法, 即平衡因子 = 0, 终止当前循环
如果当前结点是危机结点, 即平衡度绝对值等于 1, 当前结点往上回溯, 变成父节点, 继续检查它的平衡度
接下来是平衡异常的情况, 父结点平衡度为 2, 当前结点 (危机结点) 平衡度为 1, 进入左改组 LL,LL 介绍参考 2.2 左改组 LL
当前结点平衡度为 - 1, 进入左改组 LR,LR 介绍参考 2.3 左改组 LR
右改组的情况类似
- template<class K, class V>
- bool AVLTree<K, V>::Insert(const K& key, const V& value)
- {
- //1. 空树
- if (_root == NULL)
- {
- _root = new AVLTreeNode<K, V>(key, value);
- return true;
- }
- //2.AVL 树不为 NULL
- AVLTreeNode<K, V>* parent = NULL;
- AVLTreeNode<K, V>* cur = _root;
- // 找到数据插入位置
- while (cur)
- {
- if (cur->_key <key)
- {
- parent = cur;
- cur = cur->_right;
- }
- else if (cur->_key> key)
- {
- parent = cur;
- cur = cur->_left;
- }
- else
- {
- return false;
- }
- }
- // 插入数据
- cur = new AVLTreeNode<K, V>(key, value);
- cur->_parent = parent;
- if (parent->_key> key)
- parent->_left = cur;
- else
- parent->_right = cur;
- while (parent)
- {
- // 更新平衡因子
- if (cur == parent->_left)
- parent->_bf++;
- else if (cur == parent->_right)
- parent->_bf--;
- // 检验平衡因子是否合法
- if (parent->_bf == 0)
- break;
- else if (parent->_bf == -1 || parent->_bf == 1)
- { // 回溯上升 更新祖父节点的平衡因子并检验合法性
- cur = parent;
- parent = cur->_parent;
- }
- // 2 -2 平衡因子不合法 需要进行旋转 降低高度
- else
- {
- if (parent->_bf == -2)
- {
- if (cur->_bf == -1)
- _RotateRR(parent);
- else
- _RotateLR(parent);
- }
- else if (parent->_bf == 2)
- {
- if (cur->_bf == 1)
- _RotateLL(parent);
- else
- _RotateRL(parent);
- }
- break;
- }
- }
- }
2.6 遍历方法
- // 中序遍历
- template<class K, class V>
- void AVLTree<K, V>::_InOrder(AVLTreeNode<K, V>* root)
- {
- if (root == NULL)
- return;
- _InOrder(root->_left);
- cout <<root->_key <<" ";
- _InOrder(root->_right);
- }
- // 前序遍历
- template<class K, class V>
- void AVLTree<K, V>::_PreOrder(AVLTreeNode<K, V>* root)
- {
- if (root == NULL)
- return;
- cout <<root->_key <<" ";
- _PreOrder(root->_left);
- _PreOrder(root->_right);
- }
- // 后序遍历
- template<class K, class V>
- void AVLTree<K, V>::_PostOrder(AVLTreeNode<K, V>* root)
- {
- if (root == NULL)
- return;
- _PostOrder(root->_left);
- _PostOrder(root->_right);
- cout <<root->_key << " ";
- }
3. 运行和源码
运行效果如下
源代码:
来源: https://www.cnblogs.com/Java-Starter/p/10192034.html