Бинарные деревья поиска и рекурсия – это просто +21

Бинарные деревья поиска и рекурсия – это просто +21

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями. Рис. 1 Бинарное дерево Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева. То есть, данные в бинарном дереве поиска хранятся в отсортированном виде. При каждой операции вставки нового или удаления существующего узла отсортированный порядок дерева сохраняется. При поиске элемента сравнивается искомое значение с корнем. Если искомое больше корня, то поиск продолжается в правом потомке корня, если меньше, то в левом, если равно, то значение найдено и поиск прекращается. Рис. 2 Бинарное дерево поиска Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности. Рис. 3 Сбалансированное бинарное дерево поиска Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей. Например, в С++ ассоциативные контейнеры set и map представляют собой сбалансированное бинарное дерево поиска. Рис. 4 Экстремально несбалансированное бинарное дерево поиска Теперь кратко обсудим рекурсию. Рекурсия в программировании – это вызов функцией самой себя с другими аргументами. В принципе, рекурсивная функция может вызывать сама себя и с теми же самыми аргументами, но в этом случае будет бесконечный цикл рекурсии, который закончится переполнением стека. Внутри любой рекурсивной функции должен быть базовый случай, при котором происходит выход из функции, а также вызов или вызовы самой себя с другими аргументами. Аргументы не просто должны быть другими, а должны приближать вызов функции к базовому случаю. Например, вызов внутри рекурсивной функции расчета факториала должен идти с меньшим по значению аргументом, а вызовы внутри рекурсивной функции обхода дерева должны идти с узлами, находящимися дальше от корня, ближе к листьям. Рекурсия может быть не только прямой (вызов непосредственно себя), но и косвенной. Например А вызывает Б, а Б вызывает А. С помощью рекурсии можно эмулировать итеративный цикл, а также работу структуры данных стек (LIFO).

Бинарное дерево поиска с++. Немного теории

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

Определения и не только:

Свободное дерево (дерево без выделенного корня) или просто дерево — ациклический неориентированный граф.
Дерево с корнем — свободное дерево, в котором выделена одна вершина, называемая корнем (root).
Узлы (nodes) — вершины дерева с корнем.
Родительский узел или родитель узла X — последний узел, предшествующий X на пути от корня R к этому узлу X. В таком случае узел X называется дочерним к описанному родительскому узлу Y. Корень дерева не имеет родителя.
Лист — узел, у которого нет дочерних узлов.
Внутренний узел — узел, не являющийся листом.
Степень узла X — количество дочерних узлов этого узла X.
Глубина узла X — длина пути от корня R к этому узлу X.
Высота узла (height) — длина самого длинного простого (без возвратов) нисходящего пути от узла к листу.
Высота дерева — высота корня этого дерева.
Упорядоченное дерево — дерево с корнем, в котором дочерние узлы каждого узла упорядочены (т.е. задано отображение множества дочерних узлов на множество натуральных чисел от 1 до k , где k — общее количество дочерних узлов этого узла). Простыми словами, каждому дочернему узлу присвоено имя: «первый», «второй», …, " k -тый".
Бинарное дерево (binary tree) — ( рекурсивно ) либо пустое множество (не содержит узлов), либо состоит из трёх непересекающихся множеств узлов: корневой узел , бинарное дерево, называемое левым поддеревом , и бинарное дерево, называемое правым поддеревом . Таким образом, бинарное дерево — это упорядоченное дерево, у которого каждый узел имеет степень не более 2 и имеет «левый» и/или/либо «правый» дочерние узлы.
Полностью бинарное дерево (full binary tree) — бинарное дерево, у которого каждый узел либо лист, либо имеет степень два. Полностью бинарное дерево можно получить из бинарного добавлением фиктивных дочерних листов каждому узлу степени 1.
Бинарное дерево поиска — связанная структура данных, реализованная посредством бинарного дерева, каждый узел которого может быть представлен объектом, содержащим ключ (key) и сопутствующие данные, ссылки на левое и правое поддеревья и ссылку на родительский узел. Ключи бинарного дерева поиска удовлетворяют свойству бинарного дерева поиска :

если X — узел, и узел Y находится в левом поддереве X , то Y.key ? X.key . Если узел Y находится в правом поддереве X , то X.key ? Y.key .

Подразумевается, что мы умеем сравнивать ключи (на множестве значений ключа задано транзитивное отношение порядка, т.е. проще говоря операция «меньше») и говорить о равенстве ключей. В реализации без ограничения общности мы будем оперировать строгими неравенствами порядка, используя только операцию "$$ Обход дерева — формирование списка узлов, порядок определяется типом обхода.

Бинарное дерево пример. Двоичное дерево поиска

Двоичное дерево поиска
Тип	дерево
Год изобретения	1960
Автор	Andrew Donald Booth
Сложность в О-символике
В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(n) Вставка O(log n) O(n) Удаление O(log n) O(n)
Медиафайлы на Викискладе

Двоичное дерево поиска ( англ.   binary search tree , BST) — двоичное дерево , для которого выполняются следующие дополнительные условия ( свойства дерева поиска ):

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

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

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

> ≤ key>, то есть ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.

Двоичное дерево поиска не следует путать с двоичной кучей , построенной по другим правилам.

Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки .

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

Базовый интерфейс двоичного дерева поиска состоит из трёх операций:

Этот абстрактный интерфейс является общим случаем, например, таких интерфейсов, взятых из прикладных задач:

По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, INSERT, REMOVE.

Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

Дано : дерево Т и ключ K.

Задача : проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.

Алгоритм :

Дано : дерево Т и пара (K, V).

Задача : вставить пару (K, V) в дерево Т (при совпадении K, заменить V).

Алгоритм :

Дано : дерево Т с корнемnи ключом K.

Задача : удалить из дерева Т узел с ключом K (если такой есть).

Алгоритм :

n.
mставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узломm;
mправого поддерева отсутствует (n->right->left)
m, правого поддерева n->right; mвn; m.

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.

Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f, операндом которой является адрес узла. Эта функция обычно работает только с парой (K, V), хранящейся в узле. Операция INFIX_TRAVERSE может быть реализована рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.

Двоичное дерево поиска (Binary Search Tree (BST))

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

• Двоичным (бинарным) деревом называется, потому что каждый узел дерева имеет максимально два дочерних элементов.
• Деревом поиска, потому что его можно использовать для поиска числа в O(log(n)) time (алгоритм с временной сложностью T(n) = O(log(n))(прим.ред.)).

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

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

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

Есть две основные операции, которые вы можете выполнять в двоичном дереве поиска:

1. Проверка, присутствует ли число в двоичном дереве поиска.

Алгоритм зависит от свойства BST так, что, если каждое левое поддерево имеет значения ниже корневого, то каждое правое поддерево имеет значения выше корневого.

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

Алгоритм:

If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number > root->data return search(root->right)

Давайте попробуем визуализировать алгоритм с помощью диаграммы.

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

Вы могли заметить, что мы вызывали функцию return search (struct node) четыре раза. Когда мы возвращаем либо новый узел, либо NULL, значение возвращается снова и снова, до тех пор, пока search (root) не вернет окончательный результат.

Если значение не найдено, мы в конечном итоге достигаем левого или правого потомка конечного узла, который равен NULL, и он распространяется и возвращается.

2. Вставка значения в двоичное дерево поиска (BST)

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

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

Алгоритм:

If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data > node->data) node->right = insert(node->right, data); return node;

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

Мы подсоединили узел, но нам все еще нужно выйти из функции, не нанося вреда остальной части дерева. Вот где return node (возвратный узел) в конце пригодится. В этом случае NULL, вновь созданный узел возвращается и присоединяется к родительскому узлу, в противном случае тот же самый узел возвращается без каких-либо изменений, пока мы не вернемся к корневому узлу.

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

Бинарное дерево поиска - C++ реализация. Реализуйте дерево двоичного поиска с помощью ключевого слова struct в C++

Дерево двоичного поиска (BST) - это особый случай структуры данных двоичного дерева. Структура данных обычно используется для хранения отсортированного списка элементов для быстрого поиска с использованием алгоритма двоичного поиска. В отличие от обычного двоичного дерева, BST имеет специальный элемент данных в каждом узле, называемыйkey, который должен иметь уникальные значения.

Каждый узел в BST должен удовлетворять следующему требованию: значениеkeyдолжно быть больше, чем все ключи в поддереве его левого дочернего элемента, и меньше, чем все ключи в поддереве его правого дочернего элемента. Предыдущее утверждение подразумевает, что элементы с меньшими значениями ключа будут расположены в левой части древовидной иерархии; это приводит к оптимальной структуре для использования двоичного поиска.

В следующем примере кода мы определяемstructс именемBSTreeNode, состоящую из двух указателей на левый / правый узлы и членаstringдля обозначения ключа. Обратите внимание, что мы просто реализуем простейшую версию BST, где значение ключа совпадает с данными, хранящимися в узле.

Как правило, программист может определить узел BST для хранения других элементов данных, необходимых для конкретной проблемы. Это определение лучше всего подходит для имитации отсортированного массива строк, в котором нужно искать заданную строку (ключ). Прежде чем мы реализуем функцию двоичного поиска, необходимо создать объект BST с нуля. Таким образом, мы используем предопределенныйвекторстрок для инициализации нового двоичного дерева поиска.

ФункцияinsertNode- это рекурсивная реализация для создания нового дочернегоBSTreeNode, когда в качестве аргумента передается корень дерева. Если нам нужно создать сам корневой узел, вы можете объявить указатель на типBSTreeNode, присвоить емуnullptrи передать егоinsertNodeс соответствующимстроковымзначением, которое необходимо там сохранить. После того, как мы инициализировали список содержимымv1, можно вызвать функциюprintTreeдля печати всех значений ключей в отсортированном порядке, называемом обходомinorderBST.

Бинарные деревья примеры использования. Двоичное дерево

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

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

Существует следующее рекурсивное определение двоичного дерева (см. БНФ ):

 ::= ( ) | null .

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

Например, показанное справа на рис. 1 дерево согласно этой грамматике можно было бы записать так:

(m (e (c (a null null) null ) (g null (k null null) ) ) (s (p (o null null) (s null null) ) (y null null) ) )

Рис. 1. Двоичное дерево поиска, в котором ключами являются латинские символы упорядоченные по алфавиту.

.

Источник: https://arki-v-sadu.aystroika.info/stati/struktura-dannyh-java-i-derevo-algoritmov-oglavlenie

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

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

Двоичное (бинарное) дерево поиска (binary search tree, BST) – это дерево, в котором элементы размещаются согласно определенному правилу (упорядоченно):

• Каждый узел должен быть "больше" любого элемента в своем левом поддереве.
• Каждый узел должен быть "меньше" любого элемента в своем правом поддереве.

Слова "больше" и "меньше" соответственно означают результат сравнения двух узлов функцией-компаратором.

Благодаря такой сортировке мы можем использовать все преимущества стратегии "разделяй и властвуй" – при поиске элемента можно смело отбрасывать половину дерева. Такие алгоритмы работают гораздо быстрее, чем линейный перебор каждого узла.

Важно:

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

Реализация на JavaScript

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

Так как бинарное дерево поиска является упорядоченным, нам еще потребуется функция-компаратор для сравнения элементов.

class BinarySearchTreeNode extends BinaryTreeNode { constructor(value, comparator) { super(value); this.comparator = comparator; } insert(value) { if (this.comparator(value, this.value) 0) { if (this.right) return this.right.insert(value); let newNode = new BinarySearchTreeNode(value, this.comparator); this.setRight(newNode); return newNode; } return this; } } class BinarySearchTree { constructor(value, comparator) { this.root = new BinarySearchTreeNode(value, comparator); this.comparator = comparator; } insert(value) { this.root.insert(value); } }

Методinsert, сравнивает значение нового элемента со значением узла и определяет, в какое поддерево его нужно поместить.

Создадим дерево как на картинке выше:

const tree = new BinarySearchTree(8, (a, b) => a - b); tree.insert(3); tree.insert(10); tree.insert(14); tree.insert(1); tree.insert(6); tree.insert(4); tree.insert(7); tree.insert(13);

А теперь обойдем все его элементы, чтобы убедиться, что оно сформировано правильно:

traverseBF(tree.root);

Поиск в бинарном дереве поиска

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

Бинарное дерево. Дерево поиска, наивная реализация

Бинарное дерево поиска обладает следующим свойством: если $x$ — узел бинарного дерева с ключом $k$ , то все узлы в левом поддереве должны иметь ключи, меньшие $k$ , а в правом поддереве большие $k$ .

Операции в бинарном дереве поиска

Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:

Обход дерева поиска

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:

$\backslash mathrm\{inorderTraversal\}$ — обход узлов в отсортированном порядке, $\backslash mathrm\{preorderTraversal\}$ — обход узлов в порядке: вершина, левое поддерево, правое поддерево, $\backslash mathrm\{postorderTraversal\}$ — обход узлов в порядке: левое поддерево, правое поддерево, вершина.

func inorderTraversal(x : Node ): if x != null inorderTraversal(x.left) print x.key inorderTraversal(x.right)

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 3 4 6 7 8 10 13 14 .

func preorderTraversal(x : Node ) if x != null print x.key preorderTraversal(x.left) preorderTraversal(x.right)

При выполнении данного обхода вершины будут выведены в следующем порядке: 8 3 1 6 4 7 10 14 13 .

func postorderTraversal(x : Node ) if x != null postorderTraversal(x.left) postorderTraversal(x.right) print x.key

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 4 7 6 3 13 14 10 8 .

Данные алгоритмы выполняют обход за время $O(n)$ , поскольку процедура вызывается ровно два раза для каждого узла дерева.

Поиск элемента

Поиск элемента 4

Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы $O(h)$ , где $h$ — высота дерева.

Поиск минимума и максимума

Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям $left$ от корня дерева, пока не встретится значение $null$ . Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.

Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время $O(h)$ .

Поиск следующего и предыдущего элемента

Реализация с использованием информации о родителе

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

Обе операции выполняются за время $O(h)$ .

Реализация без использования информации о родителе

Рассмотрим поиск следующего элемента для некоторого ключа $x$ . Поиск будем начинать с корня дерева, храня текущий узел $current$ и узел $successor$ , последний посещенный узел, ключ которого больше $x$ .
Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла $current$ . Если $current.key\; \backslash leqslant\; x$ , значит следующий за $x$ узел находится в правом поддереве (в левом поддереве все ключи меньше $current.key$ ). Если же $x\; \backslash lt\; current.key$ , то $x\; \backslash lt\; next(x)\; \backslash leqslant\; current.key$ , поэтому может быть следующим для ключа , либо следующий узел содержится в левом поддереве . Перейдем к нужному поддереву и повторим те же самые действия.
Аналогично реализуется операция поиска предыдущего элемента.

Вставка

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

Реализация с использованием информации о родителе

func insert(x : Node , z : Node ):// x — корень поддерева, z — вставляемый элемент while x != z.key > x.key x.right != x = x.right z.parent = x x.right = z z.key

Реализация без использования информации о родителе

Время работы алгоритма для обеих реализаций — $O(h)$ .

Бинарное дерево Python. Implement Binary Tree in Python

In this article, we have explored the strategy to implement Binary Tree in Python Programming Language with complete explanation and different operations like traversal, search and delete.

Table of contents :

1. Basics of Binary Tree
2. Implementation in Python with Explanation
3. Traversal operation
4. Search Operation
5. Deletion operation

Basics of Binary Tree

What is Binary Tree?

Binary tree is special type of heirarichal data structures defined using nodes. Basically its extended version of linked list. Its a tree data structure where each node is allowed to have maximum two children node, generally referred as Left Child and Right Child. Hashing, routing data for network traffic, data compression, and binary search trees are some of its application.

Data, left subtree and right subtree are three important features in a binary tree. Each data resides in the Data cell with left pointer pointing to subsequent left subtree and Right Data cell with right pointer pointing to subsequent eight subtree.

**Some Key Termniogies:- **

Root:- The Topmost node Height:- Total Number of edges from root node to last(deepest) node Leaf:- Node with no children Depth of a Tree : The number of edges from the tree’s node to the root is. Internal Node:- Node having atleast one Children Type of Binary Tree

1. Perfect Binary Tree

A Binary Tree with all the interior node (all nodes except leaf node) have two children and all leaf node has same depth

1. Balanced Binary Tree

Every tree where the maximum difference between right and left subtree height is 1.

3)Complete Binary Tree

All binary tree where every node is completly filled with 2 or 0 node .

4)Degenrate Binary Tree

Every binary tree, where every internal node has only single child.

Applications of Binary Tree

1. Used in 3d Video Games.
2. Highly used in router for tabling purpose.
3. Scheduling processes in OS.

Implementation in Python with Explanation

Implementing the Code :-

class BinaryTree: def __init__(self, value): self.left = None self.right = None self.value = value def insert(self, value): if self.value: if data self.value: if self.right is None: self.right = BinaryTree(value) else: self.right.insert(value) else: self.value = value def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() root = BinaryTree(100) root.insert(50) root.insert(55) root.insert(60) root.insert(20) root.insert(52) root.PrintTree()

Ouput:- 20,24,35,40,55,60

Structure Of the Tree :-

40 / \ 35 55 / \ 20 60 \ 24

**Explanation:- **

Here, we define a class BinarTree, in which 3 methods are defined

__init__
1. insert()
2. PrintTree()

__init__methods are self called.

Now in the main funcion as we create a object of class in root, we pass the value 40, which we want to be the root element. In the next line we call insert() method with the object and pass the value 35, which take the flow of program to insert function, there we check if the new value is greater or less then its parent value with (if value40 / 35

Now we call the insert function with value 55, the same process as prescribed above goes here also, but here 50>35(since previously self.value was updated using self.left=BinaryTree(35) and 50 is the new value), so the flow goes to elif condition under which it see self.right is indeed equal to None therefore it updates it to 55 and self.value to 55.

40 / \ 35 55

Similarly, the rest of insert function are called and executing on every value the final Binary tree is obtained.

Traversal operation

When, we print the values of every node here we are using preorder traversal where left first left most child is printed, then root, then the right child.