随机访问的自排序数据结构

Question

我需要实现随机访问的自排序数据结构。有任何想法吗？

Answer 1

自我排序有点含糊不清。首先

什么样的数据结构？

有很多不同的数据结构在那里，如：

• 链表
• 双向链表
• 二叉树
• 哈希集合/图
• 堆栈
• 堆

还有更多，他们每个人的行为都不同于其他人，并且当然有他们的好处。

现在，并不是所有的人都可以或应该自我排序，比如Stack，如果那个人自我排序，那将会很奇怪。

但是，链接列表和二叉树可以自我排序，因此您可以按不同的方式在不同的时间对其进行排序。

对于链表

我会preffere Insertion sort对于这一点，你可以阅读维基都和其他地方关于这个不同的好文章。尽管我喜欢粘贴的链接。看看它，并试图理解这个概念。

如果你想在插入后进行排序，即随机时间，那么你可以实现一个不同于插入排序的排序算法，可能是bubblesort或者quicksort，但我会避免bubblesort，但它会慢很多！但是更容易让人思索。

随机存取

随机的东西总是那被周围这么讨论了有一个关于如何执行好随机，你会用自己的方式，如果你有一个链接列表，并有一个“getAt”读 - 方法，你可以随机化一个0到n之间的索引，并获取该索引处的项目。

Answer 2

维护排序列表并随意访问它至少需要O（lgN）/操作。因此，请查找AVL，red-black trees,treaps或任何其他类似的数据结构，并将它们扩充以支持随机索引。我建议treaps，因为他们是最容易理解/实施。

丰富树木树的一种方法是在每个节点中保留以该节点为根的子树中的节点数。修改树时必须更新计数（例如：插入/删除）。

Answer 3

最近我没有太多涉及数据结构的实现。可能这个答案根本就不是答案......你应该看到Thomas Cormen写的“算法介绍”。这本书有许多“食谱”，并解释了许多数据结构的内部工作原理。 另一方面，您必须考虑您需要花费多少时间来编写算法，输入的大小以及是否存在特殊类型数据结构的实际必要性。

Answer 4

自我排序的数据结构可以是二叉搜索树。如果你想要一个自我排序的数据结构和一个自我平衡的结构。 AVL树是要走的路。对于随机访问，检索时间将为O（lgn）。