四平网站制作,网站推广的方法有哪几种,做個app网站价格,建筑人才网查工程师证文章目录 1、AVL树1.1 AVL树的概念 2、AVL树节点的定义3、AVL树的插入和旋转3.1 左单旋左旋代码实现 3.2 右单旋右旋代码实现 3.3 右左双旋右左双旋的代码实现 3.4 左右双旋左右双旋的代码实现 3.5 insert接口实现 4、判断是否为AVL树判断AVL树的代码实现 5、AVL树的性能 问题引… 文章目录 1、AVL树1.1 AVL树的概念 2、AVL树节点的定义3、AVL树的插入和旋转3.1 左单旋左旋代码实现 3.2 右单旋右旋代码实现 3.3 右左双旋右左双旋的代码实现 3.4 左右双旋左右双旋的代码实现 3.5 insert接口实现 4、判断是否为AVL树判断AVL树的代码实现 5、AVL树的性能 问题引入 在上一篇文章中我们提到了二叉搜索树在插入时可能会形成单边树会降低二叉搜索的性能。因此我们需要平衡二叉搜索树降低二叉搜索树的高度使得二叉搜索树趋于一颗完全二叉树的样子这样就可以提高二叉搜索树的性能。本篇文章就来介绍一种平衡二叉树AVL树。
1、AVL树
1.1 AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在O(log N)搜索时间复杂度O(log N)。 我们了解了AVL树的基本规则后下面我们来实现一下AVL树。
2、AVL树节点的定义
template class K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;// 右子树 - 左子树 的高度差int _bf; // 平衡因子AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};3、AVL树的插入和旋转
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步 1. 按照二叉搜索树的方式插入新节点 2. 调整节点的平衡因子 当某个节点的平衡因子被修改为2的时候就需要旋转来调节因此就存在一下四种旋转方式
3.1 左单旋
我们将 左单旋的情况抽象出来如下图所示
当 h 0且parent-_bf 2 subR-_bf 1时触发左旋。 在这个图中只能是在 c 子树新增才能触发左旋的条件parent-_bf 2 subR-_bf 1。此时进行左旋。 如果是在 b 子树新增那么仅仅左旋是不够的 旋转步骤将60的左树变为30的右树将60的左树变为30最后将parent和subR的平衡因子变为0就完成了左旋。
左旋代码实现
// 左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;Node* parentParent parent-_parent;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;parent-_parent subR;if (_root parent) // 父节点就是根节点{_root subR;subR-_parent nullptr;}else // 子树情况{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}// 修改平衡因子parent-_bf subR-_bf 0;
}3.2 右单旋
我们将 右单旋的情况抽象出来如下图所示 当 h 0且 parent-_bf 2 subL-_bf -1时触发右旋。 在这个图中只能是在 a子树新增才能触发右旋的条件parent-_bf -2 subL-_bf -1。此时进行右旋。 如果是在 b 子树新增那么仅仅右旋是不够的。 旋转步骤将30的右树接到60的左树并断开与30的链接再将60接到30的右树并将60的父节点改为3最后再调整parent与SubL的平衡因子为0就完成整个右旋。
右旋代码实现
// 右单旋
void RotateR(Node* parent)
{Node* parentParent parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;parent-_parent subL;if (_root parent) // 父节点是根节点{_root subL;subL-_parent nullptr;}else // 子树情况{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}// 修改平衡因子parent-_bf subL-_bf 0;
}3.3 右左双旋
我们将 右左双旋的所有情况抽象出来如下图所示
右左双旋的本质是先将子树右旋让右侧一侧高再进行整体的左旋这样就完成了高度的调整。 双旋的插入位置可以是 b/c 子树此类型插入之后就会触发右左双旋。 旋转步骤直接复用右旋再复用左旋即可。不过旋转的基点不同右旋是以subR为基点左旋是以parent为基点旋转的。旋转就完成了难点在于平衡因子的调节。 平衡因子的调节 这里主要是 记下subRL最初的平衡因子它的平衡因子就代表了插入节点是在subRL的左边还是右边插入的由此可以推出最终的parent与subR的平衡因子。
当subRL-_bf 1时最后parent-_bf -1subR-_bf 0subRL-_bf 0;当subRL-_bf -1时最后parent-_bf 0subR-_bf 1subRL-_bf 0;当subRL-_bf 0时最后parent-_bf 0subR-_bf 0subRL-_bf 0;
右左双旋的代码实现
// 右左双旋
void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);if (bf 0) // subRL 就是插入的{parent-_bf subR-_bf subRL-_bf 0;}else if (bf 1) // subRL 右边边插入{parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else if (bf -1) // subRL 左边插入{parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else{assert(false);}
}3.4 左右双旋
我们将 右左双旋的所有情况抽象出来如下图所示
左右双旋与右左双旋的思路是差不多的我们来看看。 左右双旋的本质是先将子树左旋让左侧一侧高在进行整体的右旋,这样就完成了高度的调整。 双旋的插入位置可以是 b/c 子树此类型插入之后就会触发左右双旋。 旋转步骤直接复用左旋再复用右旋即可。不过旋转的基点不同右旋是以subR为基点左旋是以parent为基点旋转的。旋转就完成了难点也是在于平衡因子的调节。 平衡因子的调节 这里主要是 记下subLR最初的平衡因子它的平衡因子就代表了插入节点是在subLR的左边还是右边插入的由此可以推出最终的parent与subL的平衡因子。
当subLR-_bf 1时最后parent-_bf 1subL-_bf 0subLR-_bf 0;当subLR-_bf 1时最后parent-_bf 0subL-_bf -1subLR-_bf 0;当subLR-_bf 0时最后parent-_bf 0subL-_bf 0subLR-_bf 0;
左右双旋的代码实现
// 左右双旋
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(subL);RotateR(parent);if (0 bf){parent-_bf subL-_bf subLR-_bf 0;}else if (1 bf){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (-1 bf){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else{assert(false);}
}3.5 insert接口实现
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;// 1、先找到插入的位置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;}}// 2、new一个节点并与parent链接起来cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}// 3、调平横 —— 旋转 平衡因子的调节while (parent){if (parent-_left cur){parent-_bf--;}else{parent-_bf;}if (0 parent-_bf){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){RotateRL(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}// 1、旋转让这颗子树平衡了// 2、旋转降低了这颗子树的高度恢复到跟插入前一样的高度所以对上一层没有影响不用继续更新break;}else{assert(false);}}return true;
}4、判断是否为AVL树
AVL树的本质是搜索二叉树 平衡机制所以验证步骤 1、首先判断是否为搜索树写一个中序遍历看看是不是升序即可 2、按照AVL树的性质来判断
每个节点的左右子树高度差绝对值小于等于1节点的平衡因子是否正确
判断AVL树的代码实现
bool _IsBalance(Node* pRoot)
{if (pRoot nullptr)return true;int leftHeight _Height(pRoot-_left);int rightHeight _Height(pRoot-_right);if (rightHeight - leftHeight ! pRoot-_bf){cout pRoot-_kv.first 平衡因子异常 endl;return false;}return rightHeight - leftHeight 2 _IsAVLTree(pRoot-_left) _IsAVLTree(pRoot-_right);
}size_t _Height(Node* pRoot)
{if (pRoot nullptr)return 0;int leftHeight _Height(pRoot-_left);int rightHeight _Height(pRoot-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}void _InOrder(Node* pRoot)
{if (pRoot nullptr)return;_InOrder(pRoot-_left);cout pRoot-_kv.first ;_InOrder(pRoot-_right);
}5、AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即O(log N)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。 AVL树的实现代码放在代码仓库https://gitee.com/xiaobai-is-working-hard-jy/data-structure/tree/master/AVLTree
