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

Question

Необходимо ли внедрять летнее время как с ключами, так и со значениями?Я могу реализовать 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
}

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

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