如何根据需求选择合适的查找算法：顺序查找、二分查找、二叉平衡树、B树、红黑树？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1355个文字，预计阅读时间需要6分钟。
目录+ 排序查找+ 二分查找+ 二叉平衡树+ B树+ 红黑树+ 参考文献及资料+ 排序查找 给你一组数据，最自然的查找效率最低的算法是顺序查找——从前往后逐个比较。 时间复杂度：O(n)
- 顺序查找
- 二分查找
- 二叉平衡树
- B树
- 红黑树
- B+树
- 参考文档
给你一组数，最自然的效率最低的查找算法是顺序查找——从头到尾挨个挨个遍历查找，它的时间复杂度为O(n)。
二分查找而另一个大家都知道的，效率很高经典查找算法——二分查找法，它的时间复杂度是O(logn)。但二分法的数据结构是数组，这样才能通过公式(low+height)/2=middle计算出中间位置的元素。而数组的修改效率很低，最坏的情况下，插入一个元素，要移动n个元素。
通过模拟二分查找法的插入、查找过程，会发现和二叉平衡树很相似，那我们分析一下二叉平衡树。简单的二叉树无法保证能保证查找的每一步节点是二分法中的中间位置，最坏情况会蜕变为顺序查找。所以需要对二叉树进行调整，让它变成二叉平衡树，这样查找的效率就能保证了，二叉平衡树的查找时间复杂度也是O(logn)。但是二叉平衡树的缺点在于，调整的消耗很大。它的每次插入，都要一层一层往上确认、调整。
本文共计1355个文字，预计阅读时间需要6分钟。
目录+ 排序查找+ 二分查找+ 二叉平衡树+ B树+ 红黑树+ 参考文献及资料+ 排序查找 给你一组数据，最自然的查找效率最低的算法是顺序查找——从前往后逐个比较。 时间复杂度：O(n)
- 顺序查找
- 二分查找
- 二叉平衡树
- B树
- 红黑树
- B+树
- 参考文档
给你一组数，最自然的效率最低的查找算法是顺序查找——从头到尾挨个挨个遍历查找，它的时间复杂度为O(n)。
二分查找而另一个大家都知道的，效率很高经典查找算法——二分查找法，它的时间复杂度是O(logn)。但二分法的数据结构是数组，这样才能通过公式(low+height)/2=middle计算出中间位置的元素。而数组的修改效率很低，最坏的情况下，插入一个元素，要移动n个元素。
通过模拟二分查找法的插入、查找过程，会发现和二叉平衡树很相似，那我们分析一下二叉平衡树。简单的二叉树无法保证能保证查找的每一步节点是二分法中的中间位置，最坏情况会蜕变为顺序查找。所以需要对二叉树进行调整，让它变成二叉平衡树，这样查找的效率就能保证了，二叉平衡树的查找时间复杂度也是O(logn)。但是二叉平衡树的缺点在于，调整的消耗很大。它的每次插入，都要一层一层往上确认、调整。