如何做一间公司的网站,网络优化工程师有前途吗,音乐外链生成网站怎么做,中文网站建设合同目录
AVL树介绍
AVL树平衡因子更新分析
AVL树插入时旋转与平衡因子更新
左单旋
右单旋
左右单旋
右左单旋
AVL旋转可行性
AVL树节点删除#xff08;待补充#xff09;
AVL树分析 AVL树介绍
二叉搜索树在某些极端情况下可能会退化#xff0c;为了解决这个问题待补充
AVL树分析 AVL树介绍
二叉搜索树在某些极端情况下可能会退化为了解决这个问题引入了AVL树平衡搜索二叉树中的一种控制二叉搜索树的不平衡情况插入一个新节点后控制每一个节点的左右子树高度差的绝对值不超过1 之所以控制绝对值不超过1而不是不超过0是因为只有在满二叉树的情况下才可以满足每一个节点的左右子树高度差的绝对值不超过0为了满足普遍性选择绝对值不超过1 一棵AVL树具有以下的特点 每一个节点的左右子树都是AVL树 左右子树高度差的绝对值通过平衡因子判断不超过1 绝对值不超过1包括-1、1和0 以右子树高度减左子树高度为例下面是含有每一个节点的高度的AVL树示意图
AVL树平衡因子更新分析
在AVL树中平衡因子更新只有两种情况1. 增加 2. 减少但是需要考虑什么时候增加什么时候减少 当插入节点在左子树时平衡因子减少例如插入在8节点的左子树 当插入节点在右子树时平衡因子增加例如插入在8的右子树
接着考虑插入新节点后哪些节点的平衡因子需要改变。 如果插入节点在8的左子树那么更新时只会更新8节点的平衡因子因为8初始时是1插入在左子树平衡因子减小而对于节点7来说并没有影响到其平衡因子因为7的右子树总体的高度没有发生变化而对于根节点的左子树以及7节点的左子树来说没有一点影响 如果按照下图的插入方式插入节点为红色节点此时会更新其所有祖先节点 如果插入节点在8的右子树那么更新时8节点的平衡因子变为了2因为8初始时是1插入在右子树平衡因子增加因为AVL树规定每一个节点的左右子树高度差的绝对值不能超过1所以此时8节点需要进行额外处理使其恢复AVL树结构
综上所述存在三种情况 当插入节点的父亲节点更新为0时插入节点前父亲节点平衡因子为1或者-1一边高一边矮为1时右子树高插入位置为左子树为-1时左子树高插入位置为右子树插入在矮的一边此时只需要更新父亲节点的平衡因子因为总高度并没有发生变化。例如8节点的左子树插入节点树的总高度还是4 当插入节点的父亲节点更新为1或者-1时插入节点前父亲节点平衡因子为0左右子树高度相等当更新为1时插入位置为右子树右子树变高起始为-1时插入位置为左子树左子树变高其中一方变高此时需要更新所有祖先节点的平衡因子因为插入的节点导致了树的总高度发生变化例如例2插入红色节点树的总高度由4变为5 当插入节点的父亲节点更新为2或者-2时插入节点前父亲节点平衡因子为1或者-1左右子树存在一方高一方矮当更新为2时原父亲节点平衡因子为1并且插入位置在平衡因子为1的父亲节点的右子树例如在节点8右子树插入新节点当更新为-2时原父亲节点平衡因子为-1插入位置平衡因子为-1的父亲节点的右子树高的一方继续变高矮的一方没有改变此时需要进行旋转处理将平衡因子为2或者-2的节点对应的树进行调整使其恢复AVL树结构
AVL树插入时旋转与平衡因子更新
左单旋
当插入的节点在平衡因子为1的父亲节点的右子树的右子树上时此时父亲节点的平衡因子更新为2其右孩子节点的平衡因子分别为1和0时需要进行左单旋例如下面的一种具体情况
为了便于分析将插入位置进行抽象化a、b和c分别是高度h0的AVL子树如下图所示
此时因为父亲节点10的平衡因子变为了2需要进行左旋左旋需要进行的步骤如下 平衡因子计算 h1(新增节点所在层数)-11为20节点的平衡因子 h11(20节点所在层数)-h2为10节点的平衡因子 将20的左孩子给10节点作为其右孩子 将10降下作为20的左孩子 20节点作为本棵子树的根节点 更新10和20节点的平衡因子为0
结合变量parent、subR和subRL
代码实现 // 左单旋void rotateLeft(node* parent){// 定义节点node* subR parent-_right;node* subRL subR-_left;// 1. subRL变为parent的右孩子parent-_right subRL;// 更新subRL的_parent为parent需要注意当h0时subRL节点不存在所以需要进行判断subRL是否为空if (subRL){subRL-_parent parent;}// 2. parent变为subR的左孩子subR-_left parent;// 3. subR变为本棵子树的根节点// 记录parent的父亲节点node* parentParent parent-_parent;// 更新parent节点的父亲节点为subRparent-_parent subR;// 更新parent节点的父亲节点的孩子节点为subRif (parentParent nullptr){// 父亲节点为空证明是根节点_root subR;subR-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}// 更新subR的父亲节点subR-_parent parentParent;}// 4. 更新平衡因子parent-_bf subR-_bf 0;}
右单旋
当插入的节点在平衡因子为-1的父亲节点的左子树的左子树上时此时父亲节点的平衡因子更新为-2其左孩子节点的平衡因子分别为-1和0时需要进行右单旋例如下面的一种具体情况
为了便于分析将插入位置进行抽象化a、b和c分别是高度h0的AVL子树如下图所示
此时因为父亲节点10的平衡因子变为了-2需要进行右旋右旋需要进行的步骤如下 平衡因子计算 h-(h1(新增节点所在层数))-1为20节点的平衡因子 h-(h11(20节点所在层数))-2为10节点的平衡因子 将20的右孩子作为10的左孩子 将10作为20的右孩子 将20作为本棵子树的根节点 更新10和20的平衡因子为0
结合变量parent、subL和subLR
代码实现 // 右单旋void rotateRight(node* parent){node* subL parent-_left;node* subLR subL-_right;// 1. 将subLR作为parent的左孩子parent-_left subLR;// 更新subLR的parentif (subLR){subLR-_parent parent;}// 2. 将parent作为subL的右孩子subL-_right parent;// 3. 将subL作为本棵子树的根节点// 记录当前parent节点的父亲节点node* parentParent parent-_parent;// 更新parent的_parent为subLparent-_parent subL;if (parentParent nullptr){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}// 更新subL的父亲节点subL-_parent parentParent;}// 4. 更新平衡因子subL-_bf parent-_bf 0;}
左右单旋
当插入的节点在平衡因子为-1的父亲节点的左子树的右子树上时此时父亲节点的平衡因子更新为-2其右孩子节点的平衡因子分别为1和0时需要先进行左单旋再进行右单旋例如下面的一种具体情况
为了便于分析将插入位置进行抽象化 a、b和c分别是高度h0的AVL子树如下图所示
在当前情况下b位置的节点即为新增节点a和c位置此时均没有节点10节点的平衡因子更新为-210节点的左孩子节点的平衡因子更新为1 平衡因子计算 5节点的平衡因子h1(新增节点所在层数)-h1 10节点的平衡因子h-(h11(5节点所在层数))-2 a、b、c和d分别是高度h0的AVL子树如下图所示 h0在上图的情况下代表已经至少存在一个节点即5的右子树开始有一个节点存在所以6位置没有节点时用h-1代替 此时插入节点的位置有两种
(a) 在b位置插入此时6节点的平衡因子变为-15节点的平衡因子变为110节点的平衡因子变为-2 平衡因子的计算 6节点的平衡因子h-1-h(新增节点所在层数)-1 5节点的平衡因子h1(6节点所在层数)-h1 10节点的平衡因子h-(h11)-2 (b) 在d位置插入此时6节点的平衡因子变为-15节点的平衡因子变为110节点的平衡因子变为-2 平衡因子的计算 6节点的平衡因子h1-h(新增节点所在层数)1 5节点的平衡因子h1(6节点所在层数)-h1 10节点的平衡因子h-(h11)-2 尽管左右单旋有两种主要情况但是实际上影响到的平衡因子的更新主要思路还是先左旋再右旋为了更好观察效果以第二种情况中的第一种情况为例分析先左旋再右旋的步骤 左旋将多条路径更新化为一条路径更新 将6节点的左孩子作为5节点的右孩子 将5节点作为6节点的左孩子 将6节点作为本棵树的根节点链接到10节点的左孩子因为开始的父亲节点5是10节点的左孩子 右旋更新单一路径 将6节点的右孩子作为10节点的左孩子 将10节点作为6节点的右孩子 将6节点作为本棵树的根节点 更新平衡因子
当树旋转结束后需要更新对应的平衡因子此时需要考虑到两种主要情况即h0和h0结合变量parent、subL和subLR h0左右双旋结束后如下图所示 h0 插入位置在b左右双旋结束后如下图所示 插入位置在d左右双旋结束后如下图所示 代码实现 // 左右双旋void rotateLR(node* parent){// 记录旋转前的平衡因子node* subL parent-_left;node* subLR subL-_right;int bf subLR-_bf;// 1. 左右双旋// 左旋rotateLeft(parent-_left);// 右旋rotateRight(parent);// 更新平衡因子if (bf 0){subL-_bf parent-_bf 0;}else if (bf -1)// 插入在d位置{subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else if (bf 1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else{assert(false);}}
右左单旋
当插入的节点在平衡因子为1的父亲节点的右子树的左子树上时此时父亲节点的平衡因子更新为2其右孩子节点的平衡因子分别为-1和0时需要先进行右单旋再进行左单旋例如下面的一种具体情况
为了便于分析将插入位置进行抽象化 a、b和c分别是高度h0的AVL子树如下图所示
在当前情况下c位置的节点即为新增节点a和b位置此时均没有节点10节点的平衡因子更新为-210节点的左孩子节点的平衡因子更新为1 a、b、c和d分别是高度h0的AVL子树如下图所示 h0在上图的情况下代表已经至少存在一个节点即20的左子树开始有一个节点存在所以15位置没有节点时用h-1代替 此时插入节点的位置有两种
(a)当插入在c位置时15的平衡因子变为120的平衡因子变为-110的平衡因子变为2
(b)当插入在d位置时15的平衡因子变为-120的平衡因子变为-110的平衡因子变为2
尽管右左单旋有两种主要情况但是实际上影响到的平衡因子的更新主要思路还是先右旋再左旋为了更好观察效果以第二种情况中的第一种情况为例分析先右旋再左旋的步骤 右旋将多条路径更新化为一条路径更新 将15的右孩子作为20的左孩子 将20作为15的右孩子 15作为本棵子树的根节点链接到10节点的右孩子位置 左旋更新单一路径 将15节点的左孩子作为10节点的右孩子 10节点作为15节点的左孩子 15作为本棵子树的根 更新平衡因子
当树旋转结束后需要更新对应的平衡因子此时需要考虑到两种主要情况即h0和h0结合变量parent、subR和subRL h0左右双旋结束后如下图所示 h0 插入位置在c左右双旋结束后如下图所示 插入位置在d左右双旋结束后如下图所示
代码实现 // 右左双旋void rotateRL(node* parent){// 记录旋转前的平衡因子node* subR parent-_right;node* subRL subR-_left;int bf subRL-_bf;// 1. 右左双旋// 右旋rotateRight(parent-_right);// 左旋rotateLeft(parent);// 更新平衡因子if (bf 0){subR-_bf parent-_bf 0;}else if (bf 1)// 插入在c位置{subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1) // 插入在d位置{subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else{assert(false);}}
AVL旋转可行性
以左单旋为例其余类比推理即可
在左单旋中选择b子树作为10节点的右孩子节点是可行的因为b子树的所有节点满足比10节点大比20节点小根据二叉搜索树的规则进行旋转
AVL树节点删除待补充
AVL树分析
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即log_2 (N)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数 据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合
