Бинарное дерево в структуре данных: свойства, типы, представление и преимущества

Среди различных типов структур данных есть бинарные деревья, которые используются чаще, чем большинство других типов. Их наиболее известные приложения включают одноранговое программирование, поиск, криптографию, сетевые маршрутизаторы с более высокой пропускной способностью, чем у других, и 3D-видеоигры. Теперь мы подробно обсудим, что такое бинарные деревья в науке о данных, каковы их типы и как они представлены.

Что такое бинарные деревья?

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

Все узлы в бинарном дереве состоят из трех основных компонентов:

• элемент данных
• правильная ссылка
• левая ссылка

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

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

Ознакомьтесь с: Идеи проекта по науке о данных для начинающих

Важные свойства узлов в бинарных деревьях

Лучшее понимание этих свойств поможет вам максимально эффективно использовать это обсуждение бинарных деревьев. Глубина различных узлов определяется как количество узлов, существующих на пути, соединяющем корень с конкретным узлом. Вот почему глубина корневого узла равна 0. С другой стороны, высота различных узлов в бинарном дереве — это количество узлов, лежащих на пути, соединяющем конкретный узел с корневым узлом. Вот почему высота листовых узлов равна 0.

Как вы можете ясно видеть, глубина узла измеряется, начиная с корневого узла и затем опускаясь, чтобы достичь этого узла. С другой стороны, когда дело доходит до вычисления высоты, мы начинаем с рассматриваемого узла, а затем идем к корневому узлу. Оба раза мы начинаем с 0. Есть люди, которые также измеряют высоту и глубину от 1, а не от 0, что не является неправильным и просто нравится другим людям.

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

Узнать больше: Структуры данных и алгоритм в Python

Что такое бинарное дерево поиска?

Бинарное дерево поиска является наиболее распространенным из всех других типов бинарных деревьев. Это специализированное бинарное дерево со свойствами, которые отличаются и более полезны, чем любая другая форма бинарного дерева. Что такое бинарное дерево поиска или BST? Как следует из названия, двоичное дерево поиска используется для поиска данных в дереве.

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

Представление бинарных деревьев

1. Связанное представление

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

В этом представлении каждый узел состоит из трех разных частей:

• указатель, указывающий на правый узел,
• указатель, указывающий на левый узел,
• элемент данных.

Это более распространенное представление. Все бинарные деревья состоят из корневого указателя, указывающего в направлении корневого узла. Когда вы видите корневой узел, указывающий на null или 0, вы должны знать, что имеете дело с пустым двоичным деревом. Правый и левый указатели хранят адреса правого и левого дочерних элементов дерева.

2. Последовательное представление

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

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

Типы бинарных деревьев

1. Полные бинарные деревья: Полные бинарные деревья — это те бинарные деревья, узлы которых либо имеют двух дочерних узлов, либо ни одного. Другими словами, бинарное дерево становится полным бинарным деревом, когда все его остальные узлы, кроме листьев, имеют по два потомка.
2. Полные бинарные деревья: Полные бинарные деревья — это деревья, все уровни которых полностью заполнены. Единственным исключением из этого может быть их последний уровень, клавиши которого находятся преимущественно слева. Двоичная куча часто рассматривается как пример полного бинарного дерева.
3. Совершенные бинарные деревья. Совершенные бинарные деревья — это бинарные деревья, листья которых находятся на одном уровне, а внутренние узлы содержат двух потомков. Типичным примером идеального бинарного дерева является генеалогическое древо предков.
4. Патологические вырожденные бинарные деревья: Вырожденные деревья — это те бинарные деревья, внутренние узлы которых имеют одного дочернего элемента. Их уровни производительности аналогичны связным спискам. Узнайте больше о типах бинарного дерева.

Читайте: Шесть наиболее часто используемых структур данных в R

Преимущества бинарных деревьев

1. Идеальный способ использовать иерархический способ хранения данных
2. Отражение структурных взаимосвязей, существующих в данном наборе данных
3. Сделайте вставку и удаление быстрее, чем связанные списки и массивы
4. Гибкий способ хранения и перемещения данных
5. Используются для хранения как можно большего количества узлов
6. Быстрее, чем связанные списки, и медленнее, чем массивы, когда дело доходит до доступа к элементам.

Заключение

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

Если вам интересно узнать о бинарных деревьях в структурах данных, науке о данных, ознакомьтесь с программой Executive PG IIIT-B и upGrad по науке о данных, которая создана для работающих профессионалов и предлагает более 10 тематических исследований и проектов, практические практические семинары, наставничество с отраслевыми экспертами, индивидуальные встречи с отраслевыми наставниками, более 400 часов обучения и помощь в трудоустройстве в ведущих фирмах.