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

Поделись знанием:
Перейти к: навигация, поиск
У этого термина существуют и другие значения, см. Дерево (значения).

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





Определения

  • Корневой узел — самый верхний узел дерева (узел 8 на примере).
  • Корень — одна из вершин, по желанию наблюдателя.
  • лист, листовой или терминальный узел — узел, не имеющий дочерних элементов (узлы 1, 4, 7, 13).
  • Внутренний узел — любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом (3, 6, 10, 14).

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

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

Узлы

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

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

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

Поддеревья

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Распространённые древовидные структуры
Самобалансирующиеся двоичные деревья поиска
Прочие деревья

Напишите отзыв о статье "Дерево (структура данных)"

Примечания

Литература

Ссылки

  • [www.nist.gov/dads/HTML/tree.html Описание] из Словаря алгоритмов и структур данных
  • [ideainfo.8m.com Описание древовидных структур]
  • [algolist.manual.ru/ds/walk.php Обходы бинарных деревьев]
  • [algolist.manual.ru/ds/rbtree.php Красно-черные деревья]
Типы
Массивы

Ассоциативный массив • Ассоциативный мультимассив • Множество • Мультимножество • Хеш-таблица

Списки
Деревья
Графы

Отрывок, характеризующий Дерево (структура данных)

Анатоль повернулся к англичанину и, взяв его за пуговицу фрака и сверху глядя на него (англичанин был мал ростом), начал по английски повторять ему условия пари.
– Постой! – закричал Долохов, стуча бутылкой по окну, чтоб обратить на себя внимание. – Постой, Курагин; слушайте. Если кто сделает то же, то я плачу сто империалов. Понимаете?
Англичанин кивнул головой, не давая никак разуметь, намерен ли он или нет принять это новое пари. Анатоль не отпускал англичанина и, несмотря на то что тот, кивая, давал знать что он всё понял, Анатоль переводил ему слова Долохова по английски. Молодой худощавый мальчик, лейб гусар, проигравшийся в этот вечер, взлез на окно, высунулся и посмотрел вниз.
– У!… у!… у!… – проговорил он, глядя за окно на камень тротуара.
– Смирно! – закричал Долохов и сдернул с окна офицера, который, запутавшись шпорами, неловко спрыгнул в комнату.
Поставив бутылку на подоконник, чтобы было удобно достать ее, Долохов осторожно и тихо полез в окно. Спустив ноги и расперевшись обеими руками в края окна, он примерился, уселся, опустил руки, подвинулся направо, налево и достал бутылку. Анатоль принес две свечки и поставил их на подоконник, хотя было уже совсем светло. Спина Долохова в белой рубашке и курчавая голова его были освещены с обеих сторон. Все столпились у окна. Англичанин стоял впереди. Пьер улыбался и ничего не говорил. Один из присутствующих, постарше других, с испуганным и сердитым лицом, вдруг продвинулся вперед и хотел схватить Долохова за рубашку.
– Господа, это глупости; он убьется до смерти, – сказал этот более благоразумный человек.
Анатоль остановил его:
– Не трогай, ты его испугаешь, он убьется. А?… Что тогда?… А?…
Долохов обернулся, поправляясь и опять расперевшись руками.
– Ежели кто ко мне еще будет соваться, – сказал он, редко пропуская слова сквозь стиснутые и тонкие губы, – я того сейчас спущу вот сюда. Ну!…
Сказав «ну»!, он повернулся опять, отпустил руки, взял бутылку и поднес ко рту, закинул назад голову и вскинул кверху свободную руку для перевеса. Один из лакеев, начавший подбирать стекла, остановился в согнутом положении, не спуская глаз с окна и спины Долохова. Анатоль стоял прямо, разинув глаза. Англичанин, выпятив вперед губы, смотрел сбоку. Тот, который останавливал, убежал в угол комнаты и лег на диван лицом к стене. Пьер закрыл лицо, и слабая улыбка, забывшись, осталась на его лице, хоть оно теперь выражало ужас и страх. Все молчали. Пьер отнял от глаз руки: Долохов сидел всё в том же положении, только голова загнулась назад, так что курчавые волосы затылка прикасались к воротнику рубахи, и рука с бутылкой поднималась всё выше и выше, содрогаясь и делая усилие. Бутылка видимо опорожнялась и с тем вместе поднималась, загибая голову. «Что же это так долго?» подумал Пьер. Ему казалось, что прошло больше получаса. Вдруг Долохов сделал движение назад спиной, и рука его нервически задрожала; этого содрогания было достаточно, чтобы сдвинуть всё тело, сидевшее на покатом откосе. Он сдвинулся весь, и еще сильнее задрожали, делая усилие, рука и голова его. Одна рука поднялась, чтобы схватиться за подоконник, но опять опустилась. Пьер опять закрыл глаза и сказал себе, что никогда уж не откроет их. Вдруг он почувствовал, что всё вокруг зашевелилось. Он взглянул: Долохов стоял на подоконнике, лицо его было бледно и весело.
– Пуста!
Он кинул бутылку англичанину, который ловко поймал ее. Долохов спрыгнул с окна. От него сильно пахло ромом.
– Отлично! Молодцом! Вот так пари! Чорт вас возьми совсем! – кричали с разных сторон.
Англичанин, достав кошелек, отсчитывал деньги. Долохов хмурился и молчал. Пьер вскочил на окно.
Господа! Кто хочет со мною пари? Я то же сделаю, – вдруг крикнул он. – И пари не нужно, вот что. Вели дать бутылку. Я сделаю… вели дать.
– Пускай, пускай! – сказал Долохов, улыбаясь.
– Что ты? с ума сошел? Кто тебя пустит? У тебя и на лестнице голова кружится, – заговорили с разных сторон.
– Я выпью, давай бутылку рому! – закричал Пьер, решительным и пьяным жестом ударяя по столу, и полез в окно.
Его схватили за руки; но он был так силен, что далеко оттолкнул того, кто приблизился к нему.
– Нет, его так не уломаешь ни за что, – говорил Анатоль, – постойте, я его обману. Послушай, я с тобой держу пари, но завтра, а теперь мы все едем к***.
– Едем, – закричал Пьер, – едем!… И Мишку с собой берем…
И он ухватил медведя, и, обняв и подняв его, стал кружиться с ним по комнате.


Князь Василий исполнил обещание, данное на вечере у Анны Павловны княгине Друбецкой, просившей его о своем единственном сыне Борисе. О нем было доложено государю, и, не в пример другим, он был переведен в гвардию Семеновского полка прапорщиком. Но адъютантом или состоящим при Кутузове Борис так и не был назначен, несмотря на все хлопоты и происки Анны Михайловны. Вскоре после вечера Анны Павловны Анна Михайловна вернулась в Москву, прямо к своим богатым родственникам Ростовым, у которых она стояла в Москве и у которых с детства воспитывался и годами живал ее обожаемый Боренька, только что произведенный в армейские и тотчас же переведенный в гвардейские прапорщики. Гвардия уже вышла из Петербурга 10 го августа, и сын, оставшийся для обмундирования в Москве, должен был догнать ее по дороге в Радзивилов.
У Ростовых были именинницы Натальи, мать и меньшая дочь. С утра, не переставая, подъезжали и отъезжали цуги, подвозившие поздравителей к большому, всей Москве известному дому графини Ростовой на Поварской. Графиня с красивой старшею дочерью и гостями, не перестававшими сменять один другого, сидели в гостиной.
Графиня была женщина с восточным типом худого лица, лет сорока пяти, видимо изнуренная детьми, которых у ней было двенадцать человек. Медлительность ее движений и говора, происходившая от слабости сил, придавала ей значительный вид, внушавший уважение. Княгиня Анна Михайловна Друбецкая, как домашний человек, сидела тут же, помогая в деле принимания и занимания разговором гостей. Молодежь была в задних комнатах, не находя нужным участвовать в приеме визитов. Граф встречал и провожал гостей, приглашая всех к обеду.
«Очень, очень вам благодарен, ma chere или mon cher [моя дорогая или мой дорогой] (ma сherе или mon cher он говорил всем без исключения, без малейших оттенков как выше, так и ниже его стоявшим людям) за себя и за дорогих именинниц. Смотрите же, приезжайте обедать. Вы меня обидите, mon cher. Душевно прошу вас от всего семейства, ma chere». Эти слова с одинаковым выражением на полном веселом и чисто выбритом лице и с одинаково крепким пожатием руки и повторяемыми короткими поклонами говорил он всем без исключения и изменения. Проводив одного гостя, граф возвращался к тому или той, которые еще были в гостиной; придвинув кресла и с видом человека, любящего и умеющего пожить, молодецки расставив ноги и положив на колена руки, он значительно покачивался, предлагал догадки о погоде, советовался о здоровье, иногда на русском, иногда на очень дурном, но самоуверенном французском языке, и снова с видом усталого, но твердого в исполнении обязанности человека шел провожать, оправляя редкие седые волосы на лысине, и опять звал обедать. Иногда, возвращаясь из передней, он заходил через цветочную и официантскую в большую мраморную залу, где накрывали стол на восемьдесят кувертов, и, глядя на официантов, носивших серебро и фарфор, расставлявших столы и развертывавших камчатные скатерти, подзывал к себе Дмитрия Васильевича, дворянина, занимавшегося всеми его делами, и говорил: «Ну, ну, Митенька, смотри, чтоб всё было хорошо. Так, так, – говорил он, с удовольствием оглядывая огромный раздвинутый стол. – Главное – сервировка. То то…» И он уходил, самодовольно вздыхая, опять в гостиную.
– Марья Львовна Карагина с дочерью! – басом доложил огромный графинин выездной лакей, входя в двери гостиной.
Графиня подумала и понюхала из золотой табакерки с портретом мужа.
– Замучили меня эти визиты, – сказала она. – Ну, уж ее последнюю приму. Чопорна очень. Проси, – сказала она лакею грустным голосом, как будто говорила: «ну, уж добивайте!»


Источник — «http://wiki-org.ru/wiki/index.php?title=Дерево_(структура_данных)&oldid=77642606»