Глава 13. Бинарное дерево поиска

Оригинал: Chapter 13 Binary search tree

Переводчик: Летающий дракон

Протокол: CC BY-NC-SA 4.0

Гордо использую Google Translate

В этой главе представлено решение предыдущего упражнения, а также проводится тестирование производительности древовидных структур данных. Я продемонстрировал проблему реализации и объяснил, как Java TreeMap решает её.

13.1 Простая реализация MyTreeMap

В предыдущем упражнении я дал вам план MyTreeMap и попросил заполнить недостающие методы. Теперь я покажу результаты, начиная с findNode:

private Node findNode(Object target) {
    // some implementations can handle null as a key, but not this one
    if (target == null) {
            throw new IllegalArgumentException();
    }

    // something to make the compiler happy
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) target;

    // the actual search
    Node node = root;
    while (node != null) {
        int cmp = k.compareTo(node.key);
        if (cmp < 0)
            node = node.left;
        else if (cmp > 0)
            node = node.right;
        else
            return node;
    }
    return null;
}

findNode — это частный метод, используемый containsKey и get; он не является частью интерфейса Map. Параметр target — это ключ, который мы ищем. В предыдущем упражнении я объяснил первую часть этого метода:

• В этой реализации null не является допустимым значением ключа.
• До того, как мы сможем вызвать compareTo на target, мы должны привести его к определённому типу Comparable. Здесь используется «тип-заполнитель», который допускает как можно больше; то есть он работает для любого типа, реализующего Comparable, и чей compareTo принимает K или суперкласс K.

Затем фактический поиск становится довольно простым. Мы инициализируем переменную цикла node, которая ссылается на корневой узел. На каждой итерации мы сравниваем цель с node.key. Если цель меньше текущего ключа, мы переходим к левому поддереву. Если она больше, мы переходим к правому поддереву. Если они равны, мы возвращаем текущий узел.

Если мы не находим цель и достигаем дна дерева, я предполагаю, что её нет в дереве, и возвращаю null.

13.2 Поиск значения

В предыдущей главе я объяснил, что время выполнения findNode пропорционально высоте дерева, а не количеству узлов, потому что нам не нужно искать всё дерево. Однако для containsValue мы должны искать значение, а не ключ; свойства BST не применимы к значениям, поэтому мы должны искать всё дерево.

Мой подход рекурсивен:

public boolean containsValue(Object target) {
    return containsValueHelper(root, target);
}

private boolean containsValueHelper(Node node, Object target) {
    if (node == null) {
        return false;
    }
    if (equals(target, node.value)) {
        return true;
    }
    if (containsValueHelper(node.left, target)) {
        return true;
    }
    if (containsValueHelper(node.right, target)) {
        return true;
    }
    return false;
}

containsValue принимает целевое значение в качестве параметра и немедленно вызывает containsValueHelper, передавая корневой узел дерева в качестве дополнительного параметра.

Вот как работает containsValueHelper:

• Первый оператор if проверяет граничное условие рекурсии. Если node равен null, это означает, что мы уже достигли дна дерева и не нашли target, поэтому мы должны вернуть false. Обратите внимание, что это просто означает, что цель не была найдена на этом пути; она всё ещё может быть обнаружена на другом пути.
• Второй случай проверяет, нашли ли мы то, что искали. Если да, мы возвращаем true. В противном случае мы должны продолжить.
• Третий случай выполняет рекурсивный вызов для поиска target в левом поддереве. Если мы найдём его, мы можем сразу же вернуть true, не ища правое поддерево. В противном случае продолжаем.
• Четвёртый случай ищет правое поддерево. Аналогично, если мы находим то, что ищем, мы возвращаем true. В противном случае, когда мы пройдём по всему дереву, мы вернём false.

Этот метод «посещает» каждый узел в дереве, поэтому его время выполнения пропорционально количеству узлов.

13.3 Реализация put

Метод put немного сложнее, чем get, поскольку он должен обрабатывать два случая: (1) если заданный ключ уже находится в дереве, заменить и вернуть старое значение; (2) в противном случае необходимо добавить новый узел в дерево в правильном месте.

В предыдущем упражнении я предоставил этот начальный код:

public V put(K key, V value) {
    if (key == null) {
        throw new IllegalArgumentException();
    }
    if (root == null) {
        root = new Node(key, value);
        size++;
        return null;
    }
    return putHelper(root, key, value);
}

И попросил вас заполнить putHelper. Вот мой ответ:

private V putHelper(Node node, K key, V value) {
    Comparable<? super K> k = (Comparable<? super K>) key;
    int cmp = k.compareTo(node.key);

    if (cmp < 0) {
        if (node.left == null) {
            node.left = new Node(key, value);
            size++;
            return null;
        } else {
            return putHelper(node.left, key, value);
        }
    }
    if (cmp > 0) {
        if (node.right == null) {
            node.right = new Node(key, value);
            size++;
            return null;
        } else {
            return putHelper(node.right, key, value);
        }
    }
    V oldValue = node.value;
    node.value = value;
    return oldValue;
}

Первый параметр node изначально является корнем дерева, но каждый раз, когда мы выполняем рекурсивный вызов, он указывает на другое поддерево. Как и в случае с get, мы используем compareTo, чтобы определить, по какому пути следовать по дереву. Если cmp < 0, добавляемый ключ меньше node.key, тогда мы идём влево. Есть два случая:

• Если левое поддерево пусто, то есть если node.left равно null, мы достигли дна дерева без нахождения key. В этом случае мы знаем, что key отсутствует в дереве, и мы знаем, где его следует разместить. Поэтому мы создаём новый узел и добавляем его как левое поддерево node.
• Иначе мы делаем рекурсивный вызов для поиска левого поддерева.

Если cmp > 0, то добавляемый ключ больше node.key, и мы идём вправо. Мы обрабатываем эти два случая так же, как и предыдущий раздел. Наконец, если cmp == 0, мы нашли ключ в дереве, затем мы изменяем его и возвращаем старое значение.

Я использовал рекурсию для написания этого метода, чтобы сделать его более читаемым, но его можно было бы переписать напрямую с использованием итерации, которую вы, возможно, захотите попробовать в качестве упражнения.

13.4 Обход в порядке

Примечание: в тексте запроса присутствуют фрагменты кода на языке Java. Перевод этих фрагментов выполнен с помощью сервиса машинного перевода.