Бинарное дерево — что это? B-деревья | OTUS
⚡Подписка от OTUS!
Собери свой пул курсов на выгодных условиях. Подробности в чате →
Написать в чат

Курсы

Программирование
Unity Game Developer. Basic
-15%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-6%
Разработчик C#
-8%
Алгоритмы и структуры данных
-8%
Backend-разработчик на PHP
-8%
JavaScript Developer. Professional
-9%
iOS Developer. Professional
-8%
Базы данных
-12%
C# ASP.NET Core разработчик
-6%
Python Developer. Basic
-10%
Java Developer. Professional Web-разработчик на Python Android Developer. Basic PostgreSQL Software Architect Reverse-Engineering. Professional Kotlin Backend Developer React.js Developer VOIP инженер Нереляционные базы данных Scala-разработчик Супер-практикум по использованию и настройке GIT IoT-разработчик JavaScript Developer. Basic Advanced Fullstack JavaScript developer Unity Game Developer. Professional Супер-интенсив Azure
Инфраструктура
Супер-интенсив "Версионирование и командная работа с помощью Git"
-30%
Administrator Linux. Professional
-5%
Супер-интенсив «CI/CD или Непрерывная поставка с Docker и Kubernetes»
-30%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-6%
Administrator Linux. Advanced
-8%
Infrastructure as a code in Ansible
-12%
Network engineer
-4%
MS SQL Server Developer
-8%
Cloud Solution Architecture Highload Architect Разработчик голосовых ассистентов и чат-ботов Мониторинг и логирование: Zabbix, Prometheus, ELK Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Архитектор сетей Супер-интенсив «IaC Ansible»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Бинарное дерево — что это? B-деревья

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

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

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

tree_1-1801-ce20a6.png

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

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

Использование

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

Способы обхода

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

tree2_2-1801-44cb3c.png

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

Реализация

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

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

Screenshot_2-1801-e5f092.png

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

Screenshot_3-1801-9f3cac.png

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

Screenshot_4-1801-44c7e8.png

Бинарное дерево поиска

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

Screenshot_5-1801-690117.png

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

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

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

Screenshot_6-1801-1cf04e.png

Удаляем поддерево

Screenshot_7-1801-9af795.png

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

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

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

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

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

Screenshot_7.1-1801-d40701.png

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

Screenshot_7.2-1801-28274b.png

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

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

Screenshot_8-1801-d03310.png

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

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

Screenshot_9-1801-90456d.png

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

Algo_970x90-1801-545cb2.png

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

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться