拉米拉云网站建设,做二手市场类型的网站名字,网站开发实验总结,郑州企业建公租房的政策1 介绍
平衡二叉树#xff08;AVL树#xff09;是一种特殊的二叉搜索树#xff08;BST#xff09;#xff0c;它自动确保树保持低高度#xff0c;以便实现各种基本操作#xff08;如添加、删除和查找#xff09;的高效性能。 ——时间都维持在了O(logN)它是一棵空…1 介绍
平衡二叉树AVL树是一种特殊的二叉搜索树BST它自动确保树保持低高度以便实现各种基本操作如添加、删除和查找的高效性能。 ——时间都维持在了O(logN)它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树 平衡二叉树大部分操作和二叉查找树类似主要不同在于插入删除的时候平衡二叉树的平衡可能被改变
2 插入
把需要重新平衡的结点叫做α下图中的6由于任意两个结点最多只有两个儿子因此高度不平衡时α结点的两颗子树的高度相差2.容易看出这种不平衡可能出现在下面4中情况中 1.对α的左儿子的左子树进行一次插入 2.对α的左儿子的右子树进行一次插入 3.对α的右儿子的左子树进行一次插入 4.对α的右儿子的右子树进行一次插入 情形1和情形4是关于α的镜像对称二情形2和情形3也是关于α的镜像对称 ——因此理论上看只有两种情况 外左左、右右内左右、右左
2.1 单旋转 2.1.1 左旋转
左旋转的基本步骤如下
首先创建一个新节点 该节点的值设为根节点的值新节点的左指针指向根节点的左子树新节点的右指针指向根节点的右子节点的左子树将根节点的值设置为根节点的右子节点的值根节点的左指针指向新节点根节点的右指针指向其右子节点的右子树。
比如我们插入8 显然此时不是平衡二叉树我们进行左旋转调整 于是得到了一棵二叉树
2.1.2 右旋转
右旋转基本步骤如下
首先创建一个新节点新节点的值设为根节点的值新节点的右指针指向根节点的右子树新节点的左指针指向根节点的左子节点的右子树将根节点的值设为其左子节点的值根节点的左指针指向其左子节点的左子树根节点的右指针指向新节点。
比如我们插入一个1 显然此时不是平衡二叉树我们进行右旋转调整 2.2 双旋转
对于左右和右左两种情况单旋转不能解决问题要经过两次旋转 首先以K1为根做一次左旋转
然后以K3为根做一次右旋转
2.2.1 判断是否需要双旋转
双旋转代码的核心思想在于在创建二叉树的过程中每次添加新的节点都要判断一下该二叉树是否需要旋转。
如果二叉树需要左旋则先判断根节点的右子节点的左子树高度是否大于右子树的高度如果大于则先对根节点的右子树进行右旋最后再对原二叉树进行左旋如果二叉树需要右旋则先判断根节点的左子节点的右子树高度是否大于左子树的高度如果大于则先对根节点的左子树进行左旋最后再对原二叉树进行右旋。 3 删除
同插入操作一样删除结点时也有可能破坏平衡性这就要求我们删除的时候要判断是否进行平衡性调整
3.1 删除根结点
如果左右子树都非空。在高度较大的子树中实施删除操作 左子树高度大于右子树高度将左子树中最大的那个元素赋给当前根节点然后删除左子树中元素值最大的那个节点 左子树高度小于右子树高度将右子树中最小的那个元素赋给当前根节点然后删除右子树中元素值最小的那个节点。 3.2 删除的时候进行旋转调整 参考内容平衡二叉树详解 - zhangbaochong - 博客园 (cnblogs.com)
平衡二叉树AVL树_RonzL的博客-CSDN博客
