Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 Статья расскажет о том, что такоебинарные деревья. Будут представлены способы их представления и основные термины. Отдельное внимание будет уделено B-дереву и его отличию от двоичных структур.

2 Деревомназывают структуру данных, которая имеет древовидный вид, то есть характеризуется наличием набора связанных узлов. Бинарное дерево - это конечное множество элементов, связанных с двумя разными бинарными деревьями - правым и левым поддеревьями.

3 Способ представления:

4 На что следует обратить внимание: - А - корень дерева; - B - корень левого поддерева и предок D; - С - корень правого поддерева; - D - потомок родительского узла B; если D располагается на уровне i, то B - на уровне i-1.

5 Необходимо выделить следующие термины: -узел (вершина)- это каждый элемент бинарного дерева; -ветви- связи между узлами; -глубина (высота)- наибольший уровень какого-нибудь элемента; -лист(терминальный узел) - термин применяется, если элемент не имеет потомков; -внутренние узлы- узлы ветвления; -степеньвнутреннего узла - число его потомков (наибольшая степень всех существующих узлов - это степень всего бинарного дерева); -длина путик x - количество ветвей, которые необходимо пройти от корня до текущего узла x. Длина пути самого корня равна нулю, а узел на уровне i обладает длиной пути, которая равна i.

6 <h2>Использование</h2>

7 На практике бинарные деревья применяются, когда в каждой точке какого-нибудь вычислительного процесса нужно принимать одно из 2-х возможных решений. Существует множество задач, решаемых таким способом. Одна из них - выполнение операции, условно говоря, X с каждым элементом дерева. X рассматривается в качестве параметра обобщенной задачи посещения всех вершин либо задачи обхода дерева. Если рассмотреть такую задачу в качестве единого последовательного процесса, то можно сказать, что отдельные вершины посещаются в определенном порядке, то есть могут считаться линейно расположенными.

8 <h2>Способы обхода</h2>

9 Предположим, что имеется дерево (не пустое), в котором A является корнем, а B и C - левым и правым поддеревьями.

10 Есть 3 способа обхода: 1. Обход в прямом порядке - сверху вниз: A, B, C - префиксная форма. 2. Обход слева направо (симметричный порядок): B, A, C - инфиксная форма. 3. Обход снизу вверх (обратный порядок): B, C, A - постфиксная форма.

11 <h2>Реализация</h2>

12 На практике вершину древа можно описать в качестве структуры:

13 Тогда обход в префиксной форме будет выглядеть следующим образом:

14 Теперь инфиксная форма:

15 И постфиксная:

16 <h2>Бинарное дерево поиска</h2>

17 Оно представляет собой двоичное (бинарное) дерево, для которого справедлив ряд дополнительных условий. Эти условия называют свойствами:

18 Данные в каждой вершине должны обладать ключами, где определена операция сравнения “<”.

19 Обычно информация, которая представляет каждую вершину, - это запись, а не единственное поле данных.

20 Чтобы составить бинарное дерево поиска, пригодится функция добавления узла:

21 <h2>Удаляем поддерево</h2>

22 <h2>B-дерево. Поиск по B-дереву</h2>

23 В бинарном дереве поиска каждый узел содержит лишь одно значение (ключ) и не более 2-х потомков. Но существует особый вид древа поиска, называемый B-дерево (Би-дерево). Здесь узел содержит больше одного значения и больше 2-х потомков. Также его называют сбалансированным по высоте деревом поиска порядка m (Height Balanced m-way Search Tree).

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

25 Возможные операции: 1. Поиск. 2. Вставка (вставляем новый элемент). 3. Удаление.

26 Каждое B-дерево имеет порядок. Для примера рассмотрим B-дерево порядка m. Оно будет обладать рядом следующих характеристик:

27 Ниже можно посмотреть на B-дерево четвертого порядка, содержащее максимум три значения ключа и максимум четыре потомка для каждой вершины.

28 Поиск аналогичен поиску по двоичному дереву. Следует вспомнить, что в двоичном древе поиск начинается с корня, причем каждый раз принимается 2-стороннее решение (пойти по правому поддереву либо по левому). В В-дереве поиск тоже начинается с корневого узла, но с той лишь разницей, что на каждом шаге принимается не 2-стороннее, а n-стороннее решение, причем n для дерева в данном случае представляет общее число потомков рассматриваемого узла. Сложность поиска такого дерева - O(log n).

29 Алгоритм следующий:

30 Также существует такое понятие, как вставка в B-дерево.

31 В В-дереве вставка нового элемента возможна лишь в узел-лист. То есть вставленная новая пара ключ-значение добавляется лишь к узлу-листу. Вот, как осуществляется вставка в B-дерево:

32 Более подробную информацию всегда можно получить на наших курсах по алгоритмам в Москве.

33 Источники: - https://zen.yandex.ru/media/id/5bbcbc1ba5bd5400a990e7d9/struktura-dannyh-bderevo-5d273e1dcfcc8600ac055454; - https://prog-cpp.ru/data-tree/.