Лабораторная работа по бинарным деревьям

Определение 1

Деревом называется конечное множество, которое состоит из элементов, называемых узлами, для которых выполняются следующие правила:

Узлы связаны отношением «исходный-порожденный».
Порожденный узел не может стать исходным для своего предка, то есть отношение действует в одну сторону.
Только один узел может не иметь исходного. Он называется корневым.
Все узлы, кроме корневого, имеют один и только один исходный.
Каждый узел может иметь неограниченное количество порожденных узлов.

Определение 2

eToro - Popular Investor

Количество порожденных узлов данного узла называется его степенью.

Определение 3

Узел с нулевой степенью (не имеющий порожденных) называют листом или концевым узлом.

Определение 4

Максимальное значение степени, найденное среди всех узлов данного дерева, называют степенью дерева.

Определение 5

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

Определение 6

Упорядоченное дерево, имеющее степень не больше, чем 2, называют бинарным деревом или двоичным деревом.

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

Пример 1

Рассмотрим следующую задачу. Дана таблица, где указаны фамилии абитуриентов и средние баллы аттестатов. Нужно найти средний балл абитуриента с фамилией Петров.

Ключом поиска в данном случае будет поле familia. При построении дерева список сначала делится пополам и корневым узлом становится ключ «Искандеров». Далее пополам делится список фамилий слева от корневого узла (ключ «Атаманова» )и справа от корневого узла (ключ «Овезова»). Узлы «Атаманова» и «Овезова» становятся порожденными для корневого узла. Далее пополам делятся списки фамилий, находящиеся слева и справа от ключей «Атаманова» и «Овезова» и т.д.

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

Проверяется равенство «Федоров»= «Искандеров». Оно ложно.
Проверяется неравенство «Федоров» > «Искандеров». Оно истино, значит поиск переносится в правое поддерево корневого узла.
Проверяется равенство «Овезова»= «Федоров». Оно ложно.
Проверяется неравенство «Федоров»> «Овезова». Оно истино, значит поиск переносится в правое поддерево узла «Овезова».
Проверяется равенство «Федоров»= «Федоров». Оно истинно, значит, поиск окончен.

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

Таким образом , при каждом переходе в новое поддерево, существенно сокращается область поиска. При прямом переборе фамилия Федоров была бы найдена за 9 шагов. При использовании поиска по дереву – за пять.

Поиск по В-дереву

Кроме поиска по бинарным деревьям часто применяется поиск по В-деревьям.

Определение 7

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

Каждый узел содержит не более 2n ключей;
Каждый узел, кроме корневого, содержит не менее n ключей;
Если внутренний узел (не являющийся листом) содержит m ключей, то у него имеется m+1 порожденных узлов.
Все листья находятся на одном уровне.

Поиск по такому дереву осуществляется следующим образом. Пусть нужно найти ключ К. Имеется узел c ключами k1,k2,…km и порожденные им узлы p0, p1,…pm

Сначала происходит поиск ключа в корневом узле. Если ключ там обнаруживается, то поиск завершается.
Если ключ К не обнаруживается в корневом узле, то происходит последовательное сравнение ключа К с ключами данного узла.
Если найдутся такие ключи ki и ki+1, что ki < K km, то поиск переносится в узел pm.
Если K < k1, то поиск переносится в узел p0.
Алгоритм повторяется сначала для выбранного узла.

Пример 2

На рисунке приведен пример В-дерева второго порядка.

Чтобы найти в этом дереве ключ 56 нужно выполнить следующий алгоритм:

Проверить утверждение 40=56. Оно ложно, поэтому поиск продолжается.
Проверить утверждение 40 < 56. Оно истино, поэтому поиск перейдет к правому порожденному узлу с ключами 50 и 60.
Последовательно проверить утверждения 50=56 и 60=56. Оба утверждения ложны, поэтому нужно искать следующий порожденный узел для поиска.
Найти ключи, между которыми находится искомый: 50 < 56 < 60. Следовательно, нужно продолжать поиск в узле, который содержит ключи большие, чем 50 и меньшие, чем 60. Это узел с ключами 52,54,56,59.
Последовательным сравнением найти ключ 56 в выбранном узле.