wiki Binary_search_tree

https://en.wikipedia.org/wiki/Binary_search_tree

related repo https://github.com/learn-co-students/cs-maps-tree-map-lab-g-416

cs-maps-дерево-карта-лаборатория Цели обучения Реализуйте Mapинтерфейс, используя двоичное дерево поиска. Анализируйте производительность древовидной карты. Обзор На этом этапе вы должны быть знакомы с Mapинтерфейсом и HashMapреализацией Java. А создав свою собственную Mapтаблицу с использованием хеш-таблицы, вы должны понять, как HashMapона работает и почему мы ожидаем, что ее основные методы будут работать с постоянным временем.

Благодаря такой производительности HashMapон широко используется, но это не единственная реализация Map. Есть две причины, по которым вам может понадобиться другая реализация:

Хеширование может быть медленным, поэтому, хотя HashMapоперации выполняются с постоянным временем, «константа» может быть большой.

Ключи в хеш-таблице не хранятся в каком-то определенном порядке; на самом деле порядок может измениться при росте таблицы и перехешировании ключей. Для некоторых приложений необходимо или, по крайней мере, полезно содержать клавиши в порядке.

Оказывается, сложно решить обе эти проблемы одновременно, но Java предоставляет реализацию, которая TreeMapочень близка к этому:

Порядок роста не так хорош. Вместо постоянного времени a TreeMapзанимает время, пропорциональное log n.

Внутри TreeMapключи хранятся не по порядку; они хранятся в двоичном дереве поиска , что позволяет просматривать ключи по порядку за линейное время.

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

Бинарное дерево поиска Бинарное дерево поиска (BST) — это дерево, в котором каждый узел содержит ключ, и каждый nodeимеет «свойство BST»:

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

альтернативный тег

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

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

Поиск ключа в двоичном дереве поиска выполняется быстро, поскольку нам не нужно искать по всему дереву. Начиная с корня, мы можем использовать следующий алгоритм:

Сравните ключ, который вы ищете target, с ключом в текущем узле. Если они равны, все готово.

Если targetменьше текущего ключа, выполните поиск в левом дереве. Если его нет, значит, targetего нет в дереве.

Если targetбольше текущего ключа, выполните поиск в правильном дереве. Если его нет, значит, targetего нет в дереве.

На каждом уровне дерева вам нужно искать только одного дочернего элемента. Например, если вы ищете target = 4на предыдущей диаграмме, вы начинаете с корня, который содержит ключ 8. Поскольку targetменьше 8, идите налево. Потому что targetбольше, чем 3ты идешь направо. Поскольку targetменьше 6, идите налево. И тогда вы найдете ключ, который ищете.

В этом примере для поиска цели требуются 4сравнения, хотя дерево содержит 9 ключей. В общем, количество сравнений пропорционально высоте дерева, а не количеству ключей в дереве.

Итак, что мы можем сказать о взаимосвязи между высотой дерева hи количеством узлов n? Начинаем с малого и развиваемся:

Если h=1, дерево содержит только один узел, поэтому n=1.

Если h=2, мы можем добавить еще два узла, всего n=3.

Если h=3, мы можем добавить 4еще узлы, в общей сложности n=7.

Если h=4, мы можем добавить 8еще узлы, в общей сложности n=15.

К настоящему времени вы, возможно, увидите закономерность. Если пронумеровать дерево уровней от 1до h, уровень с индексом iможет иметь до 2 узлов i-1 . А общее количество узлов на hуровнях равно 2 ч -1. Если мы имеем

п = 2 ч - 1

Мы можем взять лог базы 2 обеих сторон:

журнал 2 ≈ час

Это означает, что высота дерева пропорциональна log n, если дерево заполнено; то есть, если каждый уровень содержит максимальное количество узлов.

Поэтому мы ожидаем, что сможем найти ключ в двоичном дереве поиска за время, пропорциональное log n. Это верно, если дерево заполнено, и даже если дерево заполнено лишь частично. Но это не всегда так, как мы увидим.

Алгоритм, требующий времени, пропорционального, log nназывается «логарифмическим» или «логарифмическим временем» и принадлежит порядку роста O( log n).

Реализация древовидной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. Один или оба дочерних узла могут быть null.

Некоторые методы Mapлегко реализовать, например sizeи clear:

public int size() {
	return size;
}

public void clear() {
	size = 0;
	root = null;
}

sizeочевидно, постоянное время.

clearкажется, что это постоянное время, но учтите следующее: когда rootустановлено значение null, сборщик мусора освобождает узлы в дереве, что занимает линейное время. Должна ли учитываться работа, проделанная сборщиком мусора? Мы так думаем.

В следующем разделе вы укажете некоторые другие методы, в том числе наиболее важные, getи put.

инструкции При проверке репозитория для этой лабораторной работы вы должны обнаружить файловую структуру, аналогичную той, которую вы видели в предыдущих лабораторных работах. Каталог верхнего уровня содержит CONTRIBUTING.md, LICENSE.md, README.md, а каталог с кодом этой лабораторной работы javacs-lab09.

В подкаталоге javacs-lab09/src/com/flatironschool/javacsвы найдете следующие исходные файлы:

MyTreeMap.javaсодержит код из предыдущего раздела с описанием отсутствующих методов.

MyTreeMapTest.javaсодержит модульные тесты для MyTreeMap.

Кроме того, в папке javacs-lab09вы найдете файл сборки Ant build.xml.

В javacs-lab09запустите ant buildдля компиляции исходных файлов. Затем запустите ant test, который запускается MyTreeMapTest. Несколько тестов должны провалиться, потому что вам есть над чем поработать!

Мы предоставили схемы для getи containsKey. Оба они используют findNode, который мы определили как частный метод; это не часть интерфейса Map. Вот как это начинается:

private Node findNode(Object target) {
	if (target == null) {
		throw new NullPointerException();
	}

	@SuppressWarnings("unchecked")
	Comparable<? super K> k = (Comparable<? super K>) target;
	int cmp = k.compareTo(p.key);
	// TODO: Fill this in.
	return null;
}

Параметр target— это ключ, который мы ищем. Если targetесть null, findNodeвыдает исключение. Некоторые реализации Mapмогут работать nullкак ключ, но в двоичном дереве поиска нам нужна возможность сравнивать ключи, поэтому работа с ними nullпроблематична. Для простоты мы решили, что наша реализация не должна разрешать nullиспользование ключа.

Следующие строки показывают, как мы можем сравнить targetключ в дереве. Судя по сигнатуре getи containsKeyкомпилятор считает, targetчто это файл Object. Но нам нужна возможность сравнивать ключи, поэтому мы приводим тип targetк Comparable<? super K>, что означает, что он сравним с экземпляром type Kили любым суперклассом K. Если вы не знакомы с таким использованием «подстановочных знаков типов», вы можете прочитать больше здесь .

К счастью, работа с системой типов Java не является целью этого упражнения. Ваша задача — заполнить оставшуюся часть findNode. Если он находит узел, содержащий targetключ, он должен вернуть этот узел. В противном случае он должен вернуться null. Когда все заработает, тесты на getи containsKeyдолжны пройти.

Обратите внимание, что ваше решение должно искать только один путь в дереве, поэтому это должно занять время, пропорциональное высоте дерева. Не стоит обыскивать все дерево!

Ваша следующая задача — заполнить containsValue. Чтобы вы могли начать, мы предоставили вспомогательный метод , equalsкоторый сравнивает targetзаданный ключ. Обратите внимание, что значения в дереве (в отличие от ключей) не обязательно сопоставимы, поэтому мы не можем использовать compareTo; мы должны equalsвызвать target. В отличие от вашего предыдущего решения для findNode, ваше решение для containsValue должно выполнять поиск по всему дереву, поэтому время его выполнения будет пропорционально количеству ключей, nа не высоте дерева h.

Следующий метод, который вам следует заполнить, — это put. Мы предоставили стартовый код, который обрабатывает простые случаи: public V put(K key, V value) { if (key == null) { throw new NullPointerException(); } 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: Fill this in.
}

Если вы попытаетесь поставить nullключ, putвыдаст исключение.

Если дерево пусто, putсоздается новый узел и инициализируется переменная экземпляра root.

В противном случае он вызывает putHelper, который является определенным нами закрытым методом; это не часть интерфейса Map.

Заполните putHelper, чтобы он искал дерево и:

Если keyоно уже есть в дереве, оно заменяет старое значение новым и возвращает старое значение.

Если keyего нет в дереве, он создает новый узел, находит подходящее место для его добавления и возвращает null.

Ваша реализация putдолжна занять время, пропорциональное h, а не n. В идеале вам следует обыскивать дерево только один раз, но если вам легче обыскивать дважды, вы можете сделать это; он будет медленнее, но это не меняет порядок роста.

Наконец, вам следует заполнить тело файла keySet. Согласно документации , этот метод должен возвращать что-то такое Set, что перебирает ключи по порядку; то есть в порядке возрастания согласно compareToметоду. Есть несколько способов сделать это, но самый простой — вернуть реализацию, Setподдерживающую порядок элементов. Наиболее часто используемые реализации, такие как HashSet, не имеют этого свойства, но Java предоставляет такую, которая имеет: LinkedHashSet. Мы предоставляем описание того, keySetчто создает и возвращает LinkedHashSet:

public Set<K> keySet() {
	Set<K> set = new LinkedHashSet<K>();
	return set;
}

Вам следует завершить этот метод, чтобы он добавлял ключи из дерева в setпорядке возрастания. Подсказка: возможно, вы захотите написать вспомогательный метод, сделать его рекурсивным и прочитать об обходе дерева по порядку .

Когда вы закончите, все тесты должны пройти. В следующем README мы рассмотрим наши решения и проверим производительность основных методов.

Ресурсы Бинарное дерево поиска : Википедия.

Подстановочные знаки ввода : учебник по Java.

Обход дерева : Википедия.

Просмотрите Карты: Tree Map Lab на Learn.co и начните учиться программировать бесплатно.

О Нет описания, веб-сайта или тем. Ресурсы Прочти меня Лицензия Посмотреть лицензию Активность Пользовательские свойства Звезды 0 звезд Наблюдатели 16 смотрю Вилки 1 вилка Репозиторий отчетов Релизы Ни одного релиза не опубликовано Пакеты Пакеты не опубликованы Авторы 4 @АлленДауни АлленДауни Аллен Дауни @ЭннДжон ЭннДжон @pletcher Плетчер Чарльз Плетчер @аарон-альфонс Аарон-Альфонс Аарон Альфонс Языки Джава 100,0% Нижний колонтитул