Articles tagged "数据结构"

在程序设计和编程中，我们经常会看到关于时间复杂度的讨论。比如为什么A方法比B方法好？是因为A方法的时间复杂度低。那么，这里的时间复杂度如何去理解，又怎么计算呢？常见的O(n)的含义是什么？本文将简单的解释这个概念。

数据结构中，自平衡二叉查找树搜索效率高，但是需要通过旋转和变色维护平衡。而列表虽然简单，但是对元素的查找需要比对列表中的每个元素，查找速度较慢。为了兼顾列表的简单易用，并提高查找效率，跳跃列表（Skip List）应运而生。

红黑树（Red-Black Tree）也是一种自平衡二叉查找树，与AVL不同的是它依靠节点颜色来维护树的平衡，在自平衡操作的时候，依赖变色和旋转两种操作来进行。

在前面的内容中，我们已经介绍了平衡二叉树。其中提到了AVL树，这是一种非常著名的平衡二叉树。这是第一个发明类似自平衡机制的二叉树数据结构。在AVL树中，任何节点的两个子树的高度最多相差一个。如果在任何时候它们相差多于一个，则重新平衡以恢复此属性。

二叉查找树是一种特殊的二叉树结构，它改善了二叉树的查找效率，二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。与一般的二叉树的主要区别就是它对子节点的键值排序有一定要求。