Необходимо ли реализовать BST с ключами и значениями? - PullRequest
Новая
       22

Необходимо ли реализовать BST с ключами и значениями?

1 голос
/ 12 января 2010

Необходимо ли реализовать 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 ]

2 голосов
/ 12 января 2010

Не использовать ключ, но подходит только значение. Тем не менее, дерево станет неизменным, если вы сделаете это. Изменение значения больше не безопасно, так как это приведет к дисбалансу дерева. Вам придется применить это, предоставив только значение свойства get для значения узла.

0 голосов
/ 12 января 2010

Нет, структуры данных, которым для работы нужны ключи, больше ничего не требуют. Это зависит только от того, как вы хотите это реализовать. Большую часть времени использование системы на основе пар «ключ-значение» является наиболее удобным, но в некоторых реализациях вы можете захотеть позволить пользователю структуры данных указать функцию сравнения и просто заставить каждый узел хранить «значение» экземпляр пользовательского класса). Этот класс может содержать ключ, помимо прочего, но вам не нужно знать формат класса, потому что пользовательская функция сравнения позаботится обо всем.

Пример, который я могу вспомнить, где это используется, в ядре Windows .

0 голосов
/ 12 января 2010

Это зависит от того, что вам действительно нужно. Если вам нужна ассоциативная структура данных, то вам нужно реализовать реализацию на основе значения ключа. В противном случае, если вы просто помещаете элементы в отсортированную коллекцию, я не вижу необходимости иметь отдельный ключ для каждого элемента. Просто убедитесь, что все элементы реализуют Comparable, или вы можете передать собственную реализацию Comparator (как в TreeSet / TreeMap), или любую четко определенную схему с общим порядком элементов BST.

0 голосов
/ 12 января 2010

Если это структура данных общего назначения, я бы предложил использовать API на основе значений ключей (поскольку вы заранее не знаете связь между ключами и значениями) с ограничением IComparable для TKey. Если это реализация конкретного случая использования, где ключ также является значением (например, BST используется для определения, содержит ли он указанный ключ или нет), я бы предложил использовать API на основе ключей.

...