红黑树

我已经看过我最近读过的几本书中提到的二叉树和二进制搜索,但是由于我还在学习计算机科学,我还没有上一个真正处理算法和数据的课程.结构严肃.

我查看了典型的来源(维基百科,谷歌),大多数关于(特别是)红黑树的实用性和实施​​的描述都是密集且难以理解的.我确信对于具有必要背景的人来说,它是完全合理的,但此刻它几乎就像一本外语.

那么是什么让二进制树在你编程时发现的一些常见任务中有用呢？除此之外,您更喜欢使用哪些树(请包括示例实现)以及为什么？

红黑树有助于营造均衡的树木.二叉搜索树的主要问题是你可以很容易地使它们失衡.想象一下你的第一个数字是15.那么之后的所有数字都会小于15.你的左侧树很重,右侧没有任何东西.

红黑树通过在插入或删除时强制平衡树来解决这个问题.它通过祖先节点和子节点之间的一系列旋转来实现这一点.该算法实际上非常简单,虽然它有点长.我建议拿起CLRS(Cormen,Lieserson,Rivest和Stein)教科书,"算法导论"和阅读RB树.

实现也不是那么短,所以在这里包含它可能并不是最好的.然而,树广泛用于需要访问大量数据的高性能应用程序.它们提供了一种非常有效的查找节点的方法,插入/删除开销相对较小.同样,我建议查看CLRS以了解它们的使用方式.

虽然可能没有明确使用BST,但几乎每一个现代RDBMS中都有一个使用树的例子.同样,您的文件系统几乎可以肯定地表示为某种树结构,并且文件同样以这种方式索引.树木为Google提供动力 树木为互联网上的每个网站提供动力.

我只想解决一个问题"那么是什么让二进制树在编程时你会发现的一些常见任务中有用呢？"

这是一个很多人不同意的大话题.有人说,在CS程度上教授的算法,如二元搜索树和有向图,不会用于日常编程,因此无关紧要.其他人不同意,他们说这些算法和数据结构是我们所有编程的基础,即使你不必为自己编写一个,也必须理解它们.这会过滤关于良好面试和招聘实践的对话.例如,Steve Yegge 在Google上有一篇关于采访的文章来解决这个问题.记住这场辩论; 有经验的人不同意.

在典型的业务编程中,您可能根本不需要经常创建二叉树甚至树.但是,您将使用许多使用树在内部操作的类.每种语言中的许多核心组织类都使用树和哈希来存储和访问数据.

如果您参与了更多高性能的工作或者有些超出商业编程规范的情况,您会发现树木是直接的朋友.正如另一张海报所说,树是各种数据库和索引的核心数据结构.它们在数据挖掘和可视化,高级图形(2d和3d)以及许多其他计算问题中非常有用.

我在3d图形中使用了BSP(二进制空间分区)树形式的二叉树.我目前正在再次查看树木,以便对Flash/Flex应用程序中的信息可视化进行大量地理编码数据和其他数据的排序.无论何时推动硬件的边界,或者想要在较低的硬件规格上运行,理解和选择最佳算法都可以在失败和成功之间产生差异.

没有一个答案能提到BSTs的优点.

如果你想要做的只是按值查找,那么散列表要快得多,O(1)插入和查找(最佳情况下摊销).

BST将是O(log N)查找,其中N是树中的节点数,插入也是O(log N).

RB和AVL树很重要,因为这个属性提到了另一个答案,如果使用有序值创建普通BST,那么树将与插入的值的数量一样高,这对于查找性能是不利的.

RB和AVL树之间的区别在于插入或删除后重新平衡所需的旋转,AVL树是重新平衡的O(log N),而RB树是O(1).这种持续复杂性的好处的一个例子是,在您可能保留持久数据源的情况下,如果您需要跟踪回滚更改,则必须使用AVL树跟踪O(log N)可能的更改.

为什么你愿意支付哈希表上树的成本？订购!哈希表没有顺序,另一方面,BST总是凭借其结构自然排序.因此,如果您发现自己在数组或其他容器中抛出一堆数据然后再对其进行排序,那么BST可能是更好的解决方案.

树的order属性为您提供了许多有序的迭代功能,按顺序,深度优先,广度优先,预订,后订购.如果您想查找它们,这些迭代算法在不同情况下很有用.

几乎每个有序的语言库容器,C++ Set and Map,.NET SortedDictionary,Java TreeSet等都在内部使用红黑树......

所以树木非常有用,你可以经常使用它们而不知道它.你很可能永远不需要自己写一个,但我强烈推荐它作为一个有趣的编程练习.