Объяснение 5 типов двоичного дерева в структуре данных

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

Указатель изображает бинарное дерево до самого верхнего узла, обычно называемого корнем дерева. Каждый узел в двоичном дереве содержит данные, указатель на левого дочернего элемента и указатель на правый дочерний элемент. Указатели используются для реализации двоичного дерева. Указатель корня обозначает первый узел в дереве. Чтобы создать бинарное дерево, вам нужно сначала создать узел.

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

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

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

Узел: содержит значение данных в двоичном дереве.

Корень: самый верхний узел в любом бинарном дереве называется корнем дерева.

Размер: обозначает количество узлов в двоичном дереве.

Родительский узел: узел в двоичном дереве с дочерним.

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

Внутренний узел: это узел с хотя бы одним дочерним элементом в двоичном дереве.

Листовой узел: это узел без дочерних элементов.В качестве альтернативы это внешний узел.

Глубина дерева узлов: рассчитывается в контексте конкретного узла.Это называется количеством ребер от определенного узла до корня.

Длина внутреннего пути дерева: относится к сумме уровней каждого внутреннего узла в двоичном дереве.

Длина внешнего пути дерева: определяется как сумма уровней каждого внешнего узла в двоичном дереве.

Высота узла в дереве: это количество ребер от определенного узла до самого глубокого листового узла бинарного дерева.Высота корня всегда будет больше высоты других узлов бинарного дерева.

Теперь давайте подробно рассмотрим 5типов бинарного дерева.

Типы бинарного дерева

1. Полное бинарное дерево

Этобинарное дерево в структуре данных также известно под названиями - Правильное бинарное дерево и Строгое бинарное дерево.Это один из самых фундаментальныхтипов двоичного дерева в структуре данных.Полное бинарное дерево определяется как бинарное дерево, в котором каждый узел должен иметь двух дочерних элементов или вообще не иметь их.

В качестве альтернативы он характеризуется как двоичное дерево, в котором каждый узел содержит двух дочерних элементов, кроме конечных узлов. Узлы, в которых хранится адрес корневого узла, называются дочерними узлами корня. Те узлы, которые лишены дочерних элементов, называются листовыми узлами.

Вам нужно обойти все узлы, чтобы проверить, является ли дерево бинарным. Код вернет «False», если у любого узла есть один дочерний узел. Он вернет «Истина», если все узлы имеют 0 или 2 дочерних элемента.

Вот свойства полного бинарного дерева:

• Количество конечных узлов равно количеству внутренних узлов + 1. Например, если количество внутренних узлов равно 4, количество конечных узлов равно 5.
• Максимальное количество узлов и количество узлов в бинарном дереве равны. Он представлен как 2h+1 -1.
• Минимальное количество узлов в полном бинарном дереве равно 2h-1.
• Минимальная высота полного бинарного дерева составляет log 2 (n+1) – 1.
• Максимальная высота полного бинарного дерева равна h = (n+1)/2.

2. Идеальное бинарное дерево

Идеальное бинарное дерево — это один из техтипов бинарных деревьев , в которых каждый узел должен иметь 0 или 2 дочерних элемента, а уровень каждого конечного узла должен быть одинаковым.Другими словами, совершенныебинарные деревья в структуре данных определяются как такие деревья, в которых все внутренние узлы имеют две ветви, а узлы без ветвей (конечные узлы) существуют на одном уровне.

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

Изучайтеонлайн-курсы по науке о данныхв лучших университетах мира. Участвуйте в программах Executive PG, Advanced Certificate Programs или Master Programs, чтобы ускорить свою карьеру.

3. Полное двоичное дерево

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

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

Вот ключевые свойства полного бинарного дерева:

• Максимальное количество узлов 2 h+1 – 1.
• Минимальное количество узлов — 2 ч .
• Минимальная высота составляет log 2 (n+1) – 1.

4. Сбалансированное бинарное дерево

В сбалансированных бинарных деревьях высота дерева составляет log 2 от общего числа узлов. Предположим, что высота дерева равна h, а общее количество узлов в дереве равно n. Уравнение для расчета высоты: h = log(n). Максимальная разница в высоте между правым поддеревом и левым поддеревом должна быть равна «1».

Разница может иметь и другие значения, такие как 0 и -1. Эти типы бинарных деревьев также называются деревьями AVL.Одним из известных примеров сбалансированных бинарных деревьев является красно-черное дерево.

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

узел частного класса {

частное целое значение;

приватный узел слева;

право частного узла;

}

общественное логическое значение isBalanced (узел n) {

если (balancedtreeHeight(n) > -1)

вернуть истину;

вернуть ложь;

}

public int balancetreeHeight (узел n) {

если (n == ноль)

вернуть 0;

int h1 = balancetreeHeight (n.right);

int h2 = balancetreeHeight (n.left);

если (h1 == -1 || h2 == -1)

возврат -1;

если (Math.abs(h1 – h2) > 1)

возврат -1;

если (h1 > h2)

вернуть h1 + 1;

вернуть h2 + 1;

}

Ознакомьтесь с нашими программами по науке о данных в США

5. Вырожденное бинарное дерево

Вырожденное бинарное дерево — один из менее часто используемыхтипов бинарного дерева поиска .Это бинарное дерево, в котором каждый узел имеет только одного потомка, т. е. левого или правого потомка. Ни один узел не должен иметь как левых, так и правых дочерних элементов.

Прочтите наши популярные статьи о науке о данных в США

Заключение

Важно понимать,что такое бинарное дерево в структуре данных , если вы хотите использовать его для различных приложений.Реализация различных функций в бинарных деревьях может помочь вам в эффективной организации и хранении данных.

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

Начните свое путешествие по машинному обучению на upGrad

Если вы хотите изучать науку о данных, вы можете продолжить обучение по программе UpGrad Master of Science in Data Science . Этот 24-месячный курс дает такие навыки, как Python, развертывание моделей ML, обработка BD с использованием Spark, прогнозная аналитика и статистика, а также контролируемые и неконтролируемые модели ML. Курс подходит для амбициозных менеджеров, выпускников MBA, инженеров и специалистов в различных областях.

Прохождение этого курса поможет вам работать инженером данных, аналитиком больших данных, инженером по машинному обучению и специалистом по данным.