53446

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

Доклад

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

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

Русский

2014-04-01

22.87 KB

28 чел.

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

Бинарное (Двоичное дерево поиска (англ. 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.


 

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

33641. Криптографические методы защиты информации, Контроль целостности программных и информационных ресурсов 37 KB
  Криптографические методы защиты информации Криптографические методы защиты основаны на возможности осуществления специальной операции преобразования информации которая может выполняться одним или несколькими пользователями АС обладающими некоторым секретом без знания которого с вероятностью близкой к единице за разумное время невозможно осуществить эту операцию. В классической криптографии используется только одна единица секретной информации ключ знание которого позволяет отправителю зашифровать информацию а получателю расшифровать...
33642. Защита периметра компьютерных сетей 48 KB
  В межсетевых экранах применяются специальные характерные только для данного вида средств методы защиты. Основные из них: трансляция адресов для сокрытия структуры и адресации внутренней сети; фильтрация проходящего трафика; управление списками доступа на маршрутизаторах; дополнительная идентификация и аутентификация пользователей стандартных служб на проходе; ревизия содержимого вложений информационных пакетов выявление и нейтрализация компьютерных вирусов; виртуальные частные сети для защиты потоков данных передаваемых по...
33643. Сетевые анализаторы и снифферы 63 KB
  Главный недостаток технологии Ethernet незащищенность передаваемой информации Метод доступа положенный в основу этой технологии требует от узлов подключенных к сети непрерывного прослушивания всего трафика. Узлы такой сети могут перехватывать информацию адресованную своим соседям. В общем смысле слово сниффер обозначает устройство подключенное к компьютерной сети и записывающее весь ее трафик подобно телефонным жучкам записывающим телефонные разговоры. В то же время сниффером программа запущенная на подключенном к сети узле и...
33644. Защита на канальном уровне 549.5 KB
  Технология создания защищенного виртуального канала по протоколу PPTP предусматривает как аутентификацию удаленного пользователя так и зашифрованную передачу данных. Программное обеспечение удаленного доступа реализующее PPTP может использовать любой стандарт криптографического закрытия передаваемых данных. Например сервер удаленного доступа Windows использует стандарт RC4 и в зависимости от версии 40 или 128разрядные сеансовые ключи которые генерируются на основе пароля пользователя. В протоколе PPTP определено три схемы его...
33645. ПРОТОКОЛЫ РАЗРЕШЕНИЯ АДРЕСОВ ARP 35.5 KB
  ПРОТОКОЛЫ РАЗРЕШЕНИЯ АДРЕСОВ RP. Для доставки дейтаграммы в локальной сети нужно определить физический адрес узла назначения. Именно для этого существует процедура автоматического определения физических адресов. Протокол разрешения адресов ddress Resolution Protocol RP обеспечивает метод динамической трансляции между IPадресом и соответствующим физическим адресом на основе широковещательных рассылок.
33646. Атаки на протокол ARP 38 KB
  Атаки на протокол RP Протокол разрешения адресов – RP. Функционально протокол RP состоит из двух частей. Одна часть протокола определяет физические адреса другая отвечает на запросы при определении физических адресов. Протокол RP работает различным образом в зависимости от того какой протокол канального уровня работает в данной сети протокол локальной сети Ethernet Token Ring FDDI с возможностью широковещательного доступа одновременно ко всем узлам сети или же протокол глобальной сети Х.
33647. ПРОТОКОЛ ICMP. ФОРМАТЫ СООБЩЕНИЙ ICMP 35 KB
  Если маршрутизатор обнаруживает ошибку он уничтожает дейтаграмму но одновременно с помощью ICMP отсылает сообщение об ошибке отправителю для принятия мер по ее устранению. 8бит – тип сообщение 8 бит – поле кода конкретизирует назначение сообщения 16 бит – контрольная сумма. Сообщение Получатель недостижим посылается маршрутизатором если он не может доставить IPдейтаграмму по назначению. В это сообщение включается IPзаголовок отвергнутой IPдейтаграммы и ее первые 64 бита.
33648. Атаки сетевого уровня на протокол IP и его защита 119 KB
  В качестве примера можно привести известную утилиту Nmp некоторые режимы которой позволяют задать поддельные адреса отправителя пакетов. Посылка специфических пакетов где определённым образом заполнены поля заголовка отвечающие за фрагментацию может приводить к зависанию или понижению производительности узла. Исправление этих ошибок – это установка пакетов обновления программного обеспечения. Большое число одинаковых фрагментированных пакетов вызывают замораживание машины на время атаки.
33649. Атаки на протокол ICMP и его защита 27.5 KB
  Атаки на протокол ICMP и его защита Поскольку протокол ICMP служит для передачи различных управляющих служебных сообщений поэтому всегда был популярной мишенью для атаки. Атака Sping Jolt Атака состоит в посылке нескольких дефрагментированных пакетов ICMP IСМР_ЕСНО больших размеров по частям. Для устранения уязвимости необходимо применить патч icmpfix который зависит от версии Windows NT и установленного пакета обновления. Атака ICMP Request Атака заключается в посылке пакета ICMP Subnet Msk ddress Request по адресу сетевого интерфейса...