Дерево в информатике

Дерево (англ. tree) - в информатике и программировании одна из самых распространенных структур данных.

Свойства

Из определения следует, что каждая вершина является в свою очередь корнем некоторого поддерева. Количество поддеревьев вершины называется степени (degree) этой вершины. Вершина степени нуль называется конечной (terminal) или письмо (leaf). Неконечная вершина также называется вершиной ветвления (branch node).

Пусть x - произвольная вершина дерева с корнем r. Тогда существует единственный путь из r в x. Все вершины на этом пути называются предками (ancestors) x; если некоторая вершина y является предком x, то x называется потомком (descendant) y. Потомки и предки вершины x, не совпадающие с ней самой, называются собственными потомками и предками. Каждую вершину x, в свою очередь, можно рассматривать как корень некоторого поддерева, элементами которого являются вершины-потомки x.
Если вершины x является предком y и не существует вершин между ними (т.е. x и y соединены одним ребром), а также существуют предки для x (т.е. x не является корнем), то вершина x называется отцом (parent) к y, а y - ребенком (child) x. Корневая вершина единственная не имеет родителей.

Вершины, имеющие общего отца, называются братьями (siblings). Вершины, имеющие детей, длина пути от корня к этой вершине. Максимальная глубина вершин дерева называется высотой.

Если существует относительный порядок на поддеревья T 1 ... T M, то такое дерево называется упорядоченным (ordered tree) или плоским (plane tree).
Лесом (англ. forest) называют множество деревьев, которые не пересекаются.

Зачастую деревья в информатике изображают с корнем, который находится сверху (говорят, что дерево в информатике «растет вниз»).

Важным частным случаем корневых деревьев является бинарные деревья, которые широко применяются в программировании и определяются как множество вершин, у которого выделен корень и два поддерева (правое и левое), не пересекаются, либо является пустой множеством вершин (в отличие от обычного дерева, которое не может быть пустым).

Операции над деревом

Важными операциями на деревьях являются:

• обход вершин в разном порядке;
• перенумерация вершин;
• поиск элемента;
• добавление элемента в назначенное место в дереве;
• удаление элемента;
• удаление целого фрагмента дерева;
• добавление целого фрагмента дерева;
• трансформации (повороты) фрагментов дерева;
• нахождение корня для любой вершины.

Наибольшее распространение эти структуры данных получили в тех задачах, где необходимо манипулирования с иерархическими данными, эффективный поиск в данных, их структурированное хранение и модификация.