是否有必要使用鍵和值來實現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？

回答

相關問題