这篇文章给大家分享的是有关C语言平衡二叉树的示例分析的内容免费云主机域名。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。平衡二叉树大部分操作和二叉查找树类似，主要不同在于插入删除的时候平衡二叉树的平衡可能被改变，并且只有从那些插入点到根结点的路径上的结点的平衡性可能被改变，因为只有这些结点的子树可能变化。平衡二叉树不平衡的情形：把需要重新平衡的结点叫做，由于任意两个结点最多只有两个儿子，因此高度不平衡时，结点的两颗子树的高度相差2.容易看出，这种不平衡可能出现在下面4中情况中：1.对的左儿子的左子树进行一次插入2.对的左儿子的右子树进行一次插入3.对的右儿子的左子树进行一次插入4.对的右儿子的右子树进行一次插入情形1和情形4是关于的镜像对称，二情形2和情形3也是关于的镜像对称，因此理论上看只有两种情况，但编程的角度看还是四种情形。第一种情况是插入发生在“外边”的情形（左左或右右），该情况可以通过一次单旋转完成调整；第二种情况是插入发生在“内部”的情形（左右或右左），这种情况比较复杂，需要通过双旋转来调整。上图是左左的情况，k2结点不满足平衡性，它的左子树k1比右子树z深两层，k1子树中更深的是k1的左子树x，因此属于左左情况。为了恢复平衡，我们把x上移一层，并把z下移一层，但此时实际已经超出了AVL树的性质要求。为此，重新安排结点以形成一颗等价的树。为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。这种情况称为单旋转。对于左右和右左两种情况，单旋转不能解决问题，要经过两次旋转。对于上图情况，为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以k2为根的平衡二叉树。同插入操作一样，删除结点时也有可能破坏平衡性，这就要求我们删除的时候要进行平衡性调整。首先在整个二叉树中搜索要删除的结点，如果没搜索到直接返回不作处理，否则执行以下操作：如果左右子树都非空。在高度较大的子树中实施删除操作。分两种情况：(1)、左子树高度大于右子树高度，将左子树中最大的那个元素赋给当前根节点，然后删除左子树中元素值最大的那个节点。(1)、左子树高度小于右子树高度，将右子树中最小的那个元素赋给当前根节点，然后删除右子树中元素值最小的那个节点。如果左右子树中有一个为空，那么直接用那个非空子树或者是NULL替换当前根节点即可。递归调用，在左子树中实施删除。这个是需要判断当前根节点是否仍然满足平衡条件，如果满足平衡条件，只需要更新当前根节点T的高度信息。否则，需要进行旋转调整：如果T的左子节点的左子树的高度大于T的左子节点的右子树的高度，进行相应的单旋转。否则进行双旋转。下面给出详细代码实现：AvlTree.hmain.cpp测试结果：感谢各位的阅读！关于“C语言平衡二叉树的示例分析”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
这篇文章主要讲解了“怎么用Java代码制作一个简单的小游戏”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“怎么用Java代码制作一个简单的小游戏”吧！java简易小游戏制作游戏思路：设置人物移动，游戏规则，积分系…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
