Информатика, 4 классДерево4 минуты чтения
Дерево
Дерево в информатике похоже на настоящее, только перевёрнутое. Корень наверху, ветви расходятся вниз, на концах листья.
4классКорень, ветви, листья
Корень это начало. Он один.
От корня отходят ветви, от них ветви поменьше. Каждая растёт из одной единственной.
Концы, из которых ничего не растёт, называют листьями. Дальше пути нет.
Дерево целиком
- Диск
- Школа
- Математика
- Домашка.txt
- Контрольная.txt
- Чтение
- Дневник.txt
- Фото
- Лето.jpg
Части дерева
- Кореньначало, он один
- Ветвьпуть от одной точки к следующей
- Узелместо, где путь ветвится
- Листконец пути
Дерево выбора
Каждый выбор рождает ветви. Пошёл направо, пошёл налево.
Из каждого нового места снова есть выбор. Дерево растёт вниз и вширь.
По такому дереву видно все возможные исходы. Ни один не потеряется.
Что надеть утром
Смотрю в окно
- Идёт дождь?
даНадень дождевик
нетНадень куртку
- На улице холодно?
даВозьми шапку
нетИди с непокрытой головой
Одет по погоде
Сколько путей
Если на каждом шаге два выбора, число путей удваивается. Один шаг это два пути, два шага уже четыре.
Три шага дают восемь, четыре шестнадцать. Растёт быстро.
Поэтому длинные деревья рисуют редко. Считают числом.
Сколько путей после каждого выбора
путей
Семейное дерево
Родословную рисуют деревом. Наверху предок, ниже дети, внуки, правнуки.
По нему видно, кто кому кем приходится. Родство читается по ветвям.
Такое дерево иногда рисуют наоборот, корнем вниз. Смысл не меняется.
Дерево папок
Папки на компьютере тоже дерево. Корень это диск, ветви это папки, листья это файлы.
Путь к файлу и есть дорога от корня до листа. Она одна и другой не бывает.
Это свойство деревьев делает их удобными. Заблудиться негде.
От корня до листа дорога одна
Диск/Школа/Математика/Домашка.txt
- Диск
- Школа
- Математика
- Домашка.txt
- Чтение
- Фото
- Лето.jpg
Глубина и ширина
У дерева есть два размера. Глубина это длина самого длинного пути от корня до листа, а ширина это число листьев.
Глубокое дерево с одним листом на каждом уровне похоже на цепочку. Широкое и мелкое похоже на веник: корень и сразу сотня листьев.
Хорошее дерево обычно посередине. По нему быстро идти вниз, и на каждом уровне выбор невелик.
Поиск по дереву
Дерево тем и ценно, что поиск в нём короткий. Спускаясь на уровень, ты отсекаешь целую ветку и больше к ней не возвращаешься.
Так устроен определитель растений: два вопроса, и половина видов отпала. Так же ищут файл в дереве папок.
Каждый шаг вниз это отброшенная половина. Поэтому даже в огромном дереве путь короткий.
Дерево турнира
Турнирная сетка это тоже дерево, только перевёрнутое ещё раз: листья внизу это команды, а корень наверху это победитель.
Каждая игра соединяет две ветки в одну, и с каждым кругом число участников уменьшается вдвое. Поэтому шестнадцать команд определяют чемпиона всего за четыре круга.
Турнирная сетка четырёх команд
Путь: Барсы → Финал → Чемпион
Где ещё встречаются деревья
Деревом устроено оглавление книги. Разделы, главы, параграфы.
Деревом рисуют разбор слова по составу и разбор предложения.
Про пути и связи без корня читай урок «Граф». Про папки есть урок «Папки».
Проверь себя: В дереве три уровня выбора, на каждом по два пути. Сколько всего разных исходов?
Восемь. Каждый новый выбор удваивает число путей: 2, потом 4, потом 8.
Короткие ответы
- Почему дерево рисуют корнем вверх?
- Так удобнее читать сверху вниз, как обычный текст. В информатике это стало привычкой.
- Может ли у ветки быть два корня?
- В дереве нет. Каждая ветка растёт ровно из одной. Если корней два, это уже не дерево, а граф.