是否有必要使用键和值来实现BST？

是否需要使用键和值来实现BST？我可以实现有方法调用，如下面的一个BST，将在其中作出比较时的遍历是否应该去基于V值的左节点或右节点每个节点：是否有必要使用键和值来实现BST？

public class BST<V> 
{ 
    public void Insert(V value) 
    { 
     //implementation 
    } 

    public V Remove(V value) 
    { 
     //implementation 
    } 

    //other methods 
}

或者，我可以实现BST使得其具有的方法调用像下面，其中K个键比较是否穿越到左节点或右节点确定：

public class BST<K key, V value> 
{ 
    public void Insert(K key, V value) 
    { 
     //implementation 
    } 

    //which of the following would then be the appropriate method signature? 
    public V Remove(K key) 
    { 
     //implementation 
    } 
    //or? 
    public V Remove(V Value) 
    { 
     //implementation 
    } 

    //other methods 
}

来源

2010-01-12 Ben Lakey

不使用键，但只有一个值是好的。但是，如果你这样做，树会变得不可变。修改一个值不再安全，因为它会使树不平衡。您必须通过仅为节点值提供属性获取器来强制执行此操作。

来源

2010-01-12 09:15:33

鉴于此，你会推荐一个包含键和值的普通BST解决方案吗？ – 2010-01-12 18:06:44

绝对是的。这就是System.Collection类的工作方式。 – 2010-01-12 18:25:11

你确定你没有考虑IDictionary风格吗？ .NET中的ICollection接口实现不提供直接访问来修改元素，而IDictionary提供基于索引/键的访问。就项目访问而言，ICollection仅提供添加和删除。 – 2010-01-21 05:31:34

如果是通用数据结构我建议使用基于键值的API（因为您事先不知道键和值之间的关系）与IComparable构造不在TKey上。如果它是特定于用例的实现，其中键也是一个值（例如，BST用于确定它是否包含指定的键），我建议使用基于键的API。

来源

2010-01-12 08:10:45

如果将其开发为通用目的，是否有意义不开发键/值关系，以使泛型可以指定KeyValuePair？ – 2010-01-12 08:12:56

但KeyValuePair没有提供明确的方法来比较它所保存的任何密钥（它对密钥没有任何约束），也没有将它们自己进行配对（KeyValuePair 未实现IComparable ）。当然，你可以像比较器.Default这样的东西，但这仍然使得API模糊，因为很难说对比将如何。 – 2010-01-12 09:16:59

这取决于你实际需要什么。如果您需要关联数据结构，则必须实现基于键值的实现。否则，如果您只是将元素放入已排序的集合中，则不需要为每个元素都有单独的键。只要确保所有元素都实现了Comparable，或者您可以传递一个自定义Comparator实现（比如在TreeSet/TreeMap中），或者任何定义好的具有BST元素的方案。

来源

2010-01-12 08:50:53 MAK

不，数据结构需要密钥才能运行，不需要其他任何东西。这取决于你想如何实现它。大多数情况下，使用基于键值对的系统是最方便的，但在某些实现中，您可能希望让数据结构的用户指定一个比较函数，并让每个节点存储一个“值”（一个用户定义的类的实例）。这个类可能包含其他关键字，但是您不必知道类的格式，因为用户指定的比较函数将处理所有内容。

我能想到的一个例子是使用它的地方是in the Windows kernel。

来源

2010-01-12 09:29:16 wj32

是否有必要使用键和值来实现BST？

回答

相关问题