Миронов А. А. - Информатика - Бинарные и красно-черные деревья
HTML-код
- Опубликовано: 18 окт 2024
- 0:00:09 1. Вопрос: Как по номеру элемента добыть элемент, например, в дереве?
0:04:44 2. Примеры бинарных деревьев. Построение бинарного дерева поиска, элементами которого будут слова
0:16:22 3. Ввод операции вращения
0:26:01 4. Красно-черное дерево
0:54:44 5. Добавление элемента в красно-черное дерево
Случайно наткнулся на это видео при изучении красно-черных деревьев. Как будто в универ вернулся, приятно было послушать и очень понятно)
Преподаватель от Бога!!)) Отлично вовлекает, удерживает внимание, практично и заставляет думатьб а не "переписывать" числа
Если ваш вопрос: Как добавляются элементы в кч-дерево, то вам сюда -> 1:11:34
Коллизией, преподаватель называет ситуацию, когда подряд идут два красных элемента.
Я еще хотел узнать механизм балансировки кч-дерева, но преподаватель на видео объясняет, что для решения этой задачи, рассматривается 8 частных случаем и разбирать все достаточно трудно и скучно. Придется искать на других ресурсах.
В целом лекция достаточно информативна и лично для меня была полезна, спасибо.
если дерево BST, то симметричным обходом можно легко получить любой элемент по индексу.. за N.
если дерево законченное, то пожалуйста, обход в ширину, храните само дерево в массиве.. по индексу можно получить нужный элемент.
ну и другими обходами также можно индексировать.. тут только смысл индекса меняется.
Хорошо преподнесена информация, но во второй половине видео, на примерах, преподаватель запутался. Рекомендую к просмотру
Почему огурец больше картошки, но икс больше игрека? 0_о
Вообще-то индексировать можно. Для этого существуют бинарные деревья по неявному ключу.
В кратце, допустим мы хотим найти в поддереве элемент с номером n, тогда если размер левого поддрева меньше или равен n, то наш элемент точно находится в левом поддереве, если размер левого поддрева плюс 1 равен n, то мы нашли искомый элемент, иначе искомый элемент находится в правом поддреве с индексом n - (размер левого поддрева) - 1.