ВИДЕОУРОК №5. Бинарное дерево поиска. АВЛ-дерево.
Основная цель этого урока – ознакомить студентов со структурами данных и понятием алгоритма. Рассмотрим асимптотическую сложность алгоритма, односвязные и двухсвязные связанные списки. Также научимся использовать О-нотации.
На занятии рассматриваются главные структуры данных. Объясняется политика роста динамического массива. Разберем главные методы работы с этими структурами данных и их реализацию, объединение, сечение, разность, симметричную разность двух множеств.
На занятии разъясняются главные виды сортировки данных. Демонстрируется их сущность и реализация. Сравниваются разные методы сортировки для разных назначений и предпосылок. Кратко объясняется суть новой сортировки Timsort.
На уроке рассматриваются две структуры данных: хэш-таблица и дерево. Разъясняется суть хэш-таблицы, принцип ее работы, хэш-функция и коллизии в хэш-таблицах. Рассматривается структура данных "Дерево", подробнее объясняется бинарное дерево поиска и добавление узлов в дерево.
Данный урок посвящен рассмотрению методов работы с бинарным деревом поиска: удаление узла из дерева (3 варианта удаления), поиск узла в дереве, прямой, обратный и симметричный обход дерева. Рассматривается сущность АВЛ-дерева как модернизация бинарного дерева поиска. Разъясняется суть балансировки АВЛ-дерева и способы реализации балансировки.
На уроке рассматривается популярная и сложная структура данных "Граф". Также поговорим о введении в теорию графов, способах задать граф и два варианта поиска по графу: в ширину и глубину.