数据结构-7.4查找_给定一个关键字序列4,5,7,2,1,3,6,试生成一棵平衡二叉树

作者：Cpp五条 | 2024-04-13 22:24:59

踩

给定一个关键字序列4,5,7,2,1,3,6,试生成一棵平衡二叉树

前言-数据结构

数据结构是需要反复咀嚼，不管什么时候都可以重中获取现在在开发中的遇到的问题答案。

举例说明:给定-个关键字序列4,5,7,2 ,1,3,6，试生成一棵平衡二叉树。
分析:平衡二叉树实际上也是一棵叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见下图。

平衡二叉树本身就是一棵叉排序树，故它的查找与二叉排序树完全相同。但它的查找性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二又排序树的最好时间复杂相同，都为O(log2n)。

二叉排序树0(n)
平衡二叉树ASL Succ = log2(n +1)-1 = log2n

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/418834