Слайд 2
![Проблема поиска значений Коллекции (вроде массивов и списков) позволяют хранить](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-1.jpg)
Проблема поиска значений
Коллекции (вроде массивов и списков) позволяют хранить данные, а
также добавлять новые, удалять более ненужные, или редактировать уже существующие элементы. Однако, кроме всего этого, часто необходимо найти определённое значение в коллекции – и делается это, например, при помощи линейного либо бинарного поиска.
Слайд 3
![Проблема поиска значений Линейный поиск (как по массиву, так и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-2.jpg)
Проблема поиска значений
Линейный поиск (как по массиву, так и по списку)
может занять слишком много времени, в том случае если количество элементов в коллекции велико. Бинарный поиск требует, чтобы элементы коллекции были отсортированы, а определение медианы в списке – это явно не самый эффективный алгоритм...
Слайд 4
![Решение проблемы поиска Если данных достаточно много, и приоритетной задачей](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-3.jpg)
Решение проблемы поиска
Если данных достаточно много, и приоритетной задачей является поиск
значений, тогда динамической структурой для хранения этих данных следует избрать дерево. Кроме того, почти так же, как и в списках, в деревьях эффективно реализуются добавление и удаление элементов.
Слайд 5
![Строим дерево!](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-4.jpg)
Слайд 6
![Определение понятия Дерево – это нелинейная структурированная совокупность элементов. Элементы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-5.jpg)
Определение понятия
Дерево – это нелинейная структурированная совокупность элементов. Элементы данных в
общем случае называются узлами (node).
Слайд 7
![Виды деревьев Сбалансированные деревья K-мерные деревья R-дерево Кучи Изящный граф-звезда](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-6.jpg)
Виды деревьев
Сбалансированные деревья
K-мерные деревья
R-дерево
Кучи
Изящный граф-звезда
Двоичное (бинарное) дерево
Красно-чёрное дерево
Октодерево
Танцующее дерево и др.
Слайд 8
![Схематичное изображение https://habrahabr.ru/post/65617/](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-7.jpg)
Схематичное изображение
https://habrahabr.ru/post/65617/
Слайд 9
![Бинарное дерево Бинарное дерево – это частный случай дерева, в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-8.jpg)
Бинарное дерево
Бинарное дерево – это частный случай дерева, в котором каждый
узел имеет не более двух потомков (т.е. каждый узел может иметь 2, 1 или 0 потомков).
Узел, не имеющий потомков, называется листом (leaf).
Узел является родительским для своих потомков и дочерним для своего предка.
Слайд 10
![Бинарное дерево Левый потомок - дочерний узел слева от текущего](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-9.jpg)
Бинарное дерево
Левый потомок - дочерний узел слева от текущего узла.
Правый
потомок - дочерний узел справа от текущего узла.
Корень – это основной узел (добавляется в дерево первым), не имеющий родителя.
Каждый узел состоит из четырех частей:
Значение.
Указатель на родителя.
Указатель на левого потомка.
Указатель на правого потомка.
Слайд 11
![Строение одного узла дерева](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-10.jpg)
Строение одного узла дерева
Слайд 12
![Главный принцип Самый главный принцип бинарного дерева заключается в том,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-11.jpg)
Главный принцип
Самый главный принцип бинарного дерева заключается в том, что для
каждого узла выполняется правило: в левой ветке содержатся только те ключи, которые имеют значения, меньшие, чем значение данного узла. В правой же ветке содержатся ключи, имеющие значения, большие, чем значение данного узла.
Слайд 13
![Рекурсия передаёт привет ☺ Бинарное дерево является рекурсивной структурой, поскольку](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-12.jpg)
Рекурсия передаёт привет ☺
Бинарное дерево является рекурсивной структурой, поскольку каждое его
поддерево само по себе является бинарным деревом, и, следовательно, каждый его узел в свою очередь является корнем самостоятельного дерева. Поэтому, при работе с деревьями обычно используются рекурсивные алгоритмы.
Слайд 14
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-13.jpg)
Слайд 15
![Основные операции Поиск элемента Добавление элемента Распечатка данных Изменение значения](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-14.jpg)
Основные операции
Поиск элемента
Добавление элемента
Распечатка данных
Изменение значения элемента
Удаление элемента
Подсчёт количества элементов
Очистка дерева
Слайд 16
![Класс элемента дерева class Node { // inner class! private](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-15.jpg)
Класс элемента дерева
class Node { // inner class!
private int
value;
private Node parent;
private Node right;
private Node left;
public int getValue() {
return value;
}
}
Слайд 17
![Распечатка дерева private void showTree(Node elem) { if (elem !=](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-16.jpg)
Распечатка дерева
private void showTree(Node elem) {
if (elem != null)
{
showTree(elem.left);
System.out.print(elem.getValue());
showTree(elem.right);
}
}
Слайд 18
![Подсчёт количества элементов private int getCount(Node elem, int count) {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-17.jpg)
Подсчёт количества элементов
private int getCount(Node elem, int count) {
if (elem
!= null) {
count = getCount(elem.left, count);
count++;
count = getCount(elem.right, count);
}
return count;
}
Слайд 19
![Ключ – значение На практике, элементы деревьев чаще всего хранят](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/275913/slide-18.jpg)
Ключ – значение
На практике, элементы деревьев чаще всего хранят не просто
одно лишь значение, а пару «ключ - значение». В качестве ключа обычно выступает целое число или строка, в то время как значением может быть список, любая другая коллекция, или объект пользовательского типа.