Отметьте все элементы которые могут присутствовать в дереве
Перейти к содержимому

Отметьте все элементы которые могут присутствовать в дереве

  • автор:

Дерево как структура данных

Какую выгоду можно извлечь из такой структуры данных, как дерево? В этой статье мы расскажем о данных в виде дерева, рассмотрим основные определения, которые следует знать, а также узнаем, как и зачем используется дерево в программировании. Спойлер: бинарные деревья часто применяют для поиска информации в базах данных, для сортировки данных, для проведения вычислений, для кодирования и в других случаях. Но давайте обо всем по порядку.

Основные термины

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

Дерево как структура данных

Каждый элемент — это вершина или узел дерева. Узлы, соединенные направленными дугами, называются ветвями. Начальный узел — это корень дерева (корневой узел). Листья — это узлы, в которые входит 1 ветвь, причем не выходит ни одной.

Общую терминологию можно посмотреть на левой и правой части картинки ниже:

Дерево как структура данных

Какие свойства есть у каждого древа:

— существует узел, в который не входит ни одна ветвь;

— в каждый узел, кроме корневого узла, входит 1 ветвь.

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

Также у дерева есть высота (глубина). Она определяется числом уровней, на которых располагаются узлы дерева. Глубина пустого древа равняется нулю, а если речь идет о дереве из одного корня, тогда единице. В данном случае на нулевом уровне может быть лишь одна вершина – корень, на 1-м – потомки корня, на 2-м – потомки потомков корня и т. д.

Ниже изображен графический вывод древа с 4-мя уровнями (дерево имеет глубину, равную четырем):

Дерево как структура данных

Следующий термин, который стоит рассмотреть, — это поддерево. Поддеревом называют часть древообразной структуры, которую можно представить в виде отдельного дерева.

Идем дальше. Древо может быть упорядоченным — в данном случае ветви, которые исходят из каждого узла, упорядочены по некоторому критерию.

Степень вершины в древе — это число ветвей (дуг), выходящих из этой вершины. Степень равняется максимальной степени вершины, которая входит в дерево. В этом случае листьями будут узлы, имеющие нулевую степень. По величине степени деревья бывают:

— двоичные (степень не больше двух);

— сильноветвящиеся (степень больше двух).

Деревья — это рекурсивные структуры, ведь каждое поддерево тоже является деревом. Каждый элемент такой рекурсивной структуры является или пустой структурой, или компонентом, с которым связано конечное количество поддеревьев.

Когда мы говорим о рекурсивных структурах, то действия с ними удобнее описывать посредством рекурсивных алгоритмов.

Обход древа

Чтобы выполнить конкретную операцию над всеми вершинами, надо все эти узлы просмотреть. Данную задачу называют обходом дерева. То есть обход представляет собой упорядоченную последовательность узлов, в которой каждый узел встречается лишь один раз.

В процессе обхода все узлы должны посещаться в некотором, заранее определенном порядке. Есть ряд способов обхода, вот три основные:

— прямой (префиксный, preorder);

— симметричный (инфиксный, inorder);

— обратный (постфиксный, postorder).

Существует много древовидных структур данных: двоичные (бинарные), красно-черные, В-деревья, матричные, смешанные и пр. Поговорим о бинарных.

Бинарные (двоичные) деревья

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

Дерево как структура данных

У бинарного древа каждый текущий узел — это структура, которая состоит из 4-х видов полей. Какие это поля:

— информационное (ключ вершины);

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

— указатель на правое поддерево;

— указатель на левое поддерево.

Самый удобный вид бинарного древа — бинарное дерево поиска.

Что значит древо в контексте программирования?

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

В каких случаях древовидные структуры могут быть полезны при программировании:

Дерево как структура данных

  1. Когда данная иерархия существует в предметной области разрабатываемой программы. К примеру, программа должна обрабатывать генеалогическое древо либо работать со структурой каталогов. В таких ситуациях иногда есть смысл сохранять между объектами программы существующие иерархические отношения. В качестве примера можно вывести древо каталогов операционной системы UNIX:
  • Когда между объектами, которые обрабатывает программа, отношения иерархии не заданы явно, но их можно задать, что сделает обработку данных удобнее. Как тут не вспомнить разработку парсеров либо трансляторов, где весьма полезным может быть древо синтаксического разбора?
  • А сейчас очевидная вещь: поиск объектов более эффективен, когда объекты упорядочены, будь то те же базы данных. К примеру, поиск значения в неструктурированном наборе из тысячи элементов потребует до тысячи операций, тогда как в упорядоченном наборе может хватить всего дюжины. Вывод прост: раз иерархия — эффективный способ упорядочивания объектов, почему же не использовать древовидную иерархию для ускорения поиска узлов со значениями? Так и происходит: если вспомнить бинарные деревья, то на практике их можно применять в следующих целях:

— поиск данных в базах данных (специально построенных деревьях);

— сортировка и вывод данных;

— вычисления арифметических выражений;

— кодирование по методу Хаффмана и пр.

Дерево (структура данных)

Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.

Определения

  • Корневой узел — самый верхний узел дерева.
  • Корень — одна из вершин, по желанию наблюдателя.
  • лист, листовой или терминальныйузел — узел, не имеющий дочерних элементов.
  • Внутренний узел — любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом.

Дерево считается ориентированным, если в корень не заходит ни одно ребро.

  • Полный сцепленный ключ — идентификатор записи, который образуется путём конкатенации всех ключей экземпляров родительских записей (групп).

Узлы

Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья ‘растут’ вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.

Корневые узлы

Самый верхний узел дерева называется корневым узлом. Быть самым верхним узлом подразумевает отсутствие у корневого узла предков. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). (Согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, кучах, корневой узел обладает особыми свойствами. Каждый узел дерева можно рассматривать как корневой узел поддерева, «растущего» из этого узла.

Поддеревья

Поддерево — часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).

Упорядочивание деревьев

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

Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.

Представление деревьев

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

Деревья как графы

В теории графов дерево — связанный ациклический граф. Корневое дерево — это граф с вершиной, выделенной в качестве корневой. В этом случае любые две вершины, связанные ребром, наследуют отношения «родитель-потомок». Ациклический граф со множеством связанных компонентов или набор корневых деревьев иногда называется лесом.

Методы обхода

Основная статья: Обход дерева

Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.

Общие операции

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

Общее применение

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

См. также

  • Двоичное разбиение пространства
  • Куча (структура данных)
  • Дерево (теория графов)
  • Дерево (теория наборов)
  • Древовидная структура
  • Префиксное дерево
  • Экспоненциальное дерево
  • Двоичное дерево
  • АА-дерево
  • АВЛ-дерево
  • Красно-чёрное дерево
  • Расширяющееся дерево
  • Дерево со штрафами
  • B-дерево (2-3-дерево, B+-деревья, B*-дерево, UB-дерево)
  • DSW-алгоритм
  • Танцующее дерево
  • Анфилада
  • Смешанное дерево
  • k-мерное дерево
  • Октодерево
  • Квадродерево
  • R-дерево
  • Дерево остатков
  • Сегментное дерево
  • Список с пропусками
  • T-дерево
  • T-пирамида
  • Верхнее дерево
  • Дерево ван Емде Боаса

Примечания

Литература

  • Дональд Э. Кнут. Глава 2.3. Деревья // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М .: Вильямс, 2000. — Т. 2. Основные алгоритмы. — 832 с. — 7000 экз. — ISBN 5-8459-0081-6 (рус.) ISBN 0-201-89684-2 (англ.)
  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Introduction to Algorithms. — 2nd Edition. — MIT Press, McGraw-Hill, 2001. — ISBN 0-262-03293-7
    • Section 10.4: Representing rooted trees, pp.214-217.
    • Chapters 12-14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp. 253—320.

    Ссылки

    • Описание из Словаря алгоритмов и структур данных
    • STL-похожий C++ класс деревьев
    • Описание древовидных структур
    • Обходы бинарных деревьев
    • АВЛ-деревья (zip)
    • Красно-черные деревья
    • Деревья со случайным поиском
    • Слоёные списки (скип-списки)
    • Б, Б+ и Б++ деревья
    • StringBTree (zip)
    Дерево (структура данных)
    Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура
    Двоичные деревья Двоичное дерево · T-дерево
    Самобалансирующиеся двоичные деревья АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи
    B-деревья B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево
    Префиксные деревья Суффиксное дерево · Radix tree · Ternary search tree
    Двоичное разбиение пространства k-мерное дерево · VP-дерево
    Недвоичные деревья Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево
    Разбиение пространства R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков
    Другие деревья Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree
    Алгоритмы Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева

    Структура информации

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

    10 класс, 2 вариант, проверка знаний по иерархии, деревья, графы
    Система оценки: 5** балльная

    Список вопросов теста

    Вопрос 1

    Как называется узел дерева, у которого нет потомков?

    Вопрос 2

    Отметьте все элементы, которые могут присутствовать в дереве.

    Варианты ответов
    • корень
    • ствол
    • ветки
    • листья
    • дуги (ребра)
    Вопрос 3

    В каких отношениях состоят узлы А и Г?

    Варианты ответов
    • узел А — родитель для узла Г
    • узел А — предок для узла Г
    • узел Г — потомок для узла А
    • узел Г — сын для узла А
    • это некорректный вопрос
    Вопрос 4

    Какова высота этого дерева?

    Вопрос 5

    Перечислите узлы, которые являются сыновьями узла А.

    Варианты ответов
    • Б, В
    • Б, В, Г, Д
    • В, Г, Д
    • Б, Г, Д
    Вопрос 6

    На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

    Вопрос 7

    Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего маршрута из А в B.

    Вопрос 8

    Между населёнными пунктами A, B, C, D, E построены дороги, стоимость перевозки по которым приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите МАКСИМАЛЬНУЮ стоимость перевозки груза из C в B при условии, что маршрут не может проходить через какой-то пункт более одного раза.

    Вопрос 9

    На рисунке приведена весовая матрица графа. Определите, сколько рёбер имеет такой граф.

    Вопрос 10

    На рисунке приведена весовая матрица графа, в которой веса обозначают расстояния между соседними пунктами. Определите длину маршрута E-D-C-A.

    Дерево

    Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.

    Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент ( корень ), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями . Каждый элемент бинарного дерева называется узлом . Связи между узлами дерева называются его ветвями .

    Бинарное дерево

    Способ представления бинарного дерева:

    • A — корень дерева
    • В — корень левого поддерева
    • С — корень правого поддерева

    Корень дерева расположен на уровне с минимальным значением.

    Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .

    Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .

    Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.

    Остальные элементы – внутренние узлы (узлы ветвления).

    Число потомков внутреннего узла называется его степенью . Максимальная степень всех узлов есть степень дерева.

    Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .

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

    Имеется много задач, которые можно выполнять на дереве.

    Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.

    Если рассматривать задачу как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно.

    Способы обхода дерева

    Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.

    Дерево

    Существует три способа обхода дерева:

    • Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
    • Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
    • Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.

    Реализация дерева

    Узел дерева можно описать как структуру:

    struct tnode <
    int field; // поле данных
    struct tnode *left; // левый потомок
    struct tnode *right; // правый потомок
    >;

    При этом обход дерева в префиксной форме будет иметь вид

    void treeprint(tnode *tree) <
    if (tree!= NULL ) < //Пока не встретится пустой узел
    cout field; //Отображаем корень дерева
    treeprint(tree->left); //Рекурсивная функция для левого поддерева
    treeprint(tree->right); //Рекурсивная функция для правого поддерева
    >
    >

    Обход дерева в инфиксной форме будет иметь вид

    void treeprint(tnode *tree) <
    if (tree!= NULL ) < //Пока не встретится пустой узел
    treeprint(tree->left); //Рекурсивная функция для левого поддерева
    cout field; //Отображаем корень дерева
    treeprint(tree->right); //Рекурсивная функция для правого поддерева
    >
    >

    Обход дерева в постфиксной форме будет иметь вид

    void treeprint(tnode *tree) <
    if (tree!= NULL ) < //Пока не встретится пустой узел
    treeprint(tree->left); //Рекурсивная функция для левого поддерева
    treeprint(tree->right); //Рекурсивная функция для правого поддерева
    cout field; //Отображаем корень дерева
    >
    >

    Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

    • оба поддерева – левое и правое, являются двоичными деревьями поиска;
    • у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X ;
    • у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X .

    Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.

    Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.

    Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.

    Добавление узлов в дерево

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12

    struct tnode * addnode( int x, tnode *tree) <
    if (tree == NULL ) < // Если дерева нет, то формируем корень
    tree =new tnode; // память под узел
    tree->field = x; // поле данных
    tree->left = NULL ;
    tree->right = NULL ; // ветви инициализируем пустотой
    >else if (x < tree->field) // условие добавление левого потомка
    tree->left = addnode(x,tree->left);
    else // условие добавление правого потомка
    tree->right = addnode(x,tree->right);
    return (tree);
    >

    Удаление поддерева

    void freemem(tnode *tree) <
    if (tree!= NULL ) <
    freemem(tree->left);
    freemem(tree->right);
    delete tree;
    >
    >

    Пример Написать программу, подсчитывающую частоту встречаемости слов входного потока.

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

    Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся бинарным деревом.

    В дереве каждый узел содержит:

    • указатель на текст слова;
    • счетчик числа встречаемости;
    • указатель на левого потомка;
    • указатель на правого потомка.

    Рассмотрим выполнение программы на примере фразы

    now is the time for all good men to come to the aid of their party

    now is the time for all good men to come to the aid of their party

    При этом дерево будет иметь следующий вид

    #include
    #include
    #include
    #include
    //#include
    #define MAX WORD 100
    struct tnode < // узел дерева
    char * word; // указатель на строку (слово)
    int count; // число вхождений
    struct tnode* left; // левый потомок
    struct tnode* right; // правый потомок
    >;
    // Функция добавления узла к дереву
    struct tnode* addtree( struct tnode* p, char * w) int cond;
    if (p == NULL ) p = ( struct tnode*)malloc( sizeof ( struct tnode));
    p->word = _strdup(w);
    p->count = 1;
    p->left = p->right = NULL ;
    >
    else if ((cond = strcmp(w, p->word)) == 0)
    p->count++;
    else if (cond < 0)
    p->left = addtree(p->left, w);
    else
    p->right = addtree(p->right, w);
    return p;
    >
    // Функция удаления поддерева
    void freemem(tnode* tree) if (tree != NULL ) freemem(tree->left);
    freemem(tree->right);
    free(tree->word);
    free(tree);
    >
    >
    // Функция вывода дерева
    void treeprint( struct tnode* p) if (p != NULL ) treeprint(p->left);
    printf( «%d %s\n» , p->count, p->word);
    treeprint(p->right);
    >
    >
    int main() struct tnode* root;
    char word[MAX WORD ];
    root = NULL ;
    do scanf_s( «%s» , word, MAX WORD );
    if (isalpha(word[0]))
    root = addtree(root, word);
    > while (word[0] != ‘0’ ); // условие выхода – ввод символа ‘0’
    treeprint(root);
    freemem(root);
    getchar();
    getchar();
    return 0;
    >

    Результат выполнения: бинарное дерево

    Результат выполнения

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *