Слияние кода завершено, страница обновится автоматически
Исходный текст: Chapter 12 TreeMap.
Переводчик: Фейлун (https://github.com/wizardforcel).
Лицензия: CC BY-NC-SA 4.0 (http://creativecommons.org/licenses/by-nc-sa/4.0/).
С гордостью использую Google Translate (https://translate.google.cn/).
В этой главе рассматривается двоичное дерево поиска, которое является эффективной реализацией интерфейса Map. Если мы хотим упорядочить элементы, оно очень полезно.
К этому моменту вы должны быть знакомы с интерфейсом Map и его реализацией HashMap в Java. Создавая собственную реализацию Map с использованием хеш-таблицы, вы должны понимать принцип работы HashMap и почему мы ожидаем, что его основные методы будут иметь постоянное время выполнения.
Благодаря такой производительности HashMap широко используется, но это не единственная реализация Map. Есть несколько причин, по которым может потребоваться другая реализация:
Трудно решить все эти проблемы одновременно, но Java предоставляет реализацию, называемую TreeMap:
В следующем разделе я объясню, как работает двоичное дерево поиска, а затем вы будете использовать его для реализации Map. Кроме того, при использовании дерева мы проанализируем производительность основных методов отображения.
Двоичное дерево поиска (BST) — это дерево, в котором каждый узел содержит ключ, и каждый из них имеет «свойство BST»:
Рисунок 12.1 показывает пример дерева с этим свойством. Изображение взято с веб-страницы двоичного дерева поиска на Википедии, расположенной по адресу http://thinkdast.com/bst, и будет полезно, когда вы будете выполнять это упражнение.
Корневой узел имеет ключ 8, и вы можете убедиться, что все ключи слева от корневого узла меньше 8, а все ключи справа больше. Вы также можете проверить, обладают ли другие узлы этим свойством.
Поиск ключа в двоичном дереве поиска происходит быстро, потому что нам не нужно искать всё дерево. Начиная с корневого узла, мы можем использовать следующий алгоритм:
На каждом уровне дерева нам нужно искать только одно поддерево. Например, если вы ищете target = 4 в приведённом выше примере, начиная с корневого узла с ключом 8, поскольку 4 меньше 8, вы переходите к левому поддереву. Поскольку 4 больше 3, вы переходите вправо. Поскольку 4 меньше 6, вы снова переходите влево. Затем вы находите нужный ключ.
В этом примере, даже если дерево содержит девять ключей, требуется четыре сравнения, чтобы найти цель. Вообще говоря, количество сравнений пропорционально высоте дерева, а не количеству ключей в дереве.
Таким образом, мы можем вычислить отношение высоты h дерева и количества узлов n. Начнём с небольшого числа и постепенно увеличиваем его:
Если h = 1, дерево состоит только из одного узла, тогда n = 1. Если h = 2, мы можем добавить два узла, всего n = 3. Если h = 3, мы можем добавить до четырёх узлов, всего n = 7. Если h = 4, мы можем добавить до восьми узлов, всего n = 15.
Теперь вы, возможно, увидите закономерность. Если мы будем считать слои дерева от 1 до n, i-й слой может содержать до 2^(n-1) узлов. Слой h имеет 2^h - 1 узлов. Если у нас есть:
n = 2^h – 1
Мы можем взять логарифм по основанию 2 с обеих сторон:
log2(n) ≈ h
Это означает, что высота дерева пропорциональна logn, если оно полностью заполнено. То есть, если каждый слой содержит максимальное количество узлов.
Поэтому мы ожидаем, что сможем искать узлы в двоичном дереве поиска за время, пропорциональное logn. Если дерево медленное, даже частично заполненное, это верно. Но это не всегда так, и мы увидим это.
Алгоритм времени, пропорционального logn, является алгоритмом логарифмического времени и принадлежит к классу роста O(logn).
Для этого упражнения вам нужно будет написать реализацию интерфейса Map с помощью двоичного дерева поиска.
Вот начало реализации, называемой MyTreeMap:
public class MyTreeMap<K, V> implements Map<K, V> {
private int size = 0;
private Node root = null;
Переменные экземпляра — это size, который отслеживает количество ключей, и root, который является ссылкой на корневой узел дерева. Когда дерево пусто, root равен null, а size равен 0.
Здесь определяется класс Node, который находится внутри MyTreeMap.
protected class Node {
public K key;
public V value;
public Node left = null;
public Node right = null;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
Каждый узел содержит пару ключ-значение, а также ссылки на два дочерних узла, left и right. Любой дочерний узел может быть нулевым.
Некоторые методы Map легко реализовать, например, size и clear:
public int size() {
return size;
}
public void clear() {
size = 0;
root = null;
}
Очевидно, что size имеет постоянное время.
clear также имеет постоянное время, но учтите следующее: когда root присваивается значение null, сборщик мусора освобождает узлы дерева, что занимает линейное время. Должна ли эта работа выполняться сборщиком мусора? Я думаю, да.
В следующем разделе вы заполните некоторые другие методы, включая наиболее важные get и set.
В репозитории этой книги вы найдёте следующие исходные файлы:
Запустите ant build для компиляции исходных файлов. Затем запустите ant MyTreeMapTest. Несколько тестов должны завершиться неудачно, потому что вам предстоит проделать некоторую работу!
Я уже предоставил наброски для get и containsKey. Они оба используют findNode, который я определил как частный метод; он не является частью интерфейса Map. Вот его начало:
private Node findNode(Object target) {
if (target == null) {
throw new IllegalArgumentException();
}
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) target;
// TODO: FILL THIS IN!
return null;
}
Параметр target — это ключ, который мы ищем. Если target равен null, findNode генерирует исключение. Некоторые реализации Map могут обрабатывать null как ключ, но в двоичном дереве поиска нам нужно иметь возможность сравнивать ключи, поэтому обработка null проблематична. Чтобы упростить задачу, эта реализация не рассматривает null как ключ.
Следующая строка показывает, как сравнить target с ключами в дереве. Согласно сигнатурам get и containsKey (имя и параметры), компилятор считает target объектом Object. Однако нам нужно сравнить его с типом K (или любым суперклассом), поэтому мы приводим target к Comparable<? super K>, что означает, что он может сравниваться с экземпляром типа K (или любого суперкласса). Если вы не знакомы с использованием «универсальных шаблонов», вы можете прочитать больше на странице http://thinkdast.com/gentut. Перевод текста на русский язык:
В данном задании основное внимание уделяется не обработке системы типов. Ваша задача — написать оставшуюся часть findNode. Если он находит узел, содержащий ключ target, он должен вернуть этот узел. В противном случае он должен возвращать null. Когда вы заставите его работать, тесты get и containsKey должны пройти успешно.
Обратите внимание, что ваше решение должно искать только по одному пути дерева, поэтому оно должно быть пропорционально высоте дерева. Вы не должны искать всё дерево!
Ваша следующая задача — заполнить containsValue. Чтобы помочь вам начать, я предоставляю вспомогательный метод equals, который сравнивает target с заданным ключом. Обратите внимание, что значения в дереве (в отличие от ключей) не обязательно сопоставимы, поэтому мы не можем использовать compareTo; мы должны вызывать equals для target.
В отличие от вашего предыдущего решения findNode, ваше решение containsValue должно искать всё дерево, поэтому время его выполнения пропорционально количеству ключей n, а не высоте дерева h.
Примечание переводчика: здесь вы можете использовать ранее упомянутый итератор DFS.
Следующий метод, который вы должны заполнить, — это put. Я предоставляю начальный код для обработки простых случаев:
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);
}
private V putHelper(Node node, K key, V value) {
// TODO: Заполните это.
}
Если вы попытаетесь использовать null в качестве ключевого слова, put вызовет исключение.
Если дерево пусто, то put создаст новый узел и инициализирует переменную экземпляра root.
Иначе он вызывает putHelper, это частный метод, определённый мной; он не является частью интерфейса Map.
Заполните putHelper, чтобы он искал дерево и:
null.Ваше put решение должно иметь время выполнения, пропорциональное высоте дерева h, а не количеству элементов n. В идеале вы должны выполнить поиск по дереву только один раз, но если вы обнаружите, что два поиска проще, вы можете это сделать: это будет немного медленнее, но не изменит уровень роста.
Наконец, вы должны заполнить keySet. Согласно документации http://thinkdast.com/mapkeyset, этот метод должен возвращать набор, который можно перебирать по порядку; то есть, следуя методу compareTo, выполнять итерацию в порядке возрастания. Реализация HashSet, которую мы использовали в разделе 8.3, не поддерживает порядок ключей, но реализация LinkedHashSet может. Вы можете прочитать http://thinkdast.com/linkedhashset.
Я предоставляю план keySet, создающий и возвращающий LinkedHashSet:
public Set<K> keySet() {
Set<K> set = new LinkedHashSet<K>();
return set;
}
Вы должны завершить этот метод, чтобы он добавлял ключи из дерева в set в порядке возрастания. Подсказка: вы, возможно, захотите написать вспомогательную программу; вы, возможно, захотите сделать её рекурсивной; вы также можете захотеть прочитать о обходе дерева в среднем порядке на http://thinkdast.com/inorder.
Когда вы закончите, все тесты должны пройти. В следующей главе я объясню своё решение и протестирую производительность основных методов.
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )