企业网站建设代理商,搜索引擎市场份额2023,开发公众号,如何百度到自己的网站AVL树 1.AVL树的概念2.平衡因子3.节点的定义4.插入操作5.旋转操作#xff08;重点#xff09;5.1左单旋5.2右单旋5.3左右双旋5.4右左双旋 6.一些简单的测试接口7.完整代码 1.AVL树的概念
普通二叉搜索树#xff1a;二叉搜索树 二叉搜索树虽可以缩短查找的效率#xff0c;但… AVL树 1.AVL树的概念2.平衡因子3.节点的定义4.插入操作5.旋转操作重点5.1左单旋5.2右单旋5.3左右双旋5.4右左双旋 6.一些简单的测试接口7.完整代码 1.AVL树的概念
普通二叉搜索树二叉搜索树 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序普通的二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法(AVL树是以这两位的名字命名的)当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1超过了需要对树中的结点进行调整(旋转)即可降低树的高度从而减少平均搜索长度。 AVL树也是二叉搜索树但有以下特点
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)搜索时间复杂度O( l o g 2 n log_2 n log2n)。 2.平衡因子
AVL树的实现有很多种本文引入平衡因子来维持高度稳定。 本文平衡因子的定义右子树高度 - 左子树的高度。 依据每个节点的平衡因子我们可以判断树的情况
平衡因子在(-1, 0, 1)当前节点所在子树是稳定的。平衡因子为2或-2当前节点所在子树是不稳定的。
插入节点后平衡因子的更新
插入节点在右子树平衡因子加一。插入节点在左子树平衡因子减一。
插入节点后平衡因子的不同情况重点
当前节点所在子树平衡因子为0子树高度不变不需要更新原来一边高一边低新插入在低一方变成完全平衡。当前节点所在子树平衡因子为1或-1子树高度变化需要向上更新。原来完全平衡现在一边高子树整体高度加1会影响到祖先的平衡故需要向上更新看祖先所在子树是否平衡当前节点所在子树平衡因子为2或-2子树高度变化且不平衡无需向上更新对当前子树进行旋转操作。当前子树已不平衡向上更新没有意义旋转操作是AVL树的核心可以降低当前子树的高度且不影响上面的树结构 3.节点的定义
节点除了需要增加一个平衡因子还需要增加一个父亲指针方便我们进行平衡因子的向上更新和旋转操作。
templateclass K, class V
struct ALVTreeNode
{ALVTreeNodeK, V* _left;ALVTreeNodeK, V* _right;ALVTreeNodeK, V* _parent;pairK, V _kv; //存储键值对int _bf; //平衡因子ALVTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0),_kv(kv){}
};4.插入操作
PS因为多加了一个父亲指针所以插入时要注意更新父亲指针平衡因子更新按前面的分析来还是比较简单的旋转操作后面单独讲。
bool Insert(const pairK, V kv)
{if (_root nullptr) //一开始为空树直接插入即可{_root new Node(kv);return true;}//找插入位置加插入Node* cur _root; //记录插入位置Node* parent nullptr; //待插入位置的父亲while (cur){if (kv.first cur-_kv.first) //待插入节点在右子树{parent cur;cur cur-_right;}else if (kv.first cur-_kv.first) //待插入节点在左子树{parent cur;cur cur-_left;}else //待插入节点已存在{return false;}}cur new Node(kv);if (kv.first parent-_kv.first) //插入在父亲的右边{parent-_right cur;}else //插入在父亲的左边{parent-_left cur;}cur-_parent parent; //注意更新父亲指针//调整平衡因子while (parent) //是有可能调整到根部的{if (cur parent-_right) //如果新插入的在右子树{parent-_bf;}else if (cur parent-_left) //如果新插入的在左子树{parent-_bf--;}if (parent-_bf 0) //插入后高度不变{break;}else if (parent-_bf 1 || parent-_bf -1) //插入后高度变化但当前子树依然平衡需要向上更新{parent parent-_parent;cur cur-_parent;}else if (parent-_bf 2 || parent-_bf -2) //插入后高度变化并且当前子树已经不平衡,旋转{//旋转操作先省略break;}else //存在大于2小于-2的情况树原来就不平衡应该报错{assert(false);}}return true;
}5.旋转操作重点
5.1左单旋
主体思想 平衡因子的调整 代码加细节处理 void RotateL(Node* parent) //左单旋,rotate-旋转
{Node* SubR parent-_right;Node* SubRL SubR-_left; //这个有可能为空Node* ppnode parent-_parent; //原来父亲的父亲parent-_right SubRL;if(SubRL) SubRL-_parent parent;SubR-_left parent;parent-_parent SubR;if (ppnode nullptr) //旋转的是整颗树{_root SubR;SubR-_parent nullptr;}else //旋转的是部分{if (ppnode-_left parent) //是左子树{ppnode-_left SubR;}else //是右子树{ppnode-_right SubR;}SubR-_parent ppnode;}//最后更新平衡因子parent-_bf SubR-_bf 0;
}5.2右单旋
PS右单旋和左单旋类似细节处理也差不多这里只讲主体思路。 主体思路
平衡因子的调整
代码
void RotateR(Node* parent) //右单旋细节处理和左单旋差不多
{Node* SubL parent-_left;Node* SubLR SubL-_right; //这个有可能为空Node* ppnode parent-_parent;parent-_left SubLR;if(SubLR) SubLR-_parent parent;SubL-_right parent;parent-_parent SubL;if (ppnode nullptr) //旋转的是整颗树{_root SubL;SubL-_parent nullptr;}else //旋转部分{if (ppnode-_left parent) //是左子树{ppnode-_left SubL;}else //右子树{ppnode-_right SubL;}SubL-_parent ppnode;}//最后更新平衡因子parent-_bf SubL-_bf 0;
}5.3左右双旋
PS双旋其实就是两次单旋(复用即可)有前面的基础很好理解重点在于旋转后平衡因子的更新。
旋转思路
平衡因子的调整 想知道平衡因子调整是那种情况我们需要在旋转前记录SubRL的平衡因子bf
bf为0是第一种情况。bf为1是第二种情况。bf为-1是第三种情况。 代码
void RotateLR(Node* parent) //左右双旋
{Node* SubL parent-_left;Node* SubLR SubL-_right;int bf SubLR-_bf;RotateL(SubL);RotateR(parent);if (bf 1) //插入的是右边{SubLR-_bf 0;SubL-_bf -1;parent-_bf 0;}else if (bf -1) //插入的是左边{SubLR-_bf 0;SubL-_bf 0;parent-_bf 1;}else if (bf 0) //刚好原来parent的左边就两个节点{SubLR-_bf SubL-_bf parent-_bf 0;}else //原来就不是平衡树出现问题{assert(false);}
}5.4右左双旋
PS右左双旋和左右双旋思路是差不多的重点还是在旋转后平衡因子的更新。
旋转思路
平衡因子的调整 和前面一样旋转前确认SubRL的平衡因子bf即可。
代码
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 0;SubR-_bf 0;parent-_bf -1;}else if (bf -1) //插入的是左边{SubRL-_bf 0;parent-_bf 0;SubR-_bf 1;}else if (bf 0) //原来parent的右边就两个节点{SubRL-_bf SubR-_bf parent-_bf 0;}else //原来就有问题{assert(false);}
}6.一些简单的测试接口
int Height()
{return _Height(_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;
}bool IsBalance()
{return IsBalance(_root);
}//看当前树是不是平衡树
//1看每个子树是否满足左右子树高度差不超过一
//2看平衡因子和所求的左右子树高度差是否一致
bool IsBalance(Node* root)
{if (root nullptr)return true;int leftHight _Height(root-_left);int rightHight _Height(root-_right);if (rightHight - leftHight ! root-_bf){cout 平衡因子异常: root-_kv.first - root-_bf endl;return false;}return abs(rightHight - leftHight) 2 IsBalance(root-_left) IsBalance(root-_right);
}7.完整代码
#pragma once
#include iostream
#include assert.h
#include utility
using namespace std;templateclass K, class V
struct ALVTreeNode
{ALVTreeNodeK, V* _left;ALVTreeNodeK, V* _right;ALVTreeNodeK, V* _parent;pairK, V _kv; //存储键值对int _bf;ALVTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0),_kv(kv){}
};templateclass K, class V
class AVLTree
{
public:typedef ALVTreeNodeK, V Node;bool Insert(const pairK, V kv){if (_root nullptr) //一开始为空树直接插入即可{_root new Node(kv);return true;}Node* cur _root; //记录插入位置Node* parent nullptr; //待插入位置的父亲while (cur){if (kv.first cur-_kv.first) //待插入节点在右子树{parent cur;cur cur-_right;}else if (kv.first cur-_kv.first) //待插入节点在左子树{parent cur;cur cur-_left;}else //待插入节点已存在{return false;}}cur new Node(kv);if (kv.first parent-_kv.first) //插入在父亲的右边{parent-_right cur;}else //插入在父亲的左边{parent-_left cur;}cur-_parent parent;//调整平衡因子while (parent) //是有可能调整到根部的{if (cur parent-_right) //如果新插入的是右子树{parent-_bf;}else if (cur parent-_left) //如果新插入的是左子树{parent-_bf--;}if (parent-_bf 0) //插入后高度不变{break;}else if (parent-_bf 1 || parent-_bf -1) //插入后高度变化但当前子树依然平衡需要向上更新{parent parent-_parent;cur cur-_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;}////int Height(){return _Height(_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;}bool IsBalance(){return IsBalance(_root);}//看当前树是不是平衡树//1看每个子树是否满足左右子树高度差不超过一//2看平衡因子和所求的左右子树高度差是否一致bool IsBalance(Node* root){if (root nullptr)return true;int leftHight _Height(root-_left);int rightHight _Height(root-_right);if (rightHight - leftHight ! root-_bf){cout 平衡因子异常: root-_kv.first - root-_bf endl;return false;}return abs(rightHight - leftHight) 2 IsBalance(root-_left) IsBalance(root-_right);}private:void RotateL(Node* parent) //左单旋,rotate-旋转{Node* SubR parent-_right;Node* SubRL SubR-_left; //这个有可能为空Node* ppnode parent-_parent; //原来父亲的父亲parent-_right SubRL;if(SubRL) SubRL-_parent parent;SubR-_left parent;parent-_parent SubR;if (ppnode nullptr) //旋转的是整颗树{_root SubR;SubR-_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; //这个有可能为空Node* ppnode parent-_parent;parent-_left SubLR;if(SubLR) SubLR-_parent parent;SubL-_right parent;parent-_parent SubL;if (ppnode nullptr) //旋转的是整颗树{_root SubL;SubL-_parent nullptr;}else //旋转部分{if (ppnode-_left parent) //是左子树{ppnode-_left SubL;}else //右子树{ppnode-_right SubL;}SubL-_parent ppnode;}//最后更新平衡因子parent-_bf SubL-_bf 0;}void RotateLR(Node* parent) //左右双旋{Node* SubL parent-_left;Node* SubLR SubL-_right;int bf SubLR-_bf;RotateL(SubL);RotateR(parent);if (bf 1) //插入的是右边{SubLR-_bf 0;SubL-_bf -1;parent-_bf 0;}else if (bf -1) //插入的是左边{SubLR-_bf 0;SubL-_bf 0;parent-_bf 1;}else if (bf 0) //刚好原来parent的左边就两个节点{SubLR-_bf SubL-_bf parent-_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 0;SubR-_bf 0;parent-_bf -1;}else if (bf -1) //插入的是左边{SubRL-_bf 0;parent-_bf 0;SubR-_bf 1;}else if (bf 0) //原来parent的右边就两个节点{SubRL-_bf SubR-_bf parent-_bf 0;}else //原来就有问题{assert(false);}}Node* _root nullptr;
};
