草丁图书馆

  1. 首页 > 生活杂烩 > >

完全二叉树 最全二叉树：完整详解二叉树的遍历以及完全二叉树等6种二叉树( 二 )


4)二叉查找树的时间复杂性
时间复杂性
二叉查找树比普通树快，搜索、插入和删除的时间复杂度为o。
劣势
二叉查找树有一个极端的情况，就是会变成一个线性链表样的结构，此时时间复杂度会变成o，为了解决这种情况，出现了下面的二元平衡树。
注意:时间复杂度
O(1):最低时间空复杂度，即时间消耗与输入数据的大小无关，无论输入数据增加多少次，时间消耗/consumption 空都是常数。哈希算法是典型的O(1)时间复杂度。数据再大，一算就能找到目标。
O(n):表示数据量增加数倍，时间消耗也增加数倍。比如常见的遍历算法。
O(logn):当数据增加n倍时，时间消耗增加logn倍。二分搜索法是一个O(logn)算法，每次搜索消除一半的可能性，在256个数据中搜索8次才能找到目标。
3.4.平衡二叉树(AVL树)
1)平衡二叉树
平衡二叉树，也称为AVL树，是一种自平衡树，是从上述二叉查找树树升级而来，重点改进平衡问题。
2)平衡二叉树的特性
AVL树还规定左节点小于根节点，右节点大于根节点。
还规定了左子树和右子树的高度差不能超过1，保证了不会变成线性链表。
3)如何解决3)AVL树的平衡
主要通过左手和右手来解决，防止在特殊情况下出现以下线性结构。
因此，上面的平衡问题是通过下图中的左手和右手运动来解决的。
但是，也有相应的不足。由于需要保持自身的平衡，所以在插入和删除节点时需要频繁旋转节点。
4.结论
通过以上介绍，我们对二叉树有了初步的了解。希望读者能牢牢把握本文介绍的基础知识，在脑海中构建一个二叉树模型。如果你喜欢数据结构和算法，点击它表示你喜欢这个题目，我以后继续写。
-结束-
视频教程推荐

推荐阅读


上一篇：眼睛发炎会自愈吗 眼睛有炎症会自愈吗 教你快速解决发炎问题

下一篇：股权出质是什么意思 股权质押是什么意思？2018股权质押新规倒计时