1

是否有必要使用键和值来实现BST ？我可以实现一个具有如下方法调用的 BST，其中它将根据 V 值在每个节点上进行遍历是应该去左节点还是右节点的比较：

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
}
4

4 回答 4

2

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

于 2010-01-12T09:15:33.740 回答
0

No, data structures which need keys to function do not require anything else. It just depends on how you want to implement it. Most of the time using a key-value-pair-based system is the most convenient, but in some implementations you might want to let the user of the data structure specify a comparison function and just have each node store a "value" (an instance of a user-defined class). This class might contain the key among other things, but you don't have to know the format of the class, because the user-specified comparison function will take care of everything.

An example I can think of where this is used is in the Windows kernel.

于 2010-01-12T09:29:16.413 回答
0

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

于 2010-01-12T08:50:53.260 回答
0

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

于 2010-01-12T08:10:45.233 回答