Сколько потомков имеет узел а

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

Узел дерева без потомков — лист, без предков — корневой узел.

Новые вопросы в Информатика

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

Допоможіть даю 30 балів 45= . бiтiв 3 кб=. бiтiв 2мБ=. бİTİB обчислення 256 КБ=. МБ 4 МБ=. КБ 614400бітів= . байтів

1.Закодуйте з використанням шифру Цезаря зі зсувом на 4 літери праворуч повідомлення: мир 20 балів

які є види ліцензій? навести до кожного виду по 2 приклади програм​

Дерево

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

Термины:

• Корневой узел — самый верхний узел дерева.
• Корень — одна из вершин, по желанию наблюдателя.
• Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов.
• Внутренний узел — любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом.
• Дерево считается ориентированным, если в корень не заходит ни одно ребро.
• Полный сцепленный ключ — идентификатор записи, который образуется путём конкатенации всех ключей экземпляров родительских записей (групп).
• M-арное дерево — число поддеревьев данного узла образует степень узла, максимальное значение m степени всех узлов дерева является степенью дерева. Дерево степени 2 называется бинарным деревом. Если в дереве на каждом уровне задан порядок следования вершин, то такое дерево называется упорядоченным

Бинарное дерево поиска

Поиск — O(log n); Вставка — O(log n); Удаление — O(log n);

Это двоичное дерево, для которого выполняются следующие условия:

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

АВЛ-Дерево

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

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

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

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

Как бинарное дерево, красно-черное обладает свойствами:

В дополнение к обычным требованиям, налагаемым на двоичные деревья поиска, к красно-чёрным деревьям применяются следующие требования:

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

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

Куча

Специализированное дерево, которая удовлетворяет *свойству кучи:*если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализации очереди с приоритетом. Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких как алгоритм Дейкстры на d-кучах и сортировка методом пирамиды.

Двои́чная ку́ча, пирами́да, или сортиру́ющее де́рево — такое двоичное дерево, для которого выполнены три условия:

• Значение в любой вершине не меньше, чем значения её потомков.
• Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.
• Последний слой заполняется слева направо без «дырок».

B-дерево

B-дерево – это структура хранения данных, являющаяся разновидностью дерева поиска. Особенностями В-деревьев является:

• сбалансированность,
• ветвистость,
• отсортированность
• логарифмическое O(log n) время работы всех стандартных операций (поиск, вставка, удаление).

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

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

Порядок(m) В-дерева – это максимальное число потомков для любого узла. Кроме узлов в дереве присутствует ещё одна сущность – ключи. Именно в них и содержится вся полезная информация. Каждый узел дерева можно представить в виде упорядоченной последовательности ”потомок1; ключ1; потомок2; ключ2; … потомок(N-1); ключ(N-1); потомокN”. Важно заметить, что ключи располагаются между ссылками на потомков и, таким образом, ключей всегда на 1 меньше. В организации В-дерева можно выделить несколько ключевых правил:

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

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

B+‍‍ дерево

B+‍‍ дерево — структура данных на основе B-дерева, сбалансированное n-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B+‍‍ дерево состоит из корня, внутренних узлов и листьев, корень может быть либо листом, либо узлом с двумя и более потомками.

Изначально структура предназначалась для хранения данных в целях эффективного поиска в блочно-ориентированной среде хранения — в частности, для файловых систем; применение связано с тем, что в отличие от бинарных деревьев поиска, B+‍‍ деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка 100 или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве.

Построение B+‍‍-дерева может требовать перестройки промежуточной структуры, это связано с тем, что количество ключей в каждом узле (кроме корня) должно быть от t до 2t, где t — степень (или порядок) дерева. При попытке вставить в узел 2t+1-й ключ возникает необходимость разделить этот узел, в качестве ключа-разделителя сформированных ветвей выступает t+1-й ключ, который помещается на соседний ярус дерева. Особым же случаем является разделение корня, так как в этом случае увеличивается число ярусов дерева. Особенностью разделения листа B+‍‍-дерева является то, что он делится на неравные части. При разделении внутреннего узла или корня возникают узлы с равным числом ключей k. Разделение листа может вызвать «цепную реакцию» деления узлов, заканчивающуюся в корне.

Свойства структуры:

• Легко реализуется независимость программы от структуры информационной записи.
• Поиск обязательно заканчивается в листе.
• Удаление ключа имеет преимущество — удаление всегда происходит из листа.
• Другие операции выполняются аналогично B-деревьям.
• B+‍‍ деревья требуют больше памяти для представления, чем классические B-деревья.
• B+‍‍ деревья имеют возможность последовательного доступа к ключам.

B* дерево

B* дерево — разновидность B дерева, в которой каждый узел дерева заполнен не менее чем на ⅔ (в отличие от B-дерева, где этот показатель составляет 1/2). B+ дерево, удовлетворяющее таким требованиям называется B+* деревом.

B* дерево относительно компактнее, так как каждый узел используется полнее. В остальном же этот вид деревьев не отличается от простого B дерева.

Для выполнения требования «заполненность узла не менее 2/3», приходится отказываться от простой процедуры разделения переполненного узла. Вместо этого происходит «переливание» в соседний узел. Если же и соседний узел заполнен, то ключи приблизительно поровну разделяются на 3 новых узла.

LSM Дерево

LSM-дерево (Log-structured merge-tree — журнально-структурированное дерево со слиянием) — используемая во многих СУБД структура данных, предоставляющая быстрый доступ по индексу в условиях частых запросов на вставку (например, при хранении журналов транзакций). LSM-деревья, как и другие деревья, хранят пары «ключ — значение». LSM-дерево поддерживает две или более различные структуры, каждая из которых оптимизирована под устройство, в котором она будет храниться. Синхронизация между этими структурами происходит блоками.

Принцип работы

Простая версия LSM-дерева — двухуровневое дерево — состоит из двух древоподобных структур C0 и C1. C0 меньше по размеру и хранится целиком в оперативной памяти, а C1 находится в энергонезависимой памяти. Новые записи вставляются в C0. Если после вставки размер C0 превышает некоторое заданное пороговое значение, непрерывный сегмент удаляется из C0 и сливается с C1 на устройстве постоянного хранения. Хорошая производительность достигается за счёт того, что деревья оптимизированы под своё хранилище, а слияние осуществляется эффективно и группами по нескольку записей, используя алгоритм, напоминающий сортировку слиянием.

Большинство LSM-деревьев, используемых на практике, реализует несколько уровней. Уровень 0 (назовём его MemTable) хранится в оперативной памяти и может быть представлен обычным деревом. Данные на устройствах постоянного хранения хранятся в виде отсортированных по ключу таблиц (SSTable). Таблица может храниться в виде отдельного файла или набора файлов с непересекающимися значениями ключей. Для поиска конкретного ключа нужно проверить его наличие в MemTable, а затем — пройти по всем SSTable на устройстве постоянного хранения.

Схема работы с LSM-деревом:

• индексы SSTable всегда загружены в оперативную память;
• запись производится в MemTable;
• при чтении сначала проверяется MemTable, а затем, если надо, — SSTable на устройстве постоянного хранения;
• периодически MemTable сбрасывается в энергонезависимую память для постоянного хранения в виде SSTable;
• периодически SSTable на устройствах постоянного хранения сливаются.

Искомый ключ может появиться сразу в нескольких таблицах на устройствах постоянного хранения, и итоговый ответ зависит от программы. Большинству приложений нужно лишь последнее значение, относящееся к данному ключу. Другие, например Apache Cassandra, в которой каждое значение представляет собой строку базы данных (а строка может иметь разное количество столбцов в разных таблицах с устройств постоянного хранения), вынуждены как-либо обрабатывать все имеющиеся значения, чтобы получить корректный результат. Чтобы сократить время выполнения запросов, на практике стараются избегать ситуации со слишком большим количеством таблиц на устройствах постоянного хранения.

Были разработаны расширения к «уровневому» методу для поддержания B+‍-структур, например, bLSM[2] и Diff-Index.[3]

Время работы

Архитектура LSM-дерева позволяет удовлетворить запрос на чтение либо из оперативной памяти, либо за одно обращение к устройствам постоянного хранения. Запись тоже всегда быстра независимо от размеров хранилища.

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

R-дерево

R-дерево (R-trees) — древовидная структура данных (дерево). Она подобна B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами (широтой и долготой). Типичным запросом с использованием R-деревьев мог бы быть такой: «Найти все музеи в пределах 2 километров от моего текущего местоположения».

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

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

Аналогично, алгоритмы поиска (например, пересечение, включение, окрестности) используют ограничивающие прямоугольники для принятия решения о необходимости поиска в дочерней вершине. Таким образом, большинство вершин никогда не затрагиваются в ходе поиска. Как и в случае с B-деревьями, это свойство R-деревьев обусловливает их применимость для баз данных, где вершины могут выгружаться на диск по мере необходимости.

Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: квадратичные и линейные.

Структура R-дерева

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

• MaxEntries — максимальное число детей у вершины
• MinEntries — минимальное число детей у вершины, за исключением корня.

§ 43. Деревья

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

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

Из двух связанных узлов тот, который находится на более вы­соком уровне, называется родителем, а другой — сыном. Ко­рень — это единственный узел, у которого нет родителя; у листьев нет сыновей.

Используются также понятия «предок» и «потомок». Пото­мок какого-то узла — это узел, в который можно перейти пострелкам от узла-предка. Соответствен­но, предок какого-то узла — это узел, из которого можно перейти по стрел­кам в данный узел.

В дереве на рис. 6.11 родитель узла Е — это узел В, а предки узла Е — это узлы А и В, для которых узел Е — по­ томок. Потомками узла А (корня дерева) являются все остальные узлы.

Высота дерева — это наибольшее расстояние (количество дуг) от корня до листа. Высота дерева, приведённого на рис. 6.11, равна 2.
Формально дерево можно определить следующим образом:

1. пустая структура — это дерево;
2. дерево — это корень и несколько связанных с ним отдельных
   (не связанных между собой) деревьев.

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

Деревья широко применяются в следующих задачах:

• поиск в большом массиве не меняющихся данных;
• сортировка данных;
• вычисление арифметических выражений;
• оптимальное кодирование данных (метод сжатия Хаффмана).

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

Значения, связанные с узлами дерева, по которым выполняется поиск, называются ключами этих узлов (кроме ключа узел может содержать множество других данных). Перечислим важные свой­ства дерева, показанного на рис. 6.12:

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

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

Например, пусть нужно найти узел, ключ которого равен 4. Начинаем поиск по дереву с корня. Ключ корня — 6 (больше за­данного), поэтому дальше нужно искать только в левом поддереве и т. д. Если при линейном поиске в массиве за одно сравнение от­секается 1 элемент, здесь — сразу примерно половина оставших­ся. Количество операций сравнения в этом случае пропорциональ­но \og₂N, т. е. алгоритм имеет асимптотическую сложность O(log_aJV). Конечно, нужно учитывать, что предварительно дерево должно быть построено. Поэтому такой алгоритм выгодно приме­нять в тех случаях, когда данные меняются редко, а поиск вы­полняется часто (например, в базах данных).

Обход двоичного дерева

Обойти дерево — это значит «посетить» все узлы по одному разу. Если перечислить узлы в порядке их посещения, мы пред­ставим данные в виде списка.

Существуют несколько способов обхода дерева:

• КЛП — «корень — левый — правый» (обход в прямом порядке):

посетить корень обойти левое поддерево обойти правое поддерево

• ЛКП — «левый — корень — правый» (симметричный обход):
обойти левое поддерево

обойти правое поддерево

• ЛПК — «левый — правый — корень» (обход в обратном по­
рядке):

обойти левое поддерево обойти правое поддерево посетить корень

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

Рассмотрим дерево, которое может быть составлено для вычис­ления арифметического выражения (1 + 4) * (9 — 5) (рис. 6.13).

Выражение вычисляется по такому дереву снизу вверх, т. е. посе­щение корня дерева — это последняя выполняемая операция.

Различные типы обхода дают последовательность узлов:

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

Обход КЛП называется «обходом в глубину», потому что сна­чала мы идём вглубь дерева по левым поддеревьям, пока не дойдём до листа. Такой обход можно выполнить с помощью стека следующим образом:

записать в стек корень дерева

нц пока стек не пуст

выбрать узел V с вершины стека

посетить узел V

если у узла V есть правый сын то

добавить в стек правого сына V

все

если у узла V есть левый сын то

добавить в стек левого сына V

все

кц

На рисунке 6.14 показано изменение состояния стека при та­ком обходе дерева, изображенного на рис. 6.13. Под стеком запи­сана метка узла, который посещается (например, данные из этого узла выводятся на экран).

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

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

записать в очередь корень дерева нц пока очередь не пуста

выбрать первый узел V из очереди

посетить узел V

если у узла V есть левый сын то добавить в очередь левого сына V

все

если у узла V есть правый сын то добавить в очередь правого сына V

все

кц

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

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

Для простоты будем рассматривать только арифметические выражения, содержащие числа и знаки четырёх арифметических операций: + — * /. Построим дерево для выражения

Нужно сначала найти последнюю операцию, просматривая выражение слева направо. Здесь последняя операция — это вто­рое вычитание, оно оказывается в корне дерева (рис. 6.15).

Как выполнить этот поиск в программе? Известно, что операции выполняются в порядке приоритета (старшинства): сначала опе­рации с более высоким приоритетом (слева направо), потом — с более низким (также слева направо). Отсюда следует важный вывод.

В корень дерева нужно поместить поспеднюю из операций с наименьшим приоритетом.

Теперь нужно построить таким же способом лез поддеревья (рис. 6.16).

Эта процедура рекурсивная, её можно записать в виде псевдокода:

найти последнюю выполняемую операцию

если операций нет то

все

поместить найденную операцию в корень дерева

построить левое поддерево

построить правое поддерево

Рекурсия заканчивается, когда в оставшейся части строки нет ни одной операции, значит, там находится число (это лист дерева).

Теперь вычислим выражение по дереву. Если в корне нахо­дится знак операции, её нужно применить к результатам вычис­ления поддеревьев:

nl:=значение левого поддерева

п2:=значение правого поддерева

Снова получился рекурсивный алгоритм.

Возможен особый случай (на нём заканчивается рекурсия), когда корень дерева содержит число (т. е. это лист). Это число и будет результатом вычисления выражения.

Использование связанных структур

Поскольку двоичное дерево — это нелинейная структура дан­ных, использовать динамический массив для размещения элемен­тов не очень удобно (хотя возможно). Вместо этого будем исполь­зовать связанные узлы. Каждый такой узел — это структура, со­держащая три области: область данных, ссылка на левое поддерево (указатель) и ссылка на правое поддерево (второй ука­затель). У листьев нет сыновей, в этом случае в указатели будем записывать значение nil (нулевой указатель). Дерево, состоящее из трёх таких узлов, показано на рис. 6.18.

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

Введём два новых типа: TNode — узел дерева, и PNode — указатель (ссылку) на такой узел:

type
PNode = «TNode;

left, right: PNode

end;

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

Как программа определяет, сколько памяти нужно выделить? Чтобы ответить на этот вопрос, вспомним, что указатель р указы-вает на структуру типа TNode, размер которой и определяет раз-мер выделяемого блока памяти.
Для освобождения памяти служит процедура Dispose (англ. dispose — ликвидировать):

Dispose(p);
В основной программе объявим одну переменную типа PNode — это будет ссылка на корень дерева:
var T: PNode;
Вычисление выражения сводится к двум вызовам функций:

T:=Tree(s);
writeIn(‘Результат: ‘, Calc (Т) ) ;

Здесь предполагается, что арифметическое выражение записано в символьной строке s, функция Tree строит в памяти дерево по этой строке, а функция Calc — вычисляет значение выражения по готовому дереву.

При построении дерева нужно выделять в памяти новый узел и искать последнюю выполняемую операцию — это будет делать функция LastOp. Она возвращает О, если ни одной операции не обнаружено, в этом случае создаётся лист — узел без потомков. Если операция найдена, её обозначение записывается в поле data, а в указатели записываются адреса поддеревьев, которые строятся рекурсивно для левой и правой частей выражения:

function Tree(s: string): PNode;

var k: integer;

New(Tree); (выделить память>

if k=0 then begin

end

else begin

Тгее Л .right:=Tree(Copy(s,k+1,Length(s)-k))

end

end;

Функция Calc тоже будет рекурсивной:
function Calc(Tree: PNode) : integer,
var nl, n2, res: integer;
begin
if Tree-4, left = nil then
Val(Tree».data, Calc, res) else begin
nl:=Calc(ТгееЛ.left);

case Tree^.data[1] of

else Calc:=MaxInt end

end;
Если ссылка, переданная функции, указывает на лист (нет левого поддерева), то значение выражения — это результат преобразова-ния числа из символьной формы в числовую (с помощью процеду¬ры Val). В противном случае вычисляются значения для левого и правого поддеревьев и к ним применяется операция, указанная в корне дерева. В случае ошибки (неизвестной операции) функ¬ция возвращает значение Maxlnt — максимальное целое число.
Осталось написать функцию LastOp, Нужно найти в символь-ной строке последнюю операцию с минимальным приоритетом. Для этого составим функцию, возвращающую приоритет опера¬ции (переданного ей символа):
function Priority(op: char): integer;

begin
case op of

‘+’,’-‘: Priority:=1;
‘*’,’/’: Priority:=2;
else Priority:=100
end
end;
Сложение и вычитание имеют приоритет 1, умножение и деле¬ние — приоритет 2, а все остальные символы (не операции) — приоритет 100 (условное значение).

Функция LastOp может выглядеть так:

function LastOp(s: string): integer;

var 1, minPrt: integer;

for i:=l to Length(s) do

end

end;

Обратите внимание, что в условном операторе указано нестрогое неравенство, чтобы найти именно последнюю операцию с наи­меньшим приоритетом. Начальное значение переменной minPrt можно выбрать любое между наибольшим приоритетом операций (2) и условным кодом не-операции (100). Тогда если найдена лю­бая операция, условный оператор срабатывает, а если в строке нет операций, условие всегда ложно и в переменной LastOp оста­ется начальное значение 0.

Хранение двоичного дерева в массиве

Двоичные деревья можно хранить в (динамическом) массиве почти так же, как и списки. Вопрос о том, как сохранить струк­туру (взаимосвязь узлов), решается следующим образом. Если нумерация элементов массива А начинается с 1, то сыновья эле­мента A[i] — это A[Z*i] и AJS4+1>. На рисунке 6.19 показан по­рядок расположения элементов в массиве для дерева, соответ­ствующего выражению

Алгоритм вычисления выражения остаётся прежним, изменяется только метод хранения данных. Обратите внимание, что некото­рые элементы остались пустыми, это значит, что их родитель — лист дерева.

Сколько потомков имеет узел а

По книге Laszlo
«Вычислительная геометрия и компьютерная графика на С++»

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

Рис. 1: Двоичное дерево с показанными внешними узллами (а) и без них (б)

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

Основанная на генеалогии метафора дает удобный способ обозначения узлов внутри двоичного дерева. Узел р является родителем (или предком) узла n, если n — потомок узла р. Два узла являются братьями, если они принадлежат одному и тому же родителю. Для двух заданных узлов n₁ и n_k таких, что узел n_k принадлежит поддереву с корнем в узле n₁, говорят, что узел n_k является потомком узла n₁, а узел n₁ — предком узла n_k. Существует уникальный путь от узла n₁ вниз к каждому из потомков n_k, a именно: последовательность узлов n₁ и n₂. n_k такая, что узел n_i является родителем узла n_i+1 для i = 1, 2. k-1. Длина пути равна числу ребер (k-1), содержащихся в нем. Например, на рис. 1а уникальный путь от узла А к узлу D состоит из последовательности А, В, D и имеет длину 2.

Глубина узла n определяется рекурсивно:

< 0	если n — корневой узел
глубина (n) =
< 1 + глубина (родителя (n))	в противном случае

Глубина узла равна длине уникального пути от корня к узлу. На рис. 1а узел А имеет глубину 0, а узел D имеет глубину, равную 2.

Высота узла n также определяется рекурсивно:

< 0	если n — внешний узел
высота (n) =
< 1 + max( высота(лев(n)), высота(прав(n)) )	в противном случае

где через лев(n) обозначен левый потомок узла n и через прав(n) — правый потомок узла n. Высота узла n равна длине самого длинного пути от узла n вниз до внешнего узла поддерева n. Высота двоичного дерева определяется как высота его корневого узла. Например, двоичное дерево на рис. 1а имеет высоту 3, а узел D имеет высоту 1.

При реализации двоичных деревьев, основанной на точечном представлении, узлы являются объектами класса TreeNode.

template class TreeNode < protected: TreeNode *_lchild; TreeNode *_rchild; Т val; public: TreeNode(T); virtual ~TreeNode(void); friend class SearchTree; // возможные пополнения friend class BraidedSearchTree; // структуры >;

Элементы данных _lchild и _rchild обозначают связи текущего узла с левым и правым потомками соответственно, а элемент данных val содержит сам элемент.

Конструктор класса формирует двоичное дерево единичного размера — единственный внутренний узел имеет два пустых потомка, каждое из которых представлено нулем NULL:

template TreeNode::TreeNode(T v) : val(v), _lchild(NULL), _rchild (NULL)

Деструктор ~TreeNode рекурсивно удаляет оба потомка текущего узла (если они существуют) перед уничтожением самого текущего узла:

template TreeNode::~TreeNode(void)

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

Рис. 2: Три двоичных дерева поиска с одним и тем же набором элементов

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

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

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

Определим шаблон нового класса SearchTree для представления двоичного дерева поиска. Класс содержит элемент данных root, который указывает на корень двоичного дерева поиска (объект класса TreeNode) и элемент данных cmp, который указывает на функцию сравнения.

template class SearchTree < private: TreeNode *root; int (*) (T,T) cmp; TreeNode*_findMin(TreeNode *); void _remove(T, TreeNode * &); void _inorder(TreeNode *, void (*) (T) ); public: SearchTree (int(*) (Т, Т) ); ~SearchTree (void); int isEmpty (void); Т find(T); Т findMin(void); void inorder (void(*) (T) ); void insert(T); void remove(T); T removeMin (void); >;

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

Конструкторы и деструкторы

Конструктор SearchTree инициализирует элементы данных cmp для функции сравнения и root для пустого дерева поиска:

template SearchTree::SearchTree (int (*с) (Т, Т) ) : cmp(с), root (NULL)

Дерево поиска пусто только, если в элементе данных root содержится нуль (NULL) вместо разрешенного указателя:

template int SearchTree::isEmpty (void)

Деструктор удаляет все дерево путем обращения к деструктору корня:

template SearchTree::~SearchTree (void)

Поиск

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

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

template T SearchTree::find (T val) < TreeNode *n = root; while (n) < int result = (*cmp) (val, n->val); if (result < 0) n = n->_lchild; else if (result > 0) n = n->_rchild; else return n->val; > return NULL; >

Этот алгоритм поиска можно сравнить с турниром, в котором участвуют некоторые кандидаты. В начале, когда мы начинаем с корня, в состав кандидатов входят все элементы в дереве поиска. В общем случае для каждого узла n в состав кандидатов входят все потомки n. На каждом этапе производится сравнение val с n->val. Если val меньше, чем n->val, то состав кандидатов сужается до элементов, находящихся в левом поддереве, а элементы в правом поддереве n, как и сам элемент n->val, исключаются из соревнования. Аналогичным образом, если val больше, чем n->val, то состав кандидатов сужается до правого поддерева n. Процесс продолжается до тех пор, пока не будет обнаружен элемент val или не останется ни одного кандидата, что означает, что элемент val не существует в дереве поиска.

Для нахождения наименьшего элемента мы начинаем с корня и прослеживаем связи с левым потомком до тех пор, пока не достигнем узла n, левый потомок которого пуст — это означает, что в узле n содержится наименьший элемент. Этот процесс также можно уподобить турниру. Для каждого узла n состав кандидатов определяется потомками узла n. На каждом шаге из состава кандидатов удаляются те элементы, которые больше или равны n->val и левый потомок n будет теперь выступать в качестве нового n. Процесс продолжается до тех пор, пока не будет достигнут некоторый узел n с пустым левым потомком и, полагая, что не осталось кандидатов меньше, чем n->val, и будет возвращено значение n->val.

Компонентная функция findMin возвращает наименьший элемент в данном дереве поиска, в ней происходит обращение к компонентной функции _findMin, которая реализует описанный ранее алгоритм поиска, начиная с узла n :

template T SearchTree::findMin (void) < TreeNode*n = _findMin (root); return (n ? n->val : NULL); > template TreeNode *SearchTree::_findMin (TreeNode *n) < if (n == NULL) return NULL; while (n->_lchild) n = n->_lchild; return n; >

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

Симметричный обход

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

Компонентная функция inorder служит в качестве ведущей функции. Она обращается к собственной компонентной функции _inorder, которая выполняет симметричный обход от узла n и применяет функцию visit к каждому достигнутому узлу.

template void SearchTree::inorder (void (*visit) (Т) ) < _inorder (root, visit); >template void SearchTree::inorder (TreeNode *n, void(*visit) (T) < if (n) < _inorder (n->_lchild, visit); (*visit) (n->val); _inorder (n->_rchild, visit); > >

При симметричном обходе каждого из двоичных деревьев поиска, показанных на рис. 2, узлы посещаются в возрастающем порядке: 2, 3, 5, 7, 8. Конечно, при симметричном обходе любого двоичного дерева поиска все его элементы посещаются в возрастающем порядке. Чтобы выяснить, почему это так, заметим, что при выполнении симметричного обхода в некотором узле n элементы меньше, чем n->val посещаются до n, поскольку они принадлежат к левому поддереву n, а элементы больше, чем n->val посещаются после n, поскольку они принадлежат правому поддереву n. Следовательно, узел n посещается в правильной последовательности. Поскольку n — произвольный узел, то это же правило соблюдается для каждого узла.

Компонентная функция inorder обеспечивает способ перечисления элементов двоичного дерева поиска в отсортированном порядке. Например, если а является деревом поиска SearchTree для строк, то эти строки можем напечатать в лексикографическом порядке одной командой а.inorder(printstring). Для этого функция обращения printstring может быть определена как:

void printstring(char *s)

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

Включение элементов

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

Компонентная функция insert включает элемент val в это двоичное дерево поиска:

Рис. 3: Включение элемента в двоичное дерево поиска

template void SearchTree::insert(T val) < if (root == NULL) < root = new TreeNode(val); return; > else < int result; TreeNode*p, *n = root; while (n) < p = n; result = (*cmp) (val, p->val); if (result < 0) n = p->_lchild; else if (result > 0) n = p->_rchild; else return; > if (result < 0) p->_lchild = new TreeNode(val); else p-> rchild = new TreeNode(val); > >

Удаление элементов

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

Рис. 4: Три ситуации, возникающие при удалении элемента из двоичного дерева поиска

Чтобы удалить элемент из дерева поиска, вначале мы отслеживаем путь поиска элемента, начиная с корня и вниз до узла n, содержащего элемент. В этот момент могут возникнуть три ситуации, показанные на рис. 4:

1. Узел n имеет пустой левый потомок. В этом случае ссылка на n (записанная в предке n, если он есть) заменяется на ссылку на правого потомка n.
2. У узла n есть непустой левый потомок, но правый потомок пустой. В этом случае ссылка вниз на n заменяется ссылкой на левый потомок узла n.
3. Узел n имеет два непустых потомка. Найдем последователя для n (назовем его m), скопируем данные, хранящиеся в m, в узел n и затем рекурсивно удалим узел m из дерева поиска.

Очень важно проследить, как будет выглядеть результирующее двоичное дерево поиска в каждом случае. Рассмотрим случай 1. Если подлежащий удалению узел n, является левым потомком, то элементы, относящиеся к правому поддереву n будут меньше, чем у узла р, предка узла n. При удалении узла n его правое поддерево связывается с узлом р и элементы, хранящиеся в новом левом поддереве узла р конечно остаются меньше элемента в узле р. Поскольку никакие другие ссылки не изменяются, то дерево остается двоичным деревом поиска. Аргументы остаются подобными, если узел n является правым потомком, и они тривиальны, если n — корневой узел. Случай 2 объясняется аналогично. В случае 3 элемент v, записанный в узле n, перекрывается следующим большим элементом, хранящимся в узле m (назовем его w), после чего элемент w удаляется из дерева. В получающемся после этого двоичном дереве значения в левом поддереве узла n будут меньше w, поскольку они меньше v. Более того, элементы в правом поддереве узла n больше, чем w, поскольку (1) они больше, чем v, (2) нет ни одного элемента двоичного дерева поиска, лежащего между v и w и (3) из них элемент w был удален.

Заметим, что в случае 3 узел m должен обязательно существовать, поскольку правое поддерево узла n непустое. Более того, рекурсивный вызов для удаления m не может привести к срыву рекурсивного вызова, поскольку если узел m не имел бы левого потомка, то был бы применен случай 1, когда его нужно было бы удалить.

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

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

Рис. 5: Последовательность операций удаления элемента: (а) и (б) — Случай 1: удаление из двоичного дерева элемента 8; (б) и (в) — Случай 2: удаление элемента 5; (в) и (г) — Случай 3: удаление элемента 3

template void SearchTree::remove(Т val) < _remove(val, root); >template void SearchTree::_remove(Т val, TreeNode * &n) < if (n == NULL) return; int result = (*cmp) (val, n->val); if (result < 0) _remove(val, n->_lchild); else if (result > 0) _remove (val, n->_rchild); else < // случай 1 if (n->_lchild == NULL) < TreeNode*old = n; n = old->_rchild; delete old; > else if (n->_rchild == NULL < // случай 2 TreeNode *old = n; n = old->_lchild; delete old; > else < // случай 3 TreeNode *m = _findMin(n->_rchild); n->val = m->val; remove(m->val, n->_rchild); > > >

Параметр n (типа ссылки) служит в качестве псевдонима для поля ссылки, которое содержит ссылку вниз на текущий узел. При достижении узла, подлежащего удалению (old), n обозначает поле ссылки (в предке узла old), содержащее ссылку вниз на old. Следовательно команда n=old->_rchild заменяет ссылку на old ссылкой на правого потомка узла old.

Компонентная функция removeMin удаляет из дерева поиска наименьший элемент и возвращает его:

template Т SearchTree::removeMin (void)

Древовидная сортировка — способ сортировки массива элементов — реализуется в виде простой программы, использующей деревья поиска. Идея заключается в занесении всех элементов в дерево поиска и затем в интерактивном удалении наименьшего элемента до тех пор, пока не будут удалены все элементы. Программа heapSort(пирамидальная сортировка) сортирует массив s из n элементов, используя функцию сравнения cmp:

template void heapSort (T s[], int n, int(*cmp) (T,T) ) < SearchTreet(cmp); for (int i = 0; i

Также доступна реализация двоичного дерева на Си с базовыми функциями. Операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в дереве. Каждый узел Node содержит указатели left, right на левого и правого потомков, а также указатель parent на предка. Собственно данные хранятся в поле data. Адрес узла, являющегося корнем дерева хранится в укзателе root, значение которого в самом начале, естественно, NULL. Функция insertNode запрашивает память под новый узел и вставляет узел в дерево, т.е. устанавливает нужные значения нужных указателей. Функция deleteNode, напротив, удаляет узел из дерева (т.е. устанавливает нужные значения нужных указателей), а затем освобождает память, которую занимал узел. Функция findNode ищет в дереве узел, содержащий заданное значение.