标签: data-structures

作为程序员,我应该何时考虑使用RB树,B树或AVL树？在决定选择之前需要考虑哪些关键点？

有人可以解释一下每个树形结构的场景,为什么选择其他树木结构参考关键点？

是特里和基数特里数据结构是一回事吗？

如果它们相同,那么radix trie(AKA Patricia trie)的含义是什么？

我很困惑,我找不到快速的答案.我基本上在Java中寻找一个实现java.util.List接口的数据结构,但它以排序顺序存储其成员.我知道你可以使用普通ArrayList并使用Collections.sort()它,但我有一个场景,我偶尔会添加并经常从我的列表中检索成员,我不希望每次检索成员时都要对它进行排序,以防万一新增了一个.有人能指出我存在于JDK甚至第三方库中的这样的东西吗？

编辑:数据结构将需要保留重复.

答案摘要:我发现所有这些都非常有趣并且学到了很多东西.Aioobe尤其值得一提,因为他坚持不懈地努力实现上述要求(主要是支持重复的有序java.util.List实现).我已经接受了他的答案,因为我提出的问题是最准确的,而且最让我发现的是我正在寻找的内容的影响,即使我问的不完全是我所需要的.

我要求的问题在于List接口本身以及接口中可选方法的概念.引用javadoc:

该接口的用户可以精确控制列表中每个元素的插入位置.

插入排序列表无法精确控制插入点.然后,你必须考虑如何处理一些方法.就拿add例如:

public boolean add(Object o)

 Appends the specified element to the end of this list (optional operation).

Run Code Online (Sandbox Code Playgroud)

你现在处于令人不安的境地:1)打破合同并实现添加的排序版本2)让add一个元素添加到列表的末尾,打破你的排序顺序3)add抛出(作为其可选)抛出一UnsupportedOperationException和实施这增加了在一个有序的物品的另一种方法.

选项3可能是最好的,但我发现它有一个你不能使用的添加方法和另一个不在界面中的sortedAdd方法令人讨厌.

其他相关解决方案(无特定顺序):

• java.util.PriorityQueue可能比我要求的最接近我所需要的.在我的情况下,队列不是对象集合的最精确定义,但从功能上来说,它可以完成我需要的所有内容.
• net.sourceforge.nite.util.SortedList.但是,这个实现通过在add(Object obj)方法中实现排序来打破List接口的契约,并且奇怪地具有无效方法add(int index, Object obj).一般共识表明throw new UnsupportedOperationException()在这种情况下可能是更好的选择.
• Guava的TreeMultiSet支持重复的集合实现
• ca.odell.glazedlists.SortedList 此类在其javadoc中附带警告:Warning: This class breaks the contract required by List

我最近意识到,虽然在我的生活中使用了BST,但我甚至都没有考虑过使用任何东西而是使用Inorder遍历(虽然我知道并且知道调整程序使用前/后顺序遍历是多么容易).

在意识到这一点之后,我拿出了一些旧的数据结构教科书,并寻找了预订和后序遍历的有用性背后的推理 - 但他们并没有说太多.

什么时候实际使用预订/后期订单的一些例子？什么时候比按顺序更有意义？

除了优先级队列的明显答案之外,什么时候堆在我的编程冒险中会有用？

.NET中的基类库为集合(List,Queue,Stack,Dictionary)提供了一些出色的数据结构,但奇怪的是它不包含二进制树的任何数据结构.对于某些算法,例如利用不同遍历路径的算法,这是非常有用的结构.我正在寻找一个正确编写的免费实现.

我只是瞎了,没找到它......它被埋在BCL的某个地方吗？如果没有,有人可以为二进制树推荐免费或开源的C#/.NET库吗？优选使用仿制药的一种.

编辑:澄清我在寻找什么.我对内部使用树的有序字典集合不感兴趣.我实际上对二叉树感兴趣 - 一个公开其结构的树,以便您可以执行诸如提取子树或在节点上执行修复后遍历等操作.理想情况下,这样的类可以扩展为提供专门树的行为(即红/黑,AVL,平衡等).

我只是在C++中错误地做了类似的事情,并且它有效.我为什么要这样做？

int main(int argc, char** argv) {
    struct MyStruct
    {
      int somevalue;
    };

    MyStruct s;
    s.somevalue = 5;
}

在做完这个之后,我记得很久以前在某个地方读过这个技巧,作为一种穷人用于C++的函数式编程工具,但我不记得为什么这个有效,或者我读到它.

欢迎回答任何一个问题!

注意:虽然在写这个问题时我没有得到任何关于这个问题的引用,但是当前的侧边栏指出了它,所以我会把它放在这里供参考,无论哪种方式问题都不同但可能有用.

根据我从SelectMany的文档中理解,可以使用它来生成1-many关系的(扁平化)序列.

我有以下课程

  public class Customer
  {
    public int Id { get; set; }
    public string Name { get; set; }
  }

  class Order
  {
    public int Id { get; set; }
    public int CustomerId { get; set; }
    public string Description { get; set; }
  }

然后我尝试使用查询表达式语法来使用它们

  var customers = new Customer[]
  {
    new Customer() { Id=1, Name ="A"},
    new Customer() { Id=2, Name ="B"},
    new Customer() { Id=3, Name ="C"}
  };

  var orders = new Order[]
  {
    new Order …

我试图列出常见数据结构的操作的时间复杂性,如数组,二进制搜索树,堆,链表等,尤其是我指的是Java.它们很常见,但我想我们中的一些人对确切的答案并不是100%有信心.任何帮助,特别是参考,非常感谢.

例如,对于单链表:更改内部元素是O(1).你怎么能这样做？你HAVE更改它之前要搜索的元素.另外,对于Vector,添加内部元素为O(n).但是为什么我们不能在使用索引的摊销常数时间内做到这一点？如果我错过了什么,请纠正我.

我发布我的发现/猜测作为第一个答案.

除了节点中的红色和黑色外,AVL和红黑树都是自平衡的.选择红黑树而不是AVL树的主要原因是什么？红黑树有哪些应用？