- Двоичное дерево поиска
- Двоичное дерево поиска. Итеративная реализация.
- Поиск в дереве
- Удаление узла
- Двоичное дерево
- Типы двоичных деревьев
- Полное двоичное дерево
- Совершенное двоичное дерево
- Законченное двоичное дерево
- Вырожденное двоичное дерево
- Скошенное вырожденное дерево
- Сбалансированное двоичное дерево
- Представление двоичного дерева
- Примеры реализации
- Python
- Java
- Си
- С++
- Где используется
Двоичное дерево поиска
Двоичное дерево поиска. Итеративная реализация.
Д воичные деревья – это структуры данных, состоящие из узлов, которые хранят значение, а также ссылку на свою левую и правую ветвь. Каждая ветвь, в свою очередь, является деревом. Узел, который находится в самой вершине дерева принято называть корнем (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) У узла нет наследников (удаляем лист). Тогда он просто удаляется, а его родитель обнуляет указатель на него.
Источник
Двоичное дерево
Двоичное дерево — древовидная структура данных, в которой у родительских узлов не может быть больше двух детей.
Типы двоичных деревьев
Полное двоичное дерево
Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 0 потомков, либо 2.
Совершенное двоичное дерево
Совершенное двоичное дерево — особый тип бинарного дерева, в котором у каждого внутреннего узла по два ребенка, а листовые вершины находятся на одном уровне.
Законченное двоичное дерево
Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.
- Все уровни должны быть заполнены.
- Все листовые вершины склоняются влево.
- У последней листовой вершины может не быть правого собрата. Это значит, что завершенное дерево необязательно полное.
Вырожденное двоичное дерево
Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.
Скошенное вырожденное дерево
Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.
Сбалансированное двоичное дерево
Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 0, либо на 1.
Представление двоичного дерева
Узел двоичного дерева можно представить структурой, содержащей данные и два указателя на другие структуры того же типа.
Примеры реализации
Python
# Двоичное дерево в Python class Node: def __init__(self, key): self.left = None self.right = None self.val = key # Прямой обход дерева def traversePreOrder(self): print(self.val, end=' ') if self.left: self.left.traversePreOrder() if self.right: self.right.traversePreOrder() # Центрированный обход дерева def traverseInOrder(self): if self.left: self.left.traverseInOrder() print(self.val, end=' ') if self.right: self.right.traverseInOrder() # Обратный обход дерева def traversePostOrder(self): if self.left: self.left.traversePostOrder() if self.right: self.right.traversePostOrder() print(self.val, end=' ') root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) print("Прямой обход дерева: ", end="") root.traversePreOrder() print("\nЦентрированный обход дерева: ", end="") root.traverseInOrder() print("\nОбратный обход дерева: ", end="") root.traversePostOrder()
Java
// Двоичное дерево на Java // Создание узла class Node < int key; Node left, right; public Node(int item) < key = item; left = right = null; >> class BinaryTree < Node root; BinaryTree(int key) < root = new Node(key); >BinaryTree() < root = null; >// Центрированный обход дерева public void traverseInOrder(Node node) < if (node != null) < traverseInOrder(node.left); System.out.print(" " + node.key); traverseInOrder(node.right); >> // Обратный обход дерева public void traversePostOrder(Node node) < if (node != null) < traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.key); >> // Прямой обход дерева public void traversePreOrder(Node node) < if (node != null) < System.out.print(" " + node.key); traversePreOrder(node.left); traversePreOrder(node.right); >> public static void main(String[] args) < BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); System.out.print("Прямой обход дерева: "); tree.traversePreOrder(tree.root); System.out.print("\nЦентрированный обход дерева: "); tree.traverseInOrder(tree.root); System.out.print("\nОбратный обход дерева: "); tree.traversePostOrder(tree.root); >>
Си
// Обход дерева на Си #include #include struct node < int item; struct node* left; struct node* right; >; // Центрированный обход дерева void inorderTraversal(struct node* root) < if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); > // Прямой обход дерева void preorderTraversal(struct node* root) < if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); > // Обратный обход дерева void postorderTraversal(struct node* root) < if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); > // Создание нового узла struct node* createNode(value) < struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; > // Вставка потомка слева от родительской вершины struct node* insertLeft(struct node* root, int value) < root->left = createNode(value); return root->left; > // Вставка потомка справа от родительской вершины struct node* insertRight(struct node* root, int value) < root->right = createNode(value); return root->right; > int main() < struct node* root = createNode(1); insertLeft(root, 2); insertRight(root, 3); insertLeft(root->left, 4); printf("Центрированный обход дерева\n"); inorderTraversal(root); printf("\nПрямой обход дерева\n"); preorderTraversal(root); printf("\nОбратный обход дерева\n"); postorderTraversal(root); >
С++
// Двоичное дерево на С++ #include #include using namespace std; struct node < int data; struct node *left; struct node *right; >; // Создание нового узла struct node *newNode(int data) < struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); > // Прямой обход дерева void traversePreOrder(struct node *temp) < if (temp != NULL) < cout data; traversePreOrder(temp->left); traversePreOrder(temp->right); > > // Центрированный обход дерева void traverseInOrder(struct node *temp) < if (temp != NULL) < traverseInOrder(temp->left); cout data; traverseInOrder(temp->right); > > // Обратный обход дерева void traversePostOrder(struct node *temp) < if (temp != NULL) < traversePostOrder(temp->left); traversePostOrder(temp->right); cout data; > > int main() < struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); cout
Где используется
- Для быстрого доступа к данным.
- В алгоритмах маршрутизации.
- Для реализации куч.
- В синтаксических деревьях.
Источник