53446

Операции над бинарными деревьями

Доклад

Информатика, кибернетика и программирование

Бинарное (Двоичное дерево поиска (англ. binary search tree, BST)) дерево - это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества

Русский

2014-04-01

22.87 KB

34 чел.

Операции над бинарными деревьями.

Бинарное (Двоичное дерево поиска (англ. binary search tree, BST)) дерево - это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются правым и левым поддеревьями исходного дерева.

На рисунке показан наиболее часто встречающийся способ представления бинарного дерева. Оно состоит из девяти узлов. Корнем дерева является узел А. Левое поддерево имеет корень В, а правое поддерево - корень С. Они соединяются соответствующими ветвями, исходящими из А. Отсутствие ветви означает пустое поддерево. Например, у поддерева с корнем С нет левого поддерева, оно пусто. Пусто и правое поддерево с корнем Е. Бинарные поддеревья с корнями D, G, H и I имеют пустые левые и правые поддеревья. Узел, имеющий пустые правое и левое поддеревья, называется листом. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правое и левое поддеревья, то дерево называется строго бинарным. Уровень узла в бинарном дереве определяется следующим образом: уровень корня всегда равен нулю, а далее номера уровней при движении по дереву от корня увеличиваются на 1 по отношению к своему непосредственному предку. Глубина бинарного дерева - это максимальный уровень листа дерева, иначе говоря, длина самого длинного пути от корня к листу дерева.

Номер корня всегда равен 1, левый потомок получает номер 2, правый - номер 3. Левый потомок узла 2 должен получить номер 4, а правый - 5, левый потомок узла 3 получит номер 6, правый - 7 и т.д. Несуществующие узлы не нумеруются, что, однако, не нарушает указанного порядка, так как их номера не используются. При такой системе нумерации в дереве каждый узел получает уникальный номер.

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

Почти полное бинарное дерево определяется как бинарное дерево, для которого существует неотрицательное целое k такое, что:

1) каждый лист в дереве имеет уровень k или k+1;

2) если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1.Итак, какие же основные операции определены над деревом? Их несколько:

Поиск узла с заданным ключом. Добавление нового узла. Удаление узла (поддерева). Обход дерева в определенном порядке: Нисходящий обход.

Восходящий обход. Смешанный обход. Поиск глубины.

Бинарное дерево поиска предусматривает операции поиска, вставки и удаления элементов по ключу. Используя эти операции можно построить любое бинарное дерево. Операции вставки, удаления и поиска элементов для бинарного дерева используют правило двоичного поиска при доступе к элементу с заданным значением ключа. Необходимо отметить структурную зависимость бинарного дерева от порядка поступления и удаления элементов. Например, при последовательных вставках элементов со строго возрастающими ключами, структура бинарного дерева выродится в линейный список правых сыновей. Важной операцией для бинарного дерева является перебор его элементов в определенном порядке для выполнения какой–либо операции. Также для BST - дерева используются ряд вспомогательных операций, позволяющих воспроизводить операции, характерные для упорядоченных таблиц поиска: доступ к k - му элементу, поиск следующего или предыдущего по ключу элемента, разбиение таблицы на две части, объединение двух таблиц в одну и другие.

Наиболее часто к бинарным деревьям применяют следующие операции (функции). Если Р указатель на узел U, то: Info(P) - возвращает содержимое узла с указателем Р;

Left(P) - возвращает указатель на левого сына узла с указателем Р;

Right(P) - возвращает указатель на правого сына;

Father(P) - возвращает указатель на отца узла с указателем Р;

Brother(P) - возвращает указатель на брата узла с указателем Р;

IsLeft(P) - возвращает true, если узел с указателем Р - левый сын;

IsRight(P) - возвращает true, если узел с указателем Р - правый сын.

HasChildren (P) - возвращает true, если у узла с указателем P есть потомки;

При создании бинарных деревьев используют функции: MakeTree(X) - создает новое бинарное дерево, состоящее из одного узла с информационным полем Х и возвращает указатель этого узла.

SetLeft(P, X) - где Р - указатель узла U, не имеющего левого сына. Создает новый левый сын узла U с информационным полем Х.

SetRight(P, X) - для правого узла, по аналогии с SetLeft.


 

А также другие работы, которые могут Вас заинтересовать

32713. ПРОБЛЕМЫ ЭКОЛГИЗАЦИИ ТЕХНОЛОГИИ В НЕФТЕПЕРЕРАБОТКЕ 104 KB
  Вначале человек не задумывался о том, что таит в себе интенсивная добыча нефти и газа. Главным было выкачать их как можно больше. Так и поступали. Но вот в начале 40-х гг. текущего столетия появились первые настораживающие симптомы.
32714. ПРОБЛЕМЫ ОБЕСПЕЧЕНИЯ БАНКОВСКИХ КРЕДИТОВ И ПУТИ РАЗВИТИЯ ФОРМ ВОЗВРАТНОСТИ КРЕДИТА 670.5 KB
  Рассмотреть наиболее часто используемые формы обеспечения возвратности кредитов: залог, уступка требований (цессия) и передача права собственности, гарантии и поручительства и др.; на примере ОАО «Сбербанк» получить представление о возможностях банка по возврату кредитов.
32715. ЭКОНОМЕТРИЧЕСКИЕ ИССЛЕДОВАНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ПАССАЖИРООБОРОТА ЖЕЛЕЗНОДОРОЖНЫХ ПЕРЕВОЗОК ОТ ДЛИНЫ ДОРОГИ 336 KB
  В конце прошлого столетия разработаны и широко применяется для решения большого числа практических задач экономики математические модели, в основу которых положены уравнения регрессии. В настоящей курсовой работе стоит задача обосновать математическую модель пассажирооборота железнодорожных перевозок
32716. Сердечные гликозиды, Механизм кардиотонического действия 94 KB
  Сердечные гликозиды вещества растительного происхождения которые оказывают высокоизбирательное кардиотоническое действие. Исследования зависимости между структурой и действием этих средств показали что лактонное кольцо и стероидное ядро в равной мере необходимы для проявления активности. Действие на сердце. Систолическое действие инотропное Усиление и укорочение систолы.
32717. АНТИАРИТМИЧЕСКИЕ СРЕДСТВА 123 KB
  Антиаритмический эффект проявляют так же вещества действие которых направлено на эфферентную иннервацию сердца. Поэтому в механизме действия ААС ведущую роль играет их действие на клеточные мембраны транспорт ионов N K C и взаимосвязанные с этим изменения мембранного потенциала кардиомиоцитов. Препараты могут угнетать сократимость обладать умеренным Мхолинолитическим действием устранение влияния вагуса может способствовать распространению предсердной аритмии на желудочки. Влияет на все отделы проводящей системы сердца угнетает...
32718. АНТИАНГИНАЛЬНЫЕ СРЕДСТВА 118.5 KB
  ngin pectoris грудная жаба лекарственные средства применяемые для купирования и предупреждения приступов стенокардии и лечения других проявлений коронарной недостаточности при ишемической болезни сердца включая безболевую форму. При всех видах стенокардии возникает несоответствие между кровоснабжением миокарда и его потребностью в кислороде. Средства понижающие потребность миокарда в кислороде и повышающие доставку кислорода а нитраты Препараты нитроглицерина Для применения в медицинской практике нитроглицерин выпускают в виде готовых...
32719. ЛЕКАРСТВЕННЫЕ СРЕДСТВА ДЛЯ ЛЕЧЕНИЯ АТЕРОСКЛЕРОЗА (ГИПОЛИПИДЕМИЧЕСКИЕ СРЕДСТВА) 105.5 KB
  Ведущая роль отводится высокому содержанию холестерина в липопротеинах низкой плотности участвующих в образовании дестабилизации атеросклеротических бляшек и тромбогенезе. Цель их использования заключается в понижении концентрации в крови атерогенных липопротеидов липопротеидов низкой плотности ЛПНП липопротеидов очень низкой плотности ЛПОНП и холестерина ХС а также повышении концентрации антиатерогенных липопротеидов высокой плотности ЛПВП. Лекарственные средства как правило имеют несколько механизмов действия один из которых...
32720. АНТИГИПЕРТЕНЗИВНЫЕ СРЕДСТВА 130.5 KB
  Их антигипертензивное действие связано со стимуляцией центральных α2адренорецепторов расположенных в нейронах продолговатого мозга и вазомоторных центрах ствола мозга. Оказывает быстрое и выраженное гипотензивное действие. Кроме влияния на ССС клофелин оказывает значительное седативное действие обладает анальгезирующим действием может уменьшать выраженность абстинентного синдрома. Побочное действие: сонливость вялость усталость диспепсия запоры сухость во рту головные боли брадикардия нарушение сна тремор кожные реакции.
32721. Вивчення універсального вимірювача Е7-11 при вимірюваннях індуктивності, ємності, опору, тангенса кута втрат й добротності елементів 404.5 KB
  Вивчення універсального вимірювача Е7-11 при вимірюваннях індуктивності, ємності, опору, тангенса кута втрат й добротності елементів.