微信云网站用什么做,有广告位怎么找广告商,怎么建设投票网站,在线logo设计网站本文已收录至《数据结构(C/C语言)》专栏#xff01; 作者#xff1a;ARMCSKGT 目录 前言正文AVL树的性质AVL树的定义AVL树的插入函数左单旋右单旋右左双旋左右双旋 检验AVL树的合法性关于AVL树 最后 前言
前面我们学习了二叉树#xff0c;普通的二叉树没有任何特殊性质语言)》专栏 作者ARMCSKGT 目录 前言正文AVL树的性质AVL树的定义AVL树的插入函数左单旋右单旋右左双旋左右双旋 检验AVL树的合法性关于AVL树 最后 前言
前面我们学习了二叉树普通的二叉树没有任何特殊性质所以后面我们又学习了二叉搜索树这种有序的结构一定程度上优化了二叉树的性能但是普通的二叉搜索树在特殊情况下例如插入序列从大到小有序时二叉搜索树会退化成类似于链表的单支数此时性能变为O(n)为了解决这个问题科学家在二叉搜索树的基础上再次进行升级而有了我们现在常见的 AVL树 和 红黑树 本节我们将介绍AVL树的基础性质。 正文
在介绍AVL树之前如果你没有了解过 二叉搜索树 或 二叉树请移步先了解前置知识 本节介绍AVL树默认中序遍历为升序序列 AVL树的性质 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。 因此两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 简而言之AVL树通过一个 平衡因子bf(右子树深度减去左子树深度) 来记录根节点左右子树深度的差一般情况下平衡因子只会有五种情况 左子树比右子树深度高两层此时平衡因子为 -2 此时需要对树进行旋转调整左子树比右子树深度高一层此时平衡因子为 -1左子树与右子树深度相等此时平衡因子为 0左子树比右子树深度低一层此时平衡因子为 1左子树比右子树深度低两层此时平衡因子为 2 此时需要对树进行旋转调整 综上如果二叉搜索树具备以下性质则为AVL树 左右子树的高度之差平衡因子的绝对值不超过 1它的左右子树都是 AVL 树 AVL树结构节点上的数字就是平衡因子 这颗树没有出现不平衡的情况每个节点的平衡因子的绝对值不超过2。 这样看来AVL树是一颗高度平衡的二叉搜索树如果AVL树有N个节点则AVL树的高度为 log n \log_n logn此时找到任意节点的时间复杂度都是O( log 2 N \log_2N log2N)。 我们学习AVL树主要是研究其插入节点后如何保持平衡的思想 AVL树的定义 AVL树在二叉树的基础上增加了一个指针指向了父节点以及一个平衡因子所以AVL树是三叉链结构 节点定义代码 #include iostreamtemplateclass K,class V
struct TreeNode
{TreeNodeK, V* _left; // 左子树TreeNodeK, V* _right; // 右子树TreeNodeK, V* _parent; // 父节点std::pairK, V _val; // 节点键值对(节点值)int _bf; // 平衡因子TreeNode():_left (nullptr),_right (nullptr),_parent(nullptr),_val(pairK,V()),_bf(0){}TreeNode(const pairK,V val):_left (nullptr), _right (nullptr), _parent(nullptr), _val(val), _bf(0){}TreeNode(const K key,const V val):_left(nullptr), _right(nullptr), _parent(nullptr), _val({key,val}), _bf(0){}
};AVL树的定义比较简单只需要一个根节点_root记录即可。 但是为了我们可以控制对比的函数以便随我们指定的方式去插入就像sort函数一样可以通过仿函数控制升序和降序排序所以我们还需要一个模板参数去作为比较函数 AVL树定义 //仿函数控制比较方式
templateclass T //升序
struct less { bool operator()(const T left, const T right) { return left right; } };
templateclass T //降序
struct greater { bool operator()(const T left, const T right) { return left right; } };//AVL树定义 默认升序(按中序输出序列)
templateclass K, class V, class Compare lessK
class AVLTree
{typedef std::pairK, V val_type; //值类型typedef TreeNodeK, V Node; //节点类型
public:AVLTree() :_root(nullptr), _size(0) {}private:Node* _root; //根节点size_t _size; //节点数量Compare _com; //比较函数
};AVL树的插入函数 在二叉搜索树的插入函数基础上AVL树的插入操作还需要对父节点的平衡因子进行调节并在失衡的根节点处进行旋转调整。 AVL树插入流程 如果是第一次插入节点直接赋值给 _root 作为根节点_size1。将插入值的key与当前节点值传入 _com函数 中对比当函数返回true时向左子树走返回false时向右子树走如果走到空则跳出准备插入如果相等则返回当前节点值。根据节点值与插入值key在_com函数中的对比结果决定插入到父节点的左子树还是右子树。调整父节点的平衡因子如果出现失衡平衡因子绝对值为2则进行旋转并依次向上继续调整祖父节点直到当前父节点平衡因子为0或节点为树的根节点为止。_size1并返回插入结果。 关于AVL树的返回值AVL树返回值为 pairval_type,bool当插入成功在返回节点值的同时并返回true当插入失败(遇到相等值节点时)返回false。 插入函数代码 //插入函数
pairval_type, bool insert(const val_type data)
{//首次插入特殊处理if (nullptr _root){Node* newnode new Node(data);_root newnode;_size;return { data,true };}//寻找合适的插入位置Node* newnode new Node(data);Node* parent _root;Node* cur _root;while (cur){if (_com(data.first, cur-_val.first)) // {parent cur;cur cur-_left;}else if (_com(cur-_val.first, data.first)) // {parent cur;cur cur-_right;}//找到相同值节点 返回false和节点值else return { data,false}; // }//将新节点插入所寻找的父节点下if (_com(data.first, parent-_val.first)) parent-_left newnode;else parent-_right newnode;newnode-_parent parent;cur newnode;while (parent){//调整父节点平衡因子if (parent-_left cur) --(parent-_bf);else if (parent-_right cur) (parent-_bf);//调整和旋转if (parent-_bf 1 || parent-_bf -1){parent parent-_parent;cur cur-_parent;}else if (parent-_bf 0) break;else //开始调整和旋转{if (parent-_bf -2 cur-_bf -1) RotateR(parent); //右单旋else if (parent-_bf 2 cur-_bf 1) RotateL(parent); //左单旋else if (parent-_bf -2 cur-_bf 1) RotateLR(parent); //左右旋else if (parent-_bf 2 cur-_bf -1) RotateRL(parent); //右左旋else { assert(false); }}}_size;return { data,true };
}关于节点调整流程 关于旋转调整节点我们接下来进行详细探究 关于需要调整的情况一共可以分为四大类 是否旋转取决于parent和cur节点的平衡因子 parent(父节点)平衡因子cur(子节点)平衡因子操作-2-1右单旋21左单旋-21左右双旋2-1右左双旋 左单旋 当根节点的右子树平衡因子为1的情况下仍然向右子树中插入比右子树节点值大的节点此时就会导致根节点平衡因子为2右子树平衡因子为1此时就需要左单旋。 当我们向20节点的右子树中插入35时35是该树中的最大节点便会插入在最右节点此时30节点的平衡因子变为125节点则变为2需要对其进行左单旋。 左单旋的函数代码 //左单旋
void RotateL(Node* parent)
{//parent右子节点Node* childR parent-_right;//parent右子节点的左子节点Node* childRL childR-_left;//parent右子节点的右子节点Node* childRR childR-_right;//parent节点的父节点Node* pparent parent-_parent;//parent节点的右指向childR的左子树parent-_right childRL;//如果childRL节点存在 则链接与parent节点的关系 否则parent-_right指向空if (childRL) childRL-_parent parent;//将childR的左指向parent 构建链接关系childR-_left parent;parent-_parent childR;//与pparent构建链接关系 如果pparent为_root根节点 则设置_rootif (pparent nullptr){_root childR;_root-_parent nullptr;}else //否则查看原parent节点是pparent的左还是右子树 插入原parent位置{if (pparent-_left parent) pparent-_left childR;else pparent-_right childR;childR-_parent pparent;}//更新受影响节点的平衡因子parent-_bf childR-_bf 0;
}旋转过程简而言之就是更改节点的链接关系使其深度降低 对于上面图中的树我们根据左单旋进行调整 左单旋过程梳理 parent节点与childRL节点构建链接关系childR节点的左子树置为parent并相互构建链接关系判断pparent是否为空不为空则将childR与pparent构建链接关系将parent节点与childR节点的平衡因子置为0 注意这里在构建链接关系时一定要注意构建与父节点的关系容易忘记childRL节点可能为空如果为空则不需要与其新父节点(parent)构建链接关系需要if判断 右单旋 当根节点的左子树平衡因子为-1的情况下仍然向左子树中插入比左子树节点值小的节点此时就会导致根节点平衡因子为-2左子树平衡因子为-1此时就需要右单旋。 右单旋与左单旋相似只不过指针的调整方式不同。 当节点3插入后节点10的平衡因子(左右子树高度差为2)为-2此时插入的节点位于左子树的左侧此时需要右旋转。 右单旋的函数代码 //右单旋
void RotateR(Node* parent)
{Node* childL parent-_left;Node* childLL childL-_left;Node* childLR childL-_right;Node* pparent parent-_parent;parent-_left childLR;if (childLR) childLR-_parent parent;childL-_right parent;parent-_parent childL;if (pparent nullptr){_root childL;_root-_parent nullptr;}else{if (pparent-_left parent) pparent-_left childL;else pparent-_right childL;childL-_parent pparent;}parent-_bf childL-_bf 0;
}对于上面图中的树我们根据右单旋进行调整 右单旋过程梳理 parent节点与childLR节点构建链接关系childL节点的右子树置为parent并相互构建链接关系判断pparent是否为空不为空则将childL与pparent构建链接关系将parent节点与childL节点的平衡因子置为0 注意这里在构建链接关系时一定要注意构建与父节点的关系容易忘记childLR节点可能为空如果为空则不需要与其新父节点(parent)构建链接关系需要if判断 右左双旋 当我们将值插入(高度差为1的树时)右子树右侧时会引发左单旋当插入左子树左侧时会引发右单旋。 相反如果将值插入右子树左侧或左子树右侧则会引发双旋。 如果插入的是右子树左侧此时parent平衡因子为那么单旋就不能解决问题了此时需要右左双旋详细解释就是先 进行右单旋 再进行左单旋这样才能降低高度。 关于以下情况就是需要进行右左双旋 右左双旋代码 //右左双旋
void RotateRL(Node* parent)
{Node* childR parent-_right;Node* childRL childR-_left;int bf childRL-_bf;RotateR(childR);RotateL(parent);/*AB CDE*/if (bf -1){parent-_bf 0;childR-_bf 1;childRL-_bf 0;}/*AB CDE*/else if (bf 1){parent-_bf -1;childR-_bf 0;childRL-_bf 0;}/*ABC*/else if (bf 0){parent-_bf 0;childR-_bf 0;childRL-_bf 0;}//如果出现其他情况则表示代码有问题需要检查else assert(false);
}关于右左双旋可以结合下图理解(三列情况对应三种不同的平衡因子调整) 关于右左双旋的过程 先确定parent和childR和childRL节点对childR进行右单旋(将childRL变成childR的父节点)对parent进行左单旋(再将childRL变成childR的父节点)调整parent,childR和childRL节点的平衡因子(根据childRL节点平衡因子调整) 关于节点平衡因子的调整从上图看出来需要根据childRL节点来进行判断 当childRL平衡因子为 0 parent的平衡因子调整为0childR的平衡因子调整为0childRL平衡因子调整为0。当childRL平衡因子为 -1 parent的平衡因子调整为0childR的平衡因子调整为1childRL平衡因子调整为0。当childRL平衡因子为 1 parent的平衡因子调整为-1childR的平衡因子调整为0childRL平衡因子调整为0。 注意右左双旋中对childR进行右单旋转再对parent进行左单旋这个顺序不能颠倒且平衡因子的调整必须根据childRL平衡因子进行调整。 左右双旋 当节点插入到左子树的右侧时此时parent平衡因子为-2且childR平衡因子为1此时需要左右双旋即需要 先进行左单旋再进行右单旋 才能降低高度。 关于以下插入情况此时的树需要进行左右双旋 左右双旋代码 //左右双旋
void RotateLR(Node* parent)
{Node* childL parent-_left;Node* childLR childL-_right;int bf childLR-_bf;RotateL(childL);RotateR(parent);/*AB CD EF*/if (bf -1){childL-_bf 0;childLR-_bf 0;parent-_bf 1;}/*AB CD EF*/else if (bf 1){childL-_bf -1;childLR-_bf 0;parent-_bf 0;}/** A* B* C*/else if (bf 0){childL-_bf 0;childLR-_bf 0;parent-_bf 0;}//如果出现其他情况则表示代码有问题需要检查else assert(false);
}关于右左双旋可以结合下图理解(三列情况对应三种不同的平衡因子调整) 关于左右双旋的过程 先确定parent和childL和childLR节点对childL进行左单旋(将childLR变成childL的父节点)对parent进行右单旋(再将childLR变成parent的父节点)调整parent,childL和childLR节点的平衡因子(根据childLR节点平衡因子调整) 关于节点平衡因子的调整从上图看出来需要根据childRL节点来进行判断 当childLR平衡因子为 0 parent的平衡因子调整为0childL的平衡因子调整为0childLR平衡因子调整为0。当childLR平衡因子为 -1 parent的平衡因子调整为1childL的平衡因子调整为0childLR平衡因子调整为0。当childLR平衡因子为 1 parent的平衡因子调整为0childL的平衡因子调整为-1childLR平衡因子调整为0。 注意左右双旋中对childL进行右单旋转再对parent进行左单旋这个顺序不能颠倒且平衡因子的调整必须根据childLR平衡因子进行调整。 AVL树主要值得学习的地方就在插入学习其控制树的高度差的思想和旋转思想。 检验AVL树的合法性 检验AVL树是否合格是否没有bug还需要从其定义入手。 空树是满足AVL树性质且满足以下条件则是AVL树 右子树减去左子树深度的绝对值不超过1右子树减去左子树深度等于根节点平衡因子每棵子树都满足该条件 以上条件满足任意一个就是AVL树。 我们代码实现采用递归方式在类中需要写一个递归函数再进行封装 代码实现 //检查AVL树合法性-调用函数
bool isAVL() { return _isAVL(_root); }//获取AVL树高度-调用函数
int getHigh() { return _getHigh(_root); }//检查AVL树合法性-执行函数
bool _isAVL(Node* root)
{if (root nullptr) return true;//获取左右子树高度int left _getHigh(root-_left);int right _getHigh(root-_right);//如果右子树减左子树高度差的绝对值小于1 且差值与根的平衡因子相等 就继续检查子树if (abs(right - left) 1 (right - left) root-_bf) return true _isAVL(root-_left) _isAVL(root-_right);return false;
}//获取树的深度-执行函数
int _getHigh(Node* root)
{if (root nullptr) return 0;int left _getHigh(root-_left);int right _getHigh(root-_right);return left right ? left 1 : right 1;
} 测试代码 int main()
{const int N 10000;AVLTree::AVLTreeint,int t;for (int i 0; i N; i) t.insert({i,i});if (t.isAVL()) cout 合法 endl;else cout 不合法 endl;cout 树高度 t.getHigh() endl;return 0;
}我们插入10001个节点此时树合法且高度为14 2 13 8192 2 14 16384 2^{13}8192 2^{14}16384 213819221416384 通过对高度的平方运算结果符合要求 关于AVL树 AVL树是一棵对身材要求及其严格的树时时刻刻要求自己左右接近对称(左右高度差不超过1)。 AVL树的优缺点 优点 因为其严格的要求当树中稍微出现退化趋势就会立刻被调整所以对于AVL树的查询时间非常快约为 l o g 2 N log_2N log2N。缺点 因为其严格的条件导致AVL树在碰到有序序列时可能会频繁旋转调整在删除情况下更是有可能一直调整到根节点因为频繁旋转非常浪费性能所以导致插入效率下降。 AVL树的使用场景 AVL树严格的平衡条件导致其查询效率极高在不频繁增删的情况下也就是静态树(只查只读) 的情况下使用AVL树会的查询效率是极好的但是在很多场景中增删查改是并存的此时我们不得不考虑摒弃一些查询时间去弥补插入删除的效率也就是需要一棵与AVL树差不多但是没有AVL树要求这么严格的二叉搜索树这棵树就是红黑树红黑树可以做的比AVL树调整次数少的情况下性能差距不超过2倍下一节我们将介绍红黑树 最后
AVL树的介绍到这里就差不多了我们首先说明了二叉搜索树的缺点引入AVL树对其进行强化AVL树的复杂之处在于其旋转调整所以我们通过AVL树的插入介绍旋转调整至于删除操作相对于插入函数更加复杂有兴趣的小伙伴可以了解对于AVL树的基本性质就是这些了
本次 AVL树 就先介绍到这里啦希望能够尽可能帮助到大家。
如果文章中有瑕疵还请各位大佬细心点评和留言我将立即修补错误谢谢
本节涉及代码AVL树博客代码 其他文章阅读推荐 数据结构初级二叉搜索树 数据结构初级二叉树 C 继承 C 多态 C STL容器适配器 欢迎读者多多浏览多多支持!
