🗊Презентация Binary Tree. Проблема поиска значений

Категория: Информатика
Нажмите для полного просмотра!
Binary Tree. Проблема поиска значений, слайд №1Binary Tree. Проблема поиска значений, слайд №2Binary Tree. Проблема поиска значений, слайд №3Binary Tree. Проблема поиска значений, слайд №4Binary Tree. Проблема поиска значений, слайд №5Binary Tree. Проблема поиска значений, слайд №6Binary Tree. Проблема поиска значений, слайд №7Binary Tree. Проблема поиска значений, слайд №8Binary Tree. Проблема поиска значений, слайд №9Binary Tree. Проблема поиска значений, слайд №10Binary Tree. Проблема поиска значений, слайд №11Binary Tree. Проблема поиска значений, слайд №12Binary Tree. Проблема поиска значений, слайд №13Binary Tree. Проблема поиска значений, слайд №14Binary Tree. Проблема поиска значений, слайд №15Binary Tree. Проблема поиска значений, слайд №16Binary Tree. Проблема поиска значений, слайд №17Binary Tree. Проблема поиска значений, слайд №18Binary Tree. Проблема поиска значений, слайд №19Binary Tree. Проблема поиска значений, слайд №20
Скачать
Вы можете ознакомиться и скачать презентацию на тему Binary Tree. Проблема поиска значений. Доклад-сообщение содержит 20 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Binary Tree
Описание слайда:
Binary Tree

Слайд 2


Проблема поиска значений Коллекции (вроде массивов и списков) позволяют хранить данные, а также добавлять новые, удалять более ненужные, или редактировать уже существующие элементы. Однако, кроме всего этого, часто необходимо найти определённое значение в коллекции – и делается это, например, при помощи линейного либо бинарного поиска.
Описание слайда:
Проблема поиска значений Коллекции (вроде массивов и списков) позволяют хранить данные, а также добавлять новые, удалять более ненужные, или редактировать уже существующие элементы. Однако, кроме всего этого, часто необходимо найти определённое значение в коллекции – и делается это, например, при помощи линейного либо бинарного поиска.

Слайд 3


Проблема поиска значений Линейный поиск (как по массиву, так и по списку) может занять слишком много времени, в том случае если количество элементов в коллекции велико. Бинарный поиск требует, чтобы элементы коллекции были отсортированы, а определение медианы в списке – это явно не самый эффективный алгоритм...
Описание слайда:
Проблема поиска значений Линейный поиск (как по массиву, так и по списку) может занять слишком много времени, в том случае если количество элементов в коллекции велико. Бинарный поиск требует, чтобы элементы коллекции были отсортированы, а определение медианы в списке – это явно не самый эффективный алгоритм...

Слайд 4


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

Слайд 5


Строим дерево!
Описание слайда:
Строим дерево!

Слайд 6


Определение понятия Дерево – это нелинейная структурированная совокупность элементов. Элементы данных в общем случае называются узлами (node).
Описание слайда:
Определение понятия Дерево – это нелинейная структурированная совокупность элементов. Элементы данных в общем случае называются узлами (node).

Слайд 7


Виды деревьев Сбалансированные деревья K-мерные деревья R-дерево Кучи Изящный граф-звезда Двоичное (бинарное) дерево Красно-чёрное дерево Октодерево Танцующее дерево и др.
Описание слайда:
Виды деревьев Сбалансированные деревья K-мерные деревья R-дерево Кучи Изящный граф-звезда Двоичное (бинарное) дерево Красно-чёрное дерево Октодерево Танцующее дерево и др.

Слайд 8


Схематичное изображение
Описание слайда:
Схематичное изображение

Слайд 9


Бинарное дерево Бинарное дерево – это частный случай дерева, в котором каждый узел имеет не более двух потомков (т.е. каждый узел может иметь 2, 1 или 0 потомков). Узел, не имеющий потомков, называется листом (leaf). Узел является родительским для своих потомков и дочерним для своего предка.
Описание слайда:
Бинарное дерево Бинарное дерево – это частный случай дерева, в котором каждый узел имеет не более двух потомков (т.е. каждый узел может иметь 2, 1 или 0 потомков). Узел, не имеющий потомков, называется листом (leaf). Узел является родительским для своих потомков и дочерним для своего предка.

Слайд 10


Бинарное дерево Левый потомок - дочерний узел слева от текущего узла. Правый потомок - дочерний узел справа от текущего узла. Корень – это основной узел (добавляется в дерево первым), не имеющий родителя. Каждый узел состоит из четырех частей: Значение. Указатель на родителя. Указатель на левого потомка. Указатель на правого потомка.
Описание слайда:
Бинарное дерево Левый потомок - дочерний узел слева от текущего узла. Правый потомок - дочерний узел справа от текущего узла. Корень – это основной узел (добавляется в дерево первым), не имеющий родителя. Каждый узел состоит из четырех частей: Значение. Указатель на родителя. Указатель на левого потомка. Указатель на правого потомка.

Слайд 11


Строение одного узла дерева
Описание слайда:
Строение одного узла дерева

Слайд 12


Главный принцип Самый главный принцип бинарного дерева заключается в том, что для каждого узла выполняется правило: в левой ветке содержатся только те ключи, которые имеют значения, меньшие, чем значение данного узла. В правой же ветке содержатся ключи, имеющие значения, большие, чем значение данного узла.
Описание слайда:
Главный принцип Самый главный принцип бинарного дерева заключается в том, что для каждого узла выполняется правило: в левой ветке содержатся только те ключи, которые имеют значения, меньшие, чем значение данного узла. В правой же ветке содержатся ключи, имеющие значения, большие, чем значение данного узла.

Слайд 13


Рекурсия передаёт привет  Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само по себе является бинарным деревом, и, следовательно, каждый его узел в свою очередь является корнем самостоятельного дерева. Поэтому, при работе с деревьями обычно используются рекурсивные алгоритмы.
Описание слайда:
Рекурсия передаёт привет  Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само по себе является бинарным деревом, и, следовательно, каждый его узел в свою очередь является корнем самостоятельного дерева. Поэтому, при работе с деревьями обычно используются рекурсивные алгоритмы.

Слайд 14


Binary Tree. Проблема поиска значений, слайд №14
Описание слайда:

Слайд 15


Основные операции Поиск элемента Добавление элемента Распечатка данных Изменение значения элемента Удаление элемента Подсчёт количества элементов Очистка дерева
Описание слайда:
Основные операции Поиск элемента Добавление элемента Распечатка данных Изменение значения элемента Удаление элемента Подсчёт количества элементов Очистка дерева

Слайд 16


Класс элемента дерева class Node { // inner class! private int value; private Node parent; private Node right; private Node left; public int getValue() { return value; } }
Описание слайда:
Класс элемента дерева 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 != null) { showTree(elem.left); System.out.print(elem.getValue()); showTree(elem.right); } }
Описание слайда:
Распечатка дерева 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) { if (elem != null) { count = getCount(elem.left, count); count++; count = getCount(elem.right, count); } return count; }
Описание слайда:
Подсчёт количества элементов private int getCount(Node elem, int count) { if (elem != null) { count = getCount(elem.left, count); count++; count = getCount(elem.right, count); } return count; }

Слайд 19


Ключ – значение На практике, элементы деревьев чаще всего хранят не просто одно лишь значение, а пару «ключ - значение». В качестве ключа обычно выступает целое число или строка, в то время как значением может быть список, любая другая коллекция, или объект пользовательского типа.
Описание слайда:
Ключ – значение На практике, элементы деревьев чаще всего хранят не просто одно лишь значение, а пару «ключ - значение». В качестве ключа обычно выступает целое число или строка, в то время как значением может быть список, любая другая коллекция, или объект пользовательского типа.

Слайд 20


Реализация бинарного дерева Пример кода: https://git.io/vwsyd Реализации сбалансированных деревьев: http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BTree.java.html https://github.com/JPWKU/BTree/blob/master/BTree.java http://www.jbixbe.com/doc/tutorial/BTree.html
Описание слайда:
Реализация бинарного дерева Пример кода: https://git.io/vwsyd Реализации сбалансированных деревьев: http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BTree.java.html https://github.com/JPWKU/BTree/blob/master/BTree.java http://www.jbixbe.com/doc/tutorial/BTree.html

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию