深圳网站优化最好的方法,wordpress无法注册,移动端程序开发,北京太阳宫网站建设文章目录 平衡二叉树总览平衡二叉树的定义平衡二叉树的插入调整最小不平衡子树在A的左孩子的左子树中插入导致不平衡在A的右孩子的右子树中插入导致不平衡上述两种的代码思路在A的左孩子的右子树中插入导致不平衡在A的右孩子的左子树中插入导致不平衡 填个坑练习查找效率分析小… 文章目录 平衡二叉树总览平衡二叉树的定义平衡二叉树的插入调整最小不平衡子树在A的左孩子的左子树中插入导致不平衡在A的右孩子的右子树中插入导致不平衡上述两种的代码思路在A的左孩子的右子树中插入导致不平衡在A的右孩子的左子树中插入导致不平衡 填个坑练习查找效率分析小结 平衡二叉树的删除删除的节点是叶子-例1删除的节点是叶子-例2删除的节点是叶子-例3删除的节点是叶子-例4删除的节点是有左右子树的-例5删除的节点是有左右子树的-例6小结 平衡二叉树
总览 平衡二叉树的定义
保存平衡查找长度小些
平衡二叉树的插入
插入后再调整树使其恢复平衡。 调整过后发现恢复平衡
调整最小不平衡子树 规律 左孩子右旋 右孩子左旋
在A的左孩子的左子树中插入导致不平衡 关于为什么所有子树的高度都是h是因为如果h1或者h-1那么插入后要不最小不平衡子树不是A要不插入后没有最小不平衡子树要不在插入前就已经出现最小不平衡子树了。总而言之都不满足假设的情况
在A的右孩子的右子树中插入导致不平衡
与上面的情况差不多只不过改的位置不一样而已
上述两种的代码思路
都是先更新A节点的子树为b的某个子树然后再更新b的子树节点为f最后再更新原来f的父节点中的子节点为b
在A的左孩子的右子树中插入导致不平衡 先左旋后右旋的结果 此时对应插入到c的左右子树两种情况
在A的右孩子的左子树中插入导致不平衡 先右旋再左旋的过程
填个坑 最小不平衡子树调整好后其父亲树都会调整平衡
练习
插入后找到最小不平衡子树让孩子旋转 再插入 再插入
查找效率分析
由平衡二叉树可知道高度为h的平衡二叉树的节点最少的话是由一个根节点和两个子树构成其中一颗子树为高度为h-1的最少节点数所构成的平衡二叉树此时可以满足该树深度为h而另一颗子树为高度为h-2的最少节点数所构成的平衡二叉树即可若也为h-1的最少节点数所构成的平衡二叉树那么此时没必要节点相比与高度为h-2的最少节点数所构成的平衡二叉树多了所以为h-2的即可
小结 平衡二叉树的删除
删除节点后也要维持平衡二叉树的平衡 删除的节点是叶子-例1 删除的节点是叶子-例2
先删节点 然后先上找到最小不平衡子树的根节点同时找到该个头最高的儿子和孙子 根据孙子位置调整 此时80左旋
删除的节点是叶子-例3 删除的节点是叶子-例4 此时调整完后发现不平衡了此时从调整后的子树继续向上传导找到最小不平衡子树 右旋后不平衡特性没有向上传到了
删除的节点是有左右子树的-例5
两种顶替的策略 转换为删除的节点只有一个子树的类型 删除后 往上找最小不平衡子树儿子左旋一次即可 没有向上传导
删除的节点是有左右子树的-例6
此时用后继节点顶替 转换为删除叶子节点 此时向北找到最小不平衡子树 此时孙子个头一样所以选哪个作为个头最高的孙子 假设此时为右孙子为个头最高 此时儿子左旋一次即可 假设此时左孙子为个头最高 此时孙子先右旋 再左旋此时不平衡无向上传导
小结
旋转后子树变矮导致上层祖先不平衡 注意平衡二叉树删除操作的时间复杂度和插入的时间复杂度是一样的
