用旧电脑做网站,怎么编写app软件,网站建设包含哪些,关于推动门户网站建设d目录 一、平衡二叉树的定义二、平衡因子三、平衡二叉树的插入和构造#xff08;一#xff09;LL型旋转#xff08;二#xff09;LR型旋转#xff08;三#xff09;RR型旋转#xff08;四#xff09;RL型旋转 四、平衡二叉树的删除#xff08;一#xff09;叶子结点一LL型旋转二LR型旋转三RR型旋转四RL型旋转 四、平衡二叉树的删除一叶子结点二只有左/右子树没有右/左子树三既有左子树又有右子树 五、平衡二叉树的查找和平均查找长度 一、平衡二叉树的定义
平衡二叉树以二叉排序树为基础若二叉排序树中左、右子树的高度之差的绝对值不超过1则称为平衡二叉树AVL树其左、右子树也为一棵平衡二叉树其平均查找长度为O(log2n)如下
二、平衡因子
二叉树中左子树的深度减去其右子树深度称为该结点的平衡因子平衡二叉树中结点的平衡因子只可能为1、-1或0三种其中叶子结点的平衡因子均为0例如下面这个二叉树为平衡二叉树
叶子结点0、1、6的平衡因子均为0 结点4的左子树深度为1右子树深度为0所以平衡因子为1-01 结点9的左子树深度为1右子树深度为0所以平衡因子为1-01 结点2的左子树深度为1右子树深度为2所以平衡因子为1-2-1 结点5的左子树深度为3右子树深度为2所以平衡因子为3-21。 而下图这个二叉树为非平衡二叉树 叶子结点0、1、4、9的平衡因子均为0 结点3的左子树深度为1右子树深度为1所以平衡因子为1-10 结点2的左子树深度为1右子树深度为2所以平衡因子为1-2-1 结点5的左子树深度为3右子树深度为1所以平衡因子为3-12不满足平衡二叉树的要求。
三、平衡二叉树的插入和构造
平衡二叉树的插入操作性质与二叉排序树一样也是要在保证一定条件下进行插入操作若导致不满足条件则需要进行调整。若平衡二叉树中插入一个元素时导致发生了不平衡则需要调整元素的位置关系使其达到平衡。 插入新结点导致不平衡的情况有以下四种
类别操作LL型旋转右单旋转在结点的左子树的左子树插入新结点导致失衡LR型旋转先左后右旋转在结点的左子树的右子树插入新结点导致失衡RR型旋转左单旋转在结点的右子树的右子树插入新结点导致失衡RL型旋转先右后左旋转在结点的右子树的左子树插入新结点导致失衡
一LL型旋转
若在结点的左子树的左子树插入新结点导致平衡二叉树失衡则进行LL型旋转即右单旋转。 插入新结点6后导致平衡二叉树失衡插入位置是结点9的左子树的左子树处所以进行LL型旋转如下 调整后的二叉树即为平衡二叉树。
二LR型旋转
若在结点的左子树的右子树插入新结点导致平衡二叉树失衡则进行LR型旋转即先左后右旋转。 插入新结点7后导致平衡二叉树失衡插入位置是结点9的左子树的右子树处所以进行LR型旋转如下 调整后的二叉树即为平衡二叉树。
三RR型旋转
若在结点的右子树的右子树插入新结点导致平衡二叉树失衡则进行RR型旋转即左单旋转。 插入新结点10后导致平衡二叉树失衡插入位置是结点7的右子树的右子树处所以进行RR型旋转如下 调整后的二叉树即为平衡二叉树。
四RL型旋转
若在结点的右子树的左子树插入新结点导致平衡二叉树失衡则进行RL型旋转即先右后左旋转。 插入新结点6后导致平衡二叉树失衡插入位置是结点5的右子树的左子树处所以进行RL型旋转如下 调整后的二叉树即为平衡二叉树。
四、平衡二叉树的删除
一叶子结点
平衡二叉树中若要删除的结点只有叶子结点则可直接将其删除不影响平衡二叉树。 例如删除平衡二叉树中的结点9由于该结点是叶子结点所以直接删除如下
二只有左/右子树没有右/左子树
平衡二叉树中若要删除的结点只有左/右子树没有右/左子树此时将该结点删除后面的子结点接上即可从而不影响平衡二叉树。
三既有左子树又有右子树
平衡二叉树中若要删除的结点既有左子树又有右子树此时可沿着左右子树的右左指针一直走到右左子树的最右左边的一个结点用该结点与要删除的结点代替【找到交换的结点】然后可以将其转换为一、二中的情况若替代后该结点为叶子结点则按照一进行删除若非叶子结点则按照二进行删除。 例如删除平衡二叉树中结点11首先找到要交换的结点即结点9所以结点11与结点9进行交换如下 然后由于此时结点11是叶子结点此时转换为第一种情况所以可直接删除如下
五、平衡二叉树的查找和平均查找长度
平衡二叉树的查找与二叉排序树一样含有n个结点的平衡二叉树的最大深度为h⌈log2(n1)⌉所以其平均查找长度为O(log2n)另外平衡二叉树的最小深度为h⌈log2(n1)⌉。
