Двоичное дерево поиска: базовые операции [итеративное решение]

  1. Элемент нумерованного списка

Структура данных «дерево»

  1. определения и общие понятия

  2. наглядный пример

  3. многие полезные структуры данных

  • Двоичное дерево поиска

  • АВЛ-дерево

  • Красно-чёрное дерево

2.Структура продукта


2.1 Работа в Wiki 2.2 Презентация

  1. Сбор информации (с 20 января по 1 февраля)

  2. 2.Сбор ссылок (с 1 по 7 февраля)

  3. 3.Размещение информации на сайте (с 7 по 17 февраля)

  4. 4.Структуирование информации (с 17 февраля по 1 марта)

  5. 5.Отформатирование информации (с 1 по 10 марта)

  6. 6.Создание презентации (с 10 по 18 марта)

  7. 7.Подготовка к выступлению (с 18 марта по 1 апреля)

Определение и общие понятие

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

Двои́чное де́рево http://dic.academic.ru/dic.nsf/ruwiki/147481— структура данных, являющаяся программной реализацией двоичного дерева (графа). Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные привязанные к узлу, left, right — ссылки на узлы, являющиеся детьми данного узла. Узел left называется левым ребёнком (сыном), а узел right — правым.

Существует следующее рекурсивное определение двоичного дерева (см. БНФ):

<дерево> ::= ( <данные> <дерево> <дерево> ) | nil .

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

Пример

Все о двоичном дереве

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

Двоичное дерево поиска (binary search tree, BST) — это двоичное дерево, в котором данные, привязанные к каждому узлу, представляют собой пару (key, value) (ключ и значение), причём на ключах определена операция сравнения «меньше», и для всех узлов дерева выполнено свойство, называемое свойством дерева поиска:

у всех узлов левого поддерева произвольного узла n значение ключей меньше, нежели значения ключа узла n, у всех узлов правого поддерева произвольного узла n значение ключей не меньше, нежели значения ключа узла n.

Основные операции в двоичном дереве поиска

Базовый интерфейс двоичного дерева поиска состоит из трех операций:

FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K. INSERT(K,V) — добавление в дерево пары (key, value) = (K, V). REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K.

По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, INSERT, REMOVE.

Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

АВЛ-дерево

АВЛ-дерево — балансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962.

Алгоритм добавления вершины

Первый шаг аналогичен добавлению вершины в Двоичное дерево поиска. Далее производится балансировка всех предков добавленной вершины в порядке от родителя к корню. Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится ⇐ 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.

  1. 1.Малое правое вращение

Данное вращение используется тогда, когда (высота b-поддерева — высота L) = 2 и высота С ⇐ высота R.

  • 2.Большое правое вращение

Данное вращение используется тогда, когда (высота b-поддерева — высота L) = 2 и высота c-поддерева > высота R.

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

Из-за условия балансированности высота дерева О(lg(N)), где N- количество вершин, поэтому добавление элемента требует O(lg(N)) операций.

Красно-чёрное дерево

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

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

http://algolist.manual.ru/ds/rbtree.php

 

За исключением случаев, когда указано иное, содержимое этой вики предоставляется на условиях следующей лицензии:CC Attribution-Noncommercial-Share Alike 3.0 Unported


Содержание | <<< | >>>

Двоичные деревья

Напоследок мы рассмотрим структуру данных, которая называется двоичное дерево (binary tree). Несмотря на то, что бывает много различных типов деревьев, двоичные деревья играют особую роль, так как в отсортированном состоянии позволяют очень быстро выполнять вставку, удаление и поиск. Каждый элемент двоичного дерева состоит из информационной части и указателей на левый и правый элементы. На рис. 22.8 показано небольшое двоичное дерево.

При обсуждении деревьев применяется специальная терминология. Программисты не являются специалистами в области филологии, и поэтому терминология, применяемая в теории графов (а ведь деревья представляют собой частный случай графов!), является классическим примером неправильного употребления слов. Первый элемент дерева называется корнем (root). Каждый элемент данных называется вершиной дерева (node), а любой фрагмент дерева называется поддеревом (subtree). Вершина, к которой не присоединены поддеревья, называется заключительным узлом (terminal node) или листом (leaf). Высота (height) дерева равняется максимальному количеству уровней от корня до листа. При работе с деревьями можно допустить, что в памяти они существуют в том же виде, что и на бумаге. Но помните, что дерево — всего лишь способ логической организации данных в памяти, а память линейна.

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

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

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

d ↙ ↘ b f ↙ ↘ ↙ ↘ a c e g

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

Симметричный обход a b c d e f g Прямой обход d b a c f e g Обход снизу a c b e g f d

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

Приведенная ниже функция создает упорядоченное двоичное дерево:

struct tree { char info; struct tree *left; struct tree *right; }; struct tree *stree( struct tree *root, struct tree *r, char info) { if(!r) { r = (struct tree *) malloc(sizeof(struct tree)); if(!r) { printf(«Не хватает памяти\n»); exit(0); } r->left = NULL; r->right = NULL; r->info = info; if(!root) return r; /* первый вход */ if(info < root->info) root->left = r; else root->right = r; return r; } if(info < r->info) stree(r,r->left,info); else stree(r,r->right,info); return root; }

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

/* вызов функции street() */ rt = street(rt, rt, info);

Функция использует рекурсивный алгоритм, как и большинство процедур работы с деревьями. Точно такая же функция, основанная на итеративных методах, была бы в несколько раз длиннее. Функцию необходимо вызывать со следующими параметрами (слева направо): указатель на корень всего дерева, указатель на корень следующего поддерева, в котором осуществляется поиск, и сохраняемые данные. При первом вызове оба первых параметрах указывают на корень всего дерева. Для простоты в вершинах дерева хранятся одиночные символы. Тем не менее, вместо них можно использовать любой тип данных.

Динамические структуры данных: бинарные деревья

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

void inorder(struct tree *root) { if(!root) return; inorder(root->left); if(root->info) printf(«%c «, root->info); inorder(root->right); }

Данная рекурсивная функция завершает работу тогда, когда находит заключительный узел (нулевой указатель).

В следующем листинге показаны функции, выполняющие обход дерева в ширину и в глубину.

void preorder(struct tree *root) { if(!root) return; if(root->info) printf(«%c «, root->info); preorder(root->left); preorder(root->right); } void postorder(struct tree *root) { if(!root) return; postorder(root->left); postorder(root->right); if(root->info) printf(«%c «, root->info); }

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

void print_tree(struct tree *r, int l) { int i; if(r == NULL) return; print_tree(r->right, l+1); for(i=0; i

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

/* Эта программа выводит на экран двоичное дерево. */ #include <stdlib.h> #include <stdio.h> struct tree { char info; struct tree *left; struct tree *right; }; struct tree *root; /* начальная вершина дерева */ struct tree *stree(struct tree *root, struct tree *r, char info); void print_tree(struct tree *root, int l); int main(void) { char s[80]; root = NULL; /* инициализация корня дерева */ do { printf(«Введите букву: «); gets(s); root = stree(root, root, *s); } while(*s); print_tree(root, 0); return 0; } struct tree *stree( struct tree *root, struct tree *r, char info) { if(!r) { r = (struct tree *) malloc(sizeof(struct tree)); if(!r) { printf(«Не хватает памяти\n»); exit(0); } r->left = NULL; r->right = NULL; r->info = info; if(!root) return r; /* первый вход */ if(info < root->info) root->left = r; else root->right = r; return r; } if(info < r->info) stree(r, r->left, info); else stree(r, r->right, info); return root; } void print_tree(struct tree *r, int l) { int i; if(!r) return; print_tree(r->right, l+1); for(i=0; i

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

Если вы запускали программу печати дерева, вы, вероятно, заметили, что некоторые деревья являются сбалансированными (balanced), т.е. каждое поддерево имеет примерно такую же высоту, как и остальные, а некоторые деревья очень далеки от этого состояния. Например, дерево abcd выглядит следующим образом:

a ↘ b ↘ c ↘ d

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

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

struct tree *search_tree(struct tree *root, char key) { if(!root) return root; /* пустое дерево */ while(root->info != key) { if(key

К сожалению, удалить вершину дерева не так просто, как отыскать. Удаляемая вершина может быть либо корнем, либо левой, либо правой вершиной. Помимо того, к вершине могут быть присоединены поддеревья (количество присоединенных поддеревьев может равняться 0, 1 или 2). Процесс переустановки указателей подсказывает рекурсивный алгоритм, приведенный ниже:

struct tree *dtree(struct tree *root, char key) { struct tree *p,*p2; if(!root) return root; /* вершина не найдена */ if(root->info == key) { /* удаление корня */ /* это означает пустое дерево */ if(root->left == root->right){ free(root); return NULL; } /* или если одно из поддеревьев пустое */ else if(root->left == NULL) { p = root->right; free(root); return p; } else if(root->right == NULL) { p = root->left; free(root); return p; } /* или есть оба поддерева */ else { p2 = root->right; p = root->right; while(p->left) p = p->left; p->left = root->left; free(root); return p2; } } if(root->info < key) root->right = dtree(root->right, key); else root->left = dtree(root->left, key); return root; }

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

root = dtree(root, key);

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


Содержание | <<< | >>>

Двоичное дерево – вид связного ациклического (не имеющего циклов) графа, характерный тем, что у каждого из его узлов имеется не более двух потомков (связанных узлов, находящихся иерархически ниже).

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

В двоичном дереве есть только один узел, у которого нет предка, он называется корнем. Конечные узлы – листья. Если у корня отсутствует предок, то у листьев – потомки. Все вершины помимо корня и листьев называются узлами ветвления. Длина пути от корня до узла определяет уровень этого самого узла. Уровень корня дерева всегда равен нулю, а уровень всех его потомков определяется удаленностью от него. Например, узлы F и L (рис. ниже) расположены на первом уровне, а U и B – на третьем.

Связный граф является деревом тогда и только тогда, когда PA=1, где P – количество вершин в графе, а A – количество ребер, поскольку в любом дереве с n вершинами, должно быть n-1 ребро. Это справедливо и для бинарного дерева, так как оно входит в класс деревьев. А увидеть отличительные признаки бинарного дерева, можно просто зная его определение.

Деревья, виды, способы представления, структуры данных, обходы дерева

Достаточно взглянуть на рисунок 1, чтобы понять является ли изображенный на нем граф бинарным деревом.

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

Уровень

Количество вершин

0

1

1

2

2

3

3

2

Обозначим уровень символом k, а количество вершин n, тогда для бинарного дерева будет справедливо равенство n2k, т. е. количество вершин на k-ом уровне не может иметь значение большее, чем степень двойки этого уровня. Для доказательства этого достаточно построить полное дерево, все уровни которого содержат максимально возможное для двоичного дерева количество вершин:

Продолжая построение, будем получать на каждом новом уровне число вершин равное k-ой степени двойки, а их общее количество вычисляется по формуле:Для рисунка 2 формула раскрывается так: 20+21+22+23=15.

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

Выделяют четыре основных метода обхода:

  • обход в ширину;
  • прямой обход;
  • обратный обход;
  • симметричный обход;

Обход в ширину – это поуровневая обработка узлов слева на право. Работа метода заключается в просмотре всех вершин, начиная с некоторой вершины на n-ом уровне.

Возьмем нулевой уровень за начальный (рис. 2), и, начиная с вершины K, будем методом обхода в ширину поочередно двигаться вниз, просматривая вершины в следующем порядке: K A X T N H Q F U P L B J V Y.

Обход в прямом порядке вначале предполагает обработку узлов предков, а потом их потомков, то есть сначала посещается вершина дерева, далее левое и правое поддеревья, именно в описанном порядке. Для нашего дерева последовательность прямого обхода такая: K A T F U N P L X H B J Q V Y.

Обход в обратном порядке противоположен прямому обходу. Первыми осматриваются потомки, а уже затем предки, иначе говоря, первоначально обращение идет к элементам нижних уровней левого поддерева, потом то же самое с элементами правого, и в конце осматривается корень. Обратный обход дерева с рисунка 2: F U T P L N A B J H V Y Q X K.

Обход в симметричном порядке заключается в посещении левого узла, перехода в корень и оттуда в правый узел. Все для того же дерева узлы будут осмотрены в следующем порядке: F T U A P N L K B H J X V Q Y.

На практике используются не просто бинарные деревья, а их частные случаи, например, такие как двоичное дерево поиска, АВЛ-дерево, двоичная куча и другие.


Похожие записи:

Алгоритмы обхода дерева

Существуют три алгоритма обхода деревьев, которые естественно следуют из самой структуры дерева.

1. Обход слева направо: Left-Root-Right (сначала посещаем левое поддерево, затем – корень и, наконец, правое поддерево).

2. Обход сверху вниз: Root-Left-Right (посещаем корень до поддеревьев).

3. Обход снизу вверх: Left-Right-Root (посещаем корень после поддеревьев).

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

Пусть для операндов А и В выполня­ется операция сложения.

Структуры данных. Деревья

Привычная форма записи в виде А+В называется ин­фиксной. Форма записи, в которой знак операции следует перед операндами +АВ, называется префиксной, если же операция записывается после операндов АВ+ – постфиксной.

Рассмотрим небольшой пример, пусть задано выражение А+В*С. Так как умножение имеет более высокий приоритет, то данное выражение можно переписать в виде А+(В*С). Для записи выражения в постфиксной форме сначала преобразуем ту часть выражения, которая вычисляется первой, в результате получим: А+(ВС*).

Теперь запишем в постфиксной форме операцию сложения между операндами А и (ВС*): АВС*+.

Таким образом, выражение А+В*С в постфиксном виде АВС*+, префиксная форма записи будет иметь вид +*АВС.

Рассмотрим различные обходы дерева на примере формулы: ((a+b/c)*(de*f )). Дерево формируется по принципу:

– в корне размещаем операцию, которая выполнится последней;

– далее узлы-операции, операнды – листья дерева.

Обход 1 (Left-Root-Right) дает обычную инфиксную запись выражения (без скобок):

a + b / c * de * f .

Обход 2 (Root-Left-Right) – префиксную запись выражения (без скобок):

* + a / b cd * e f .

Обход 3 (Left-Right-Root) – постфиксную запись выражения:

a b c / + d e f * – * .

Функция просмотра

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

void View ( Tree *t, int level ) {

if ( t ) {

View ( t -> Right , level+1); // Вывод правого поддерева

for ( int i=0; i<level; i++) printf(" ");

printf(“ %d\n”, t -> info);

View( t -> Left , level+1); // Вывод левого поддерева

}

}

Обращение к функции View будет иметь вид View(Root, 0);

Функция View рекурсивная, вторым ее параметром является переменная, определяющая, на каком уровне (level) находится узел. Корень находится на уровне «0». Значения узлов выводятся по горизонтали так, что корень находится слева. Перед значением узла для имитации структуры дерева выводится количество пробелов, пропорциональное уровню узла. Если закомментировать цикл печати пробелов, значения ключей будут выведены просто в столбик.

Для последовательно введенных ключей 10 (корень), 25, 20, 6, 21, 8, 1, 30, будет построено дерево, вывод которого на экран с помощью функции View будет иметь следующий вид:

 


Дата добавления: 2017-10-04; просмотров: 878;


Похожие статьи:

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

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

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

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

Алгоритмы и структуры данных для начинающих: двоичное дерево поиска

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

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

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

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

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

В теории графовдерево — связный ациклический граф. Корневое дерево — это граф с вершиной, выделенной в качестве корневой.

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

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

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

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