Відмінності між версіями «Дерево»!!!
111 (обговорення • внесок) |
111 (обговорення • внесок) |
||
| (не показані 3 проміжні версії цього учасника) | |||
| Рядок 14: | Рядок 14: | ||
[[Файл:tree.png]] | [[Файл:tree.png]] | ||
| + | |||
| + | |||
| + | |||
A - корінь дерева | A - корінь дерева | ||
| + | |||
В - корінь лівого піддерева | В - корінь лівого піддерева | ||
| − | + | ||
| + | C - корінь правого піддерева | ||
| + | |||
Корінь дерева розташований на рівні з мінімальним значенням. | Корінь дерева розташований на рівні з мінімальним значенням. | ||
| Рядок 38: | Рядок 44: | ||
Якщо розглядати завдання як єдиний послідовний процес, то окремі вузли відвідуються в певному порядку і можуть вважатися розташованими лінійно. | Якщо розглядати завдання як єдиний послідовний процес, то окремі вузли відвідуються в певному порядку і можуть вважатися розташованими лінійно. | ||
| + | |||
| + | == Посилання == | ||
| + | |||
| + | [https://prog-cpp.ru/data-tree/ TreeMap] | ||
| + | |||
| + | [https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85) Wikipedia ] | ||
Поточна версія на 18:27, 18 лютого 2018
Дерево данних
Дерево - одна з найбільш широко поширених структур даних в інформатиці, емулююча деревоподібну структуру у вигляді набору пов'язаних вузлів. Є зв'язковим графом, що не містить цикли. Більшість джерел також додають умова на те, що ребра графа не повинні бути орієнтованими. На додаток до цих трьох обмеженням, в деяких джерелах вказується, що ребра графа не повинні бути зваженими.
Структура
Дерево - структура даних, що представляє собою деревоподібну структуру у вигляді набору пов'язаних вузлів.
Бінарне дерево - це кінцеве безліч елементів, яке або порожня, або містить елемент (корінь), пов'язаний з двома різними бінарними деревами, званими лівим і правим піддеревами. Кожен елемент бінарного дерева називається вузлом. Зв'язки між вузлами дерева називаються його гілками.
Спосіб подання бінарного дерева:
A - корінь дерева
В - корінь лівого піддерева
C - корінь правого піддерева
Корінь дерева розташований на рівні з мінімальним значенням.
Вузол D, який знаходиться безпосередньо під вузлом B, називається нащадком B. Якщо D знаходиться на рівні i, то B - на рівні i-1. Вузол B називається предком D.
Максимальний рівень будь-якого елементу дерева називається його глибиною або висотою.
Якщо елемент не має нащадків, він називається листом або термінальним вузлом дерева.
Інші елементи - внутрішні вузли (вузли розгалуження).
Число нащадків внутрішнього вузла називається його ступенем. Максимальний ступінь всіх вузлів є ступінь дерева.
Число гілок, яке потрібно пройти від кореня до вузла x, називається довжиною шляху до x. Корінь має довжину шляху рівну 0; вузол на рівні i має довжину шляху рівну i.
Бінарне дерево застосовується в тих випадках, коли в кожній точці обчислювального процесу повинно бути прийнято одне з двох можливих рішень.
Є багато завдань, які можна виконувати на дереві.
Поширена завдання - виконання заданої операції p з кожним елементом дерева. Тут p розглядається як параметр більш загальної задачі відвідування всіх вузлів або завдання обходу дерева.
Якщо розглядати завдання як єдиний послідовний процес, то окремі вузли відвідуються в певному порядку і можуть вважатися розташованими лінійно.
