是否有必要同时使用键和值来实现 BST？
是否有必要使用键和值来实现 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
}
Is it necessary to implement a BST with both keys and values? I can implement a BST that has method calls such as the following, in which it will make the comparison at each node of whether the traversal should go to the left node or right node based upon the V value:
public class BST<V>
{
public void Insert(V value)
{
//implementation
}
public V Remove(V value)
{
//implementation
}
//other methods
}
Or, I can implement the BST such that it has the method calls like the following, in which the K keys are the comparing determination of whether to traverse to the left node or the right node:
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
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
不使用键而仅使用值就可以了。但是，如果这样做，树将变得不可变。修改值不再安全，因为它会导致树不平衡。您必须通过仅为节点值提供属性获取器来强制执行此操作。
Not using a key but only a value is fine. However, the tree will become immutable if you do this. Modifying a value is no longer safe since it will imbalance the tree. You will have to enforce this by providing only a property getter for the node value.
如果它是通用数据结构，我建议使用基于键值的 API（因为您事先不知道键和值之间的关系），并在 TKey 上使用 IComparable 约束。如果它是特定于用例的实现，其中键也是一个值（例如，BST 用于确定它是否包含指定的键），我建议使用基于键的 API。
If it is general purpose data structure I'd suggest to use key-value based API (as you do not know in advance the relation between keys and values) with IComparable constraint on TKey. If it is use case specific implementation where a key is a value as well (for example, BST is used to determine whether it contains specified key or not) I'd suggest to use key based API.
这取决于您的实际需要。如果您需要关联数据结构，则必须实现基于键值的实现。否则，如果您只是将元素放入已排序的集合中，我认为不需要为每个元素设置单独的键。只需确保所有元素都实现 Comparable，或者您可以传递自定义 Comparator 实现（如在 TreeSet/TreeMap 中），或具有 BST 元素的总排序。
It depends on what you actually need. If you need an associative data structure, a key-value based implementation is what you have to implement. Otherwise, if you are simply putting elements into a sorted collection, I don't see the need to have a separate key for each element. Just make sure all elements implement Comparable or you can pass a custom Comparator implementation (like in TreeSet/TreeMap), or any well defined scheme of having a total ordering of the elements of the BST.
不，需要键才能运行的数据结构不需要任何其他东西。这仅取决于您想要如何实现它。大多数时候，使用基于键值对的系统是最方便的，但在某些实现中，您可能希望让数据结构的用户指定一个比较函数，并让每个节点存储一个“值”（一个用户定义类的实例）。该类可能包含键以及其他内容，但您不必知道该类的格式，因为用户指定的比较函数将处理所有事情。
我能想到的一个使用示例是 在 Windows 内核中。
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.