网站设计博客,网站内容添加,网站内容管理系统怎么用,网站开发中什么是站点cAVL树
1. 前言
map/multimap、set/multiset这几个容器的共同点是#xff1a;它们的底层都是按照搜索二叉树来实现的#xff0c;但是搜索二叉树存在一个缺陷#xff1a;如果往树中插入的元素有序或接近有序#xff0c;二叉树搜索就会退化成单支树#xff0c;时间复杂度会…cAVL树
1. 前言
map/multimap、set/multiset这几个容器的共同点是它们的底层都是按照搜索二叉树来实现的但是搜索二叉树存在一个缺陷如果往树中插入的元素有序或接近有序二叉树搜索就会退化成单支树时间复杂度会退化成O(N)。
因此map、set等关联式容器的底层结构对搜索二叉树做了平衡处理即用平衡树AVL树来实现。
2. AVL树的概念
俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决二叉搜索树将退化为单支树的方法
当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1需要对树中的结点进行调整即可降低树的高度从而减少平均搜索长度。平衡因子不是必须的只是一种控制方式帮助便捷得控制树。
AVL树的性质 1.它的左右子树都是AVL树 2.左右子树高度之差简称平衡因子的绝对值不超过1(-1/0/1)平衡因子右子树高度-左子树高度 3.如果一颗二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可以保持在O(log2n)搜索时间复杂度为O(log2n) 。 3. AVL树的定义
templateclass T
struct AVLTreeNode
{AVLTreeNode(const T data):_pLeft(nullptr),_pRight(nullptr),_pParent(nullptr),_data(data),_bf(0){}AVLTreeNodeT* _pLeft;//左孩子AVLTreeNodeT* _pRight;//右孩子AVLTreeNodeT* _pParent;//该结点的父结点T_data;int _bf;
};3. AVL树的插入
AVL树是添加了平衡因子的搜索二叉树它的插入可以分成两步 1.按照搜索二叉树的方式插入新结点 2.调整平衡因子 在这颗AVL树中绿色的数字表示每个结点的平衡因子(_bf)如果左子树高度多1那么_bf减1如果右边的子树高度多1那么_bf如果左右子树高度相等那么_bf就是0 插入一个结点会对平衡因子产生影响 插入结点对平衡因子的影响 在父结点的左边插入父结点的_bf–在父结点的右边插入父结点的_bf _bf是否继续更新取决于父结点的高度是否发生变化是否影响爷结点 更新后如果_bf是0说明更新前_bf是1或-1。父结点的左右平衡了高度不变不会影响爷结点。 更新后如果_bf是1或-1说明更新前_bf是0父结点的左右不平衡了高度变化会影响爷结点。 更新后如果_bf是2或-2树就要旋转使树的结构仍符合AVL树。
判断怎么插入的方式是通过查看平衡因子的值决定的
bool Insert(const pairK, 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;while (parent){if(cur parent-_left){parent-_bf--;}else{parent-_bf;}if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){cur 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{RotateRL(parent);}break;}else{// 插入之前AVL树就有问题assert(false);}}return true;}4. AVL树的旋转
由于AVL树插入的规则是根据“比我小的插入左边比我大的插入右边”所以在某些情况下插入会导致出现不平衡的情况。这时候就需要通过旋转操作来平衡AVL树。旋转的目的是降低树的高度。 某些情况插入可能会导致出现不平衡的情况 这种情况下把结点旋转到左边树就能变回平衡了 4.1 左单旋
对于插入的结点是在右边的情况只需要把200的结点向左旋转即可。
左旋某个结点的口诀是**“我的左变成你的右你变成我的左”**。 200的左子树b变成了100的右子树100变成了200的左孩子 void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if(subRL)//b不一定有subRL-_parent parent;subR-_left parent;Node* ppnode parent-parent;parent-_parent subR;if(ppnode _root)//判断100为根结点的情况{_rootsubR;subR-_parent nullptr;}else //判断100还有父结点的情况{if(ppnode-left parent)//判断100在它父结点的左边的情况{ppnode-_left subR;}else //判断100在它父结点的右边的情况{ppnode-_right subR;}}parent-_bf 0;subR-_bf 0;
}4.2 右单旋
对于插入的结点是在左边的情况只需要把100的结点向右旋转即可。
右旋某个结点的口诀是**“我的右变成你的左你变成我的右”**。 void RotateR(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}subL-_bf 0;parent-_bf 0;}4.3 双旋
双旋也有两种情况可以分为先左单旋再右单旋的结构和先右单旋再左单旋的结构
4.3.1 左右双旋
如果插入的结点在中间且左高右低这时候不能直接在这个层面上操作还需要把b拆开然后再对插入的左或右子树进行先左旋再右旋的操作 那么此时需要分三种情况讨论
插入的结点在中间结点的左子树 插入的结点在中间结点的右子树
如果插入的结点在150的右边那么其实操作和上面类似只是最后的平衡因子不一样 中间结点就是被插入的结点本身
如果150就是被插入的结点操作也是一样的先左单旋再右单旋 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-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1)//插入在中间结点的右边{subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf 0)//中间结点就是插入结点{subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false);}}4.2 右左双旋
如果插入的结点在中间且左低右高需要把b拆开然后再对插入的左或右子树进行先右旋再左旋的操作 插入的结点在中间结点的左子树 插入的结点在中间结点的右子树 中间的结点就是插入结点本身 void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);subRL-_bf 0;if (bf 1){subR-_bf 0;parent-_bf -1;}else if (bf -1){parent-_bf 0;subR-_bf 1;}else{parent-_bf 0;subR-_bf 0;}}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first [ root-_bf ] endl;_InOrder(root-_right);}void InOrder(){_InOrder(_root);}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;}int Height(){return _Height(_root);}5. AVL树的检查
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步 1.验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树 2.验证其为平衡树 每个节点子树高度差的绝对值不超过1注意节点中如果没有平衡因子 节点的平衡因子是否计算正确 bool _IsBalance(Node* root, int height){if (root nullptr){height 0;return true;}int leftHeight 0, rightHeight 0;if (!_IsBalance(root-_left, leftHeight) || !_IsBalance(root-_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) 2){cout root-_kv.first不平衡 endl;return false;}if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}height leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;}bool IsBalance(){int height 0;return _IsBalance(_root, height);}6. AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即O(log2n)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。
因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的即不会改变可以考虑AVL树但一个结构经常修改就不太适合。 t root-_kv.first “平衡因子异常” endl; return false; } height leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;
}bool IsBalance()
{int height 0;return _IsBalance(_root, height);
}## 6. AVL树的性能AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即**O(log2n)**。但是**如果要对AVL树做一些结构修改的操作性能非常低下**比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的即不会改变可以考虑AVL树但一个结构经常修改就不太适合。
