Бинарное дерево. Основные определения и понятия. Бинарный поиск по дереву. Формирование бинарного дерева этим методом
Бинарное (двоичное) дерево (binary tree) – древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Бинарное дерево [др. источник] – это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла. Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева. Узел дерева, не имеющий потомков, называется листом. То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. К
аждый узел в дереве задаёт поддерево, корнем которого он является. У вершины n=(data, left, right) есть два ребёнка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right. Свойство. Строго бинарное дерево с n листами всегда содержит 2n-1 узлов. Уровень узла в бинарном дереве: уровень корня всегда равен нулю, а далее номера уровней при движении по дереву от корня увеличиваются на 1 по отношению к своему непосредственному предку. Глубина бинарного дерева — это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева. Полное бинарное дерево уровня n — это дерево, в котором каждый узел уровня n является листом, и каждый узел уровня меньше n имеет непустые левое и правое поддеревья Почти полное бинарное дерево — это бинарное дерево, для которого существует неотрицательное целое k такое, что: 1) Каждый лист в дереве имеет уровень k или k+1. 2) Если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1. Упорядоченные бинарные деревья — это деревья, в которых для каждого узла Х выполняется правило: в левом поддереве — ключи, меньшие Х, в правом поддереве — большие или равные Х. Построение бинарного дерева. Двоичное дерево поиска. П
равило построения двоичного дерева поиска: элементы, у которых значение некоторого признака меньше, чем у корня, всегда включаются слева от некоторого поддерева, а элементы со значениями, большими, чем у корня — справа. Этот принцип используется и при формировании двоичного дерева, и при поиске в нем элементов. Обратить внимание: поиск места подключения очередного элемента всегда начинается с корня. Пример: 20, 10, 35, 15, 17, 27, 24, 8, 30. Поиск элемента в бинарном дереве. При поиске элемента с некоторым значением признака происходит спуск по дереву, начиная от корня, причем выбор ветви следующего шага — направо или налево согласно значению искомого признака — происходит в каждом очередном узле на этом пути. При поиске элемента результатом будет либо найденный узел с заданным значением признака, либо поиск закончится листом с «нулевой» ссылкой, а требуемый элемент отсутствует на проделанном по дереву пути. Если поиск был проделан для включения очередного узла в дерево, то в результате будет найден узел с пустой ссылкой (пустыми ссылками), к которому справа или слева в соответствии со значением признака и будет присоединен новый узел. Двоичное дерево поиска можно определить так:
- Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные привязанные к узлу, left и right — ссылки на потомков.
- Данные (data) обладают ключом (key) на котором определена операция сравнения «меньше«. В конкретных реализациях это может быть пара (key, value).
- Для любого узла X выполняются свойства дерева поиска:
key[left[X]] < key[X] ≤ key[right[X]], т. е. ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого. Основные операции в двоичном дереве поиска: FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K. INSERT(K,V) — добавление в дерево пары (key, value) = (K, V). REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K.
Для продолжения скачивания необходимо пройти капчу:
Источник
Бинарные деревья
Хотя деревья общего вида достаточно важны, мы сосредоточимся на ограниченном классе деревьев, где каждый родитель имеет не более двух сыновей (рис. 4). Такие бинарные деревья (binary trees) имеют унифицированную структуру, допускающую разнообразные алгоритмы прохождения и эффективный доступ к элементам. Изучение бинарных деревьев дает возможность решать наиболее общие задачи, связанные с деревьями, поскольку любое дерево общего вида можно представить эквивалентным ему бинарным деревом.
У каждого узла бинарного дерева может быть 0, 1 или 2 сына. По отношению к узлу слева будем употреблять термин левый сын (left child), а по отношению к узлу справа – правый сын (right child). Наименования «левый» и «правый» относятся к графическому представлению дерева. Бинарное дерево является рекурсивной структурой. Каждый узел – это корень своего собственного поддерева. У него есть сыновья, которые сами являются корнями деревьев, называемых левым и правым поддеревьями соответственно. Таким образом, процедуры обработки деревьев рекурсивны.
Дадим рекурсивное определение бинарного дерева.
Бинарное дерево — это такое множество узлов B, что
а) B является деревом, если множество узлов пусто (пустое дерево – тоже дерево);
б) B разбивается на три непересекающихся подмножества:
Рис.4. Пример бинарного дерева
На любом уровне n бинарное дерево может содержать от 1 до 2n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. Интуитивно плотность есть мера величины дерева (число узлов) по отношению к глубине дерева. На рис. 4 дерево А содержит 8 узлов при глубине 3, в то время как дерево B содержит 5 узлов при глубине 4. Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (E) и каждый нелистовой узел имеет только одного сына. Вырожденное дерево эквивалентно связанному списку.
Рис.5. Бинарные деревья различной плотности
Деревья с большой плотностью очень важны в качестве структур данных, так как позволяют хранить большие коллекции данных и осуществлять эффективный доступ к элементам. Быстрый поиск – главное, что обусловливает использование деревьев для хранения данных.
Вырожденные деревья имеют наименьшую плотность (1). Другая крайность – законченные бинарные деревья (complete binary tree) глубины N, где каждый уровень 0, 1, . N-1 имеет полный набор узлов, и все листья уровня N расположены слева. Законченное бинарное дерево, содержащее 2N узлов на уровне N, является полным. На Рис. 6 показаны законченное и полное бинарные деревья.
Законченные и полные бинарные деревья дают интересные математические факты. На нулевом уровне имеется 2 0 узлов, на первом — 2 1 , на втором — 2 2 и т.д. На первых k-1 уровнях имеется 2 k-1 узлов.
1 + 2 + 4 + . + 2 k-1 = 2 k -1
На уровне k количество дополнительных узлов колеблется от 1 до 2k (полное). В полном дереве число узлов равно
1 + 2 + 4 + . + 2 k-1 + 2 k = 2 k-1 — 1
Число узлов законченного бинарного дерева удовлетворяет неравенству
2 k N 2 k-1 — 1 2 k-1
Решая его относительно k, имеем
k log2 (N) k+1
Например, полное дерево глубины 3 имеет
2 4 — 1 = 15 узлов
Рис.6. Классификация бинарных деревьев
Структура бинарного дерева
Структура бинарного дерева состоит из узлов (рис.7). Как и в связанном списке, эти узлы содержат поля данных и указатели на другие узлы в коллекции. В этом разделе мы определим узлы дерева и операции для его построения и прохождения. Объявим класс TreeNode, реализующий функциональность узла дерева, и разработаем ряд функций, позволяющих создавать бинарные деревья и осуществлять прохождение по их узлам.
Узел дерева содержит поле данных и два поля с указателями. Поля указателей называются левым указателем (left) и правым указателем (right), поскольку они указывают на левое и правое поддерево, соответственно. Значение NULL является признаком пустого дерева.
Рис.7. Структура узлов дерева
Корневой узел определяет входную точку дерева, а поля указателей – узлы следующего уровня. Листовой узел содержит NULL в полях правого и левого указателей. Пример представления структуры дерева дан на рис. 8.
Рис.8. Представление структуры дерева
Источник