Бинарные деревья
Двоичное дерево — это тип структуры данных, в которой каждый узел имеет не более двух дочерних элементов (левый дочерний элемент и правый дочерний элемент). Двоичные деревья используются для реализации двоичных деревьев поиска и двоичных куч, а также для эффективного поиска и сортировки. Бинарное дерево — это частный случай K-арного дерева, где k равно 2. Общие операции для бинарных деревьев включают вставку, удаление и обход. Сложность выполнения этих операций зависит от того, сбалансировано ли дерево, а также от того, являются ли узлы листовыми узлами или узлами ветвления. Для сбалансированных деревьев глубина левого и правого поддеревьев каждого узла отличается на 1 или меньше. Это позволяет получить предсказуемую глубину, также известную как высота. . Это мера узла от корня до листа, где корень равен 0, а следующие узлы — (1,2..n). Это может быть выражено целой частью log 2 (n), где n — количество узлов в дереве.
g s 9 / \ / \ / \ b m f u 5 13 / \ / \ / \ c d t y 11 15 Операции, выполняемые с деревьями, требуют поиска одним из двух основных способов: поиск в глубину и поиск в ширину. Поиск в глубину (DFS) — это алгоритм обхода или поиска структур данных в виде дерева или графа. Каждый начинает с корня и исследует, насколько это возможно, каждую ветвь, прежде чем вернуться. Существует три типа обхода поиска в глубину: посещение по предварительному заказу , влево, вправо, влево по порядку , посещение, вправо, влево по порядку , вправо, посещение. Поиск в ширину (BFS) — это алгоритм обхода или поиска структур дерева или графа. В порядке уровней, когда мы посещаем каждый узел на уровне, прежде чем перейти на более низкий уровень.
Упражнение
Ниже представлена реализация двоичного дерева с возможностью вставки и печати. Это дерево упорядочено, но не сбалансировано. Этот пример сохраняет порядок во время вставки.
Измените процедуру печати на предварительный заказ поиска в глубину .
Источник
Двоичное дерево поиска
Двоичное дерево поиска. Итеративная реализация.
Д воичные деревья – это структуры данных, состоящие из узлов, которые хранят значение, а также ссылку на свою левую и правую ветвь. Каждая ветвь, в свою очередь, является деревом. Узел, который находится в самой вершине дерева принято называть корнем (root), узлы, находящиеся в самом низу дерева и не имеющие потомков называют листьями (leaves). Ветви узла называют потомками (descendants). По отношению к своим потомкам узел является родителем (parent) или предком (ancestor). Также, развивая аналогию, имеются сестринские узлы (siblings – родные братья или сёстры) – узлы с общим родителем. Аналогично, у узла могут быть дяди (uncle nodes) и дедушки и бабушки ( grandparent nodes). Такие названия помогают понимать различные алгоритмы.
Двоичное дерево. На этом рисунке узел 10 корень, 7 и 12 его наследники. 6, 9, 11, 14 — листья. 7 и 12, также как и 6 и 9 являются сестринскими узлами, 10 — это дедушка узла 6, а 12 — дядя узла 6 и узла 9
Двоичные деревья одна из самых простых структур (по сравнению, например, с другими деревьями). Они обычно реализуют самый базовый и самый естественный способ классификации элементов – делят их по определённому признаку, размещая одну группу в левом поддереве, а другую группу в правом. В поддеревьях рекурсивно поддерживается такой же порядок, за счёт чего узлы дерева упорядочиваются.
Двоичное дерево поиска (далее ДДП) – это несбалансированное двоичное дерево, в котором элементы БОЛЬШЕ корневого размещаются справа, а элементы, которые МЕНЬШЕ размещаются слева.
Такое размещение – слева меньше, справа больше – не обязательно, можно располагать элементы, которые меньше, справа. Отношение БОЛЬШЕ и МЕНЬШЕ – это не обязательно естественная сортировка по величине, это некоторая бинарная операция, которая позволяет разбить элементы на две группы.
Для реализации бинарного дерева поиска будем использовать структуру Node, которая содержит значение, ссылку на правое и левое поддерево, а также ссылку на родителя. Ссылка на родительский узел, в принципе, не является обязательной, однако сильно упрощает и ускоряет все алгоритмы. Далее, ради тренировки, мы ещё рассмотрим реализацию без ссылки на родителя.
ЗАМЕЧАНИЕ: мы рассматриваем случай, когда в дереве все значения разные и не равны NULL. Деревья с повторяющимися узлами рассмотрим позднее.
Обычно в качестве типа данных мы используем void* и далее передаём функции сравнения через указатели. В этот раз будем использовать пользовательский тип и макросы.
typedef int T; #define CMP_EQ(a, b) ((a) == (b)) #define CMP_LT(a, b) ((a) < (b)) #define CMP_GT(a, b) ((a) >(b)) typedef struct Node < T data; struct Node *left; struct Node *right; struct Node *parent; >Node;
Сначала, как обычно, напишем функцию, которая создаёт новый узел. Она принимает в качестве аргументов значение и указатель на своего родителя. Корневой элемент не имеет родителя, значение указателя parent равно NULL.
Node* getFreeNode(T value, Node *parent) < Node* tmp = (Node*) malloc(sizeof(Node)); tmp->left = tmp->right = NULL; tmp->data = value; tmp->parent = parent; return tmp; >
Разберёмся со вставкой. Возможны следующие ситуации
- 1) Дерево пустое. В этом случае новый узел становится корнем ДДП.
- 2) Новое значение меньше корневого. В этом случае значение должно быть вставлено слева. Если слева уже стоит элемент, то повторяем эту же операцию, только в качестве корневого узла рассматриваем левый узел. Если слева нет элемента, то добавляем новый узел.
- 3) Новое значение больше корневого. В этом случае новое значение должно быть вставлено справа. Если справа уже стоит элемент, то повторяем операцию, только в качестве корневого рассматриваем правый узел. Если справа узла нет, то вставляем новый узел.
Пусть нам необходимо поместить в ДДП следующие значения
Первое значение становится корнем.
Второе значение меньше десяти, так что оно помещается слева.
Число 9 меньше 10, так что узел должен располагаться слева, но слева уже стоит значение. 9 больше 7, так что новый узел становится правым потомком семи.
Число 12 помещается справа от 10.
Добавляем оставшиеся узлы 14, 3, 4, 11
Функция, добавляющая узел в дерево
Два узла. Первый – вспомогательная переменная, чтобы уменьшить писанину, второй – тот узел, который будем вставлять.
Node *tmp = NULL; Node *ins = NULL;
Проверяем, если дерево пустое, то вставляем корень
Проходим по дереву и ищем место для вставки
Пока не дошли до пустого узла
Если значение больше, чем значение текущего узла
Если при этом правый узел не пустой, то за корень теперь считаем правую ветвь и начинаем цикл сначала
if (tmp->right) < tmp = tmp->right; continue;
Если правой ветви нет, то вставляем узел справа
> else < tmp->right = getFreeNode(value, tmp); return; >
Также обрабатываем левую ветвь
> else if (CMP_LT(value, tmp->data)) < if (tmp->left) < tmp = tmp->left; continue; > else < tmp->left = getFreeNode(value, tmp); return; > > else < exit(2); >>
void insert(Node **head, int value) < Node *tmp = NULL; Node *ins = NULL; if (*head == NULL) < *head = getFreeNode(value, NULL); return; >tmp = *head; while (tmp) < if (CMP_GT(value, tmp->data)) < if (tmp->right) < tmp = tmp->right; continue; > else < tmp->right = getFreeNode(value, tmp); return; > > else if (CMP_LT(value, tmp->data)) < if (tmp->left) < tmp = tmp->left; continue; > else < tmp->left = getFreeNode(value, tmp); return; > > else < exit(2); >> >
Рассмотрим результат вставки узлов в дерево. Очевидно, что структура дерева будет зависеть от порядка вставки элементов. Иными словами, форма дерева зависит от порядка вставки элементов.
Если элементы не упорядочены и их значения распределены равномерно, то дерево будет достаточно сбалансированным, то есть путь от вершины до всех листьев будет одинаковый. В таком случае максимальное время доступа до листа равно log(n), где n – это число узлов, то есть равно высоте дерева.
Но это только в самом благоприятном случае. Если же элементы упорядочены, то дерево не будет сбалансировано и растянется в одну сторону, как список; тогда время доступа до последнего узла будет порядка n. Это слабая сторона ДДП, из-за чего применение этой структуры ограничено.
Дерево, которое получили вставкой чередующихся возрастающей и убывающей последовательностей (слева) и полученное при вставке упорядоченной последовательности (справа)
Для решения этой проблемы можно производить балансировку дерева, или использовать структуры, которые автоматически проводят самобалансировку во время вставки и удаления.
Поиск в дереве
И звестно, что слева от узла располагается элемент, который меньше чем текущий узел. Из чего следует, что если у узла нет левого наследника, то он является минимумом в дереве. Таким образом, можно найти минимальный элемент дерева
Node* getMinNode(Node *root) < while (root->left) < root = root->left; > return root; >
Аналогично, можно найти максимальный элемент
Node* getMaxNode(Node *root) < while (root->right) < root = root->right; > return root; >
Опять же, если дерево хорошо сбалансировано, то поиск минимума и максимума будет иметь сложность порядка log(n), а в случае плохой балансировки стремится к n.
Поиск нужного узла по значению похож на алгоритм бинарного поиска в отсортированном массиве. Если значения больше узла, то продолжаем поиск в правом поддереве, если меньше, то продолжаем в левом. Если узлов уже нет, то элемент не содержится в дереве.
Node *getNodeByValue(Node *root, T value) < while (root) < if (CMP_GT(root->data, value)) < root = root->left; continue; > else if (CMP_LT(root->data, value)) < root = root->right; continue; > else < return root; >> return NULL; >
Удаление узла
С уществует три возможных ситуации.
- 1) У узла нет наследников (удаляем лист). Тогда он просто удаляется, а его родитель обнуляет указатель на него.
Источник
Обычное двоичное дерево для тестового задания
Как-то раз я делал задание для приёма на работу после собеседования, что-то вроде тестового задания только не на дом. Был интернет и я гуглил код на языке Си и нашел какой-то код который содержал ошибки, из-за этого я не смог сделать задание на которое выделили час. Почему так случилось скажу лишь то, что по программированию у меня было все плохо по минимуму и своего кода для деревьев у меня не было и для графов тоже.
Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево не является упорядоченным ориентированным деревом. [1]
//Листинг #1 Бинарное дерево, представление #include #include using namespace std; //Наша структура struct node < int info; //Информационное поле node *l, *r; //Левая и Правая часть дерева >; node *tree = NULL; //Объявляем переменную, тип которой структура Дерево /*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/ void push(int a, node **t) < if ((*t) == NULL) //Если дерева не существует < (*t) = new node; //Выделяем память (*t)->info = a; //Кладем в выделенное место аргумент a (*t)->l = (*t)->r = NULL; //Очищаем память для следующего роста return; //Заложили семечко, выходим > //Дерево есть if (a > (*t)->info) push(a, &(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо else push(a, &(*t)->l); //Иначе кладем его влево > /*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/ void print(node *t, int u) < if (t == NULL) return; //Если дерево пустое, то отображать нечего, выходим else //Иначе < print(t->l, ++u); //С помощью рекурсивного посещаем левое поддерево for (int i = 0; i < u; ++i) cout info print(t->r, ++u); //С помощью рекурсии посещаем правое поддерево > int sum(node *node_) < if (node_ == 0) return 0; return node_->info + sum(node_->l) + sum(node_->r); > int main() < int n = 16; //Количество элементов int s; //Число, передаваемое в дерево for (int i = 0; i < n; ++i) < s = -5 + rand() % 10; //Считываем элемент за элементом push(s, &tree); //И каждый кладем в дерево >cout
Данный код задает дерево и считает рекурсивно сумму его вершин. Дерево неупорядочено и не отсортировано.
Может быть мне или кому-нибудь еще пригодится данный код для устройства на работу, просто сейчас очень многие постят код который с ошибками в глуповатых статьях и сайтах.
Источник