Дерево!!!
Дерево данних
Дерево - одна з найбільш широко поширених структур даних в інформатиці, емулююча деревоподібну структуру у вигляді набору пов'язаних вузлів. Є зв'язковим графом, що не містить цикли. Більшість джерел також додають умова на те, що ребра графа не повинні бути орієнтованими. На додаток до цих трьох обмеженням, в деяких джерелах вказується, що ребра графа не повинні бути зваженими.
Структура
Дерево - структура даних, що представляє собою деревоподібну структуру у вигляді набору пов'язаних вузлів.
Бінарне дерево - це кінцеве безліч елементів, яке або порожня, або містить елемент (корінь), пов'язаний з двома різними бінарними деревами, званими лівим і правим піддеревами. Кожен елемент бінарного дерева називається вузлом. Зв'язки між вузлами дерева називаються його гілками.
Спосіб подання бінарного дерева:
A - корінь дерева
В - корінь лівого піддерева
C - корінь правого піддерева
Корінь дерева розташований на рівні з мінімальним значенням.
Вузол D, який знаходиться безпосередньо під вузлом B, називається нащадком B. Якщо D знаходиться на рівні i, то B - на рівні i-1. Вузол B називається предком D.
Максимальний рівень будь-якого елементу дерева називається його глибиною або висотою.
Якщо елемент не має нащадків, він називається листом або термінальним вузлом дерева.
Інші елементи - внутрішні вузли (вузли розгалуження).
Число нащадків внутрішнього вузла називається його ступенем. Максимальний ступінь всіх вузлів є ступінь дерева.
Число гілок, яке потрібно пройти від кореня до вузла x, називається довжиною шляху до x. Корінь має довжину шляху рівну 0; вузол на рівні i має довжину шляху рівну i.
Бінарне дерево застосовується в тих випадках, коли в кожній точці обчислювального процесу повинно бути прийнято одне з двох можливих рішень.
Є багато завдань, які можна виконувати на дереві.
Поширена завдання - виконання заданої операції p з кожним елементом дерева. Тут p розглядається як параметр більш загальної задачі відвідування всіх вузлів або завдання обходу дерева.
Якщо розглядати завдання як єдиний послідовний процес, то окремі вузли відвідуються в певному порядку і можуть вважатися розташованими лінійно.
