文章目录一、二叉搜索树1.1概念1.2操作1.3代码实现二、二叉搜索树的应用K模型和KV模型三、二叉搜索树的性能分析四、AVL树4.1AVL树的概念4.2AVL树的实现原理4.3旋转4.4AVL树最终代码一、二叉搜索树1.1概念二叉搜索树（BinarySearchTree，BST）是一种特殊的二叉树，它可以是空树，也可以是满足以下性质的一颗二叉树：若左子树不为空，左子树中所有节点的键值都小于根节点的值。若右子树不为空，右子树中所有节点的键值都大于根节点的值。左右子树也分别为二叉搜索树。因此，二叉搜索树的中序遍历结果是一个有序序列。这个特性使得二叉搜索树在搜索、插入和删除操作时具有高效性能。📝二
文章目录AVL树节点的定义AVL树的定义AVL树的插入插入后更新平衡因子AVL树的右单旋AVL树的左单旋先左单旋再右单旋先右单旋再左单旋检查是否满足AVL树总代码AVL树AVL树也叫平衡二叉搜索树，通过旋转解决了搜索二叉树的不确定性，让整颗树趋近于一颗满二叉树。1.左右都是一颗AVL树2.平衡因子的绝对值不会超过1上图的蓝字表示平衡因子，平衡因子=右子树的高度-左子树的高度AVL树节点的定义templateclassK,classV>structAVLTreeNode{ ALVTreeNodeK,V>*_left; AVLTreeNodeK,V>*_right; AVLTreeNodeK,V>
AVL树文章目录AVL树一、底层结构二、AVL树的概念三、AVL树节点的定义四、AVL树的基本框架五、AVL树的插入六、AVL树的旋转1.左单旋2.右单旋3.左右双旋4.右左双旋七、AVL树的验证八、AVL树的修改九、AVL树的查找十、AVL树的删除（了解）十一、AVL树的性能一、底层结构前面对map、multimap、set、multiset进行了简单的介绍，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行
AVL树文章目录AVL树一、底层结构二、AVL树的概念三、AVL树节点的定义四、AVL树的基本框架五、AVL树的插入六、AVL树的旋转1.左单旋2.右单旋3.左右双旋4.右左双旋七、AVL树的验证八、AVL树的修改九、AVL树的查找十、AVL树的删除（了解）十一、AVL树的性能一、底层结构前面对map、multimap、set、multiset进行了简单的介绍，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行
文章目录AVL树AVL树的实现AVL树的节点AVL树的平衡因子AVL树的插入AVL树的旋转左单旋右单旋左右正旋右左正旋中序遍历打印节点判断子树是否平衡整体代码验证代码红黑树概念性质（规则）红黑树的实现结点定义插入parent在grandparent的左情况一：uncle结点存在且uncle结点也是红色情况二：grandparent,parent,cur呈现直线状态当uncle结点不存在当uncle存在且为黑时情况三：grandparent,parent,cur呈现折线状态uncle不存在uncle存在且为黑parent在grandparent的右整体插入函数左旋右旋（和AVL树的一致）打印，验
文章目录AVL树AVL树的实现AVL树的节点AVL树的平衡因子AVL树的插入AVL树的旋转左单旋右单旋左右正旋右左正旋中序遍历打印节点判断子树是否平衡整体代码验证代码红黑树概念性质（规则）红黑树的实现结点定义插入parent在grandparent的左情况一：uncle结点存在且uncle结点也是红色情况二：grandparent,parent,cur呈现直线状态当uncle结点不存在当uncle存在且为黑时情况三：grandparent,parent,cur呈现折线状态uncle不存在uncle存在且为黑parent在grandparent的右整体插入函数左旋右旋（和AVL树的一致）打印，验
✨个人主页：北海🎉所属专栏：C++修行之路🎃操作环境：VisualStudio2019版本16.11.17文章目录🌇前言🏙️正文1、认识AVL树1.1、AVL树的定义2、AVL树的插入操作2.1、抽象图2.2、插入流程2.3、左单旋2.4、右单旋2.5、右左双旋2.6、左右双旋2.7、注意事项及调试技巧3、AVL树的合法性检验3.1、检验依据3.2、检验方法3.3、AVL树的性能🌆总结🌇前言普通的二叉搜索树可能会退化为单支树（歪脖子树），导致搜索性能严重下降，为了解决这个问题，诞生了平衡二叉搜索树，主要是通过某些规则判断后，降低二叉树的高度，从而避免退化，本文介绍的AVL树就属于其中一种比较经
文章目录前言一、AVL树的概念二、AVL树的操作1.AVL树节点的定义2.AVL树的插入3.AVL树的旋转(1)左单旋(2)右单旋(3)先左单旋再右单旋(4)先右单旋再左单旋(5)旋转总结4.AVL树的删除三、AVL树的验证四、AVL树的性能五、AVL树的代码实现1.AVLTree.h2.Test.cpp前言之前我们对map/multimap/set/multiset进行了简单的介绍，我们发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等
文章目录1.AVL树的概念2.AVL树的结点3.AVL树的插入🍑更新平衡因子🍑插入函数的实现4.AVL树的旋转🍑左单旋🍑右单旋🍑左右双旋🍑右左双旋🍑总结6.AVL树的删除🍑算法思想🍑示例一🍑示例二🍑代码实现7.AVL树的遍历8.AVL树的查找9.AVL树的高度10.AVL树的验证🍑数据测试11.AVL树优缺点分析1.AVL树的概念二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中
🐱作者：一只大喵咪1201🐱专栏：《数据结构与算法》🔥格言：你只管努力，剩下的交给时间！AVL树🌲AVL树🌴AVL树的插入🌴AVL树的旋转左单旋右单旋左右双旋右左双旋🌴AVL树的验证🌴AVL数的删除(了解)🌴AVL数的性能🌴总结我们知道，二叉搜索树的搜索效率非常高，平均时间复杂度是O(log2N)，但是当数据原本就有序时，插入二叉树中就会形成单支结构，此时搜索的时间复杂度就是O(N)。为了避免二叉搜索树的这个缺陷，在它的基础上提出了AVL树(高度平衡二叉搜索树)和红黑树。🌲AVL树AVL树：当向二叉搜索树中插入新节点后，要保证每个节点的左右子树高度差的绝对值不超过1。根据高度差不超过1的规制，
