Что такое двоичное дерево

Двоичное дерево

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

Типы двоичных деревьев

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

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

Совершенное двоичное дерево

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

Законченное двоичное дерево

Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.

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

Вырожденное двоичное дерево

Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.

Скошенное вырожденное дерево

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

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

Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 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

Где используется

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

Источник

Разбираемся с двоичными деревьями поиска

Перевод статьи «Understanding Binary Search Trees».

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

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

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

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

Как вы, вероятно, догадались, двоичное дерево поиска (binary search tree, BST) это подвид двоичного дерева. Ключевое отличие BST состоит в том, что здесь узлы хранятся особым образом: узлы с меньшими значениями хранятся слева, а с большими — справа. Если вы сами не заметили, обращаю ваше внимание, что на рисунке изображено именно двоичное дерево поиска. Возможно, вам пока сложно понять, как упорядочены узлы, но не волнуйтесь, мы рассмотрим это подробнее в следующих разделах!

Создание классов Node и BST

Как обычно, я призываю читателей писать код вместе со мной и проверять все, о чем говорится. Для начала мы создадим наш класс Node , который будет представлять узлы нашего двоичного дерева поиска (BST):

Далее мы объявим базовую структуру нашего класса BinarySearchTree :

Наш следующий шаг — реализация нескольких методов. А именно:

• insert(data)
• inOrderTraverse()
• preOrderTraverse()
• postOrderTraverse()
• search(data)
• remove(data)

Вставка узла в BST

Чтобы вставить в дерево новый узел, нужно пройти два шага:

1. Проверить, является ли наша вставка особым случаем. Другими словами, нам нужно проверить, не должен ли быть первым в нашем дереве тот узел, который мы хотим добавить. Если он таки должен быть первым, нам просто нужно направить root на этот новый узел, создав экземпляр класса Node и назначив его свойству root .
2. Добавить узел на другую позицию (не root ).

insert(data) < let newNode = new Node(data); if(this.root === null) < this.root = newNode; >else < this.insertNode(this.root, newNode); // helper method below >> insertNode(node, newNode) < if(newNode.data < node.data) < if(node.left === null) < node.left = newNode; >else < this.insertNode(node.left, newNode); >> else < if(node.right === null) < node.right = newNode; >else < this.insertNode(node.right, newNode); >> >

В общем, insert(data) создает новый Node со значением data , и если дерево пустое, этот узел устанавливается в качестве root . В противном случае вызывается insertNode(this.root, newNode) .

insertNode(node, newNode) это наш вспомогательный метод, ответственный за сравнение данных нового узла с данными текущего узла и соответственное смещение влево или вправо. Это делается рекурсивно, пока не будет найден подходящий узел с нулевым значением, куда может быть добавлен новый узел.

Рассмотрим пример. Если мы выполним следующий код…

const BST = new BinarySearchTree(); BST.insert(11); // establishes root node BST.insert(7); BST.insert(9); BST.insert(15); . BST.insert(6);

то сможем проиллюстрировать последнюю вставку такой диаграммой:

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

Обход дерева это процедура посещения всех узлов дерева и осуществления операций с каждым узлом. Главный вопрос состоит в том, как нам идти. Есть три основных подхода: центрированный (in-order), прямой (pre-order) и обратный (post-order).

Центрированный обход

Совершая центрированный обход, мы посещаем все узлы в восходящем порядке, начиная с заданного узла (опционально) и выполняя указанную функцию callback (тоже опционально). Здесь мы опять воспользуемся рекурсией:

inOrderTraverse(node, callback) < if(node != null) < this.inOrderTraverse(node.left, callback); callback(node.data); this.inOrderTraverse(node.right, callback); >>

Следующая диаграмма показывает путь нашего inOrderTraverse :

Прямой обход

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

preOrderTraverse(node, callback) < if(node != null) < callback(node.data); this.preOrderTraverse(node.left, callback); this.preOrderTraverse(node.right, callback); >>

Обратный обход

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

postOrderTraverse(node, callback) < if(node != null) < this.postOrderTraverse(node.left, callback); this.postOrderTraverse(node.right, callback); callback(node.data); >>

Поиск значений в BST

В нашей реализации node представляет текущий узел, а data — искомое значение:

search(node, data) < if(node === null) < return null; >else if(data < node.data) < return this.search(node.left, data); >else if(data > node.data) < return this.search(node.right, data); >else < return node; >>

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

Удаление узла из BST

Метод remove — самый сложный из методов, которые мы рассматриваем в этой статье. Его сложность связана с тем, что нам нужно обрабатывать разные сценарии, к тому же рекурсивно.

remove(data) < this.root = this.removeNode(this.root, data); // helper method below >removeNode(node, data) < if(node === null) < return null; // if data to be deleted is less than the root's data, move to the left subtree >else if(data < node.data) < node.left = this.removeNode(node.left, data); return node; // if data to be deleted is greater than the root's data, move to the right subtree >else if(data > node.data) < node.right = this.removeNode(node.right, data); return node; // if data is similar to the root's data, delete the node >else < // delete node with no children (leaf node) if(node.left === null && node.right === null) < node = null; return node; >// delete node with one child if(node.left === null) < node = node.right; return node; >else if(node.right === null) < node = node.left; return node; >// delete node with two children // minimum node of the right subtree is stored in newNode let newNode = this.minNode(node.right); node.data = newNode.data; node.right = this.removeNode(node.right, newNode.data); return node; > >

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

Удаление листового узла

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

Удаление узла с одним потомком

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

Удаление узла с двумя потомками

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

1. Найдя узел, который нужно удалить, нужно найти минимальный узел из его правого поддерева (на диаграмме — затененная часть дерева).
2. Далее вы можете обновить значение удаляемого узла, назначив ему ключ минимального узла из его правого поддерева. Таким образом вы замените ключ узла, а это означает, что узел будет эффективно удален.
3. Теперь у вас в дереве есть два узла с одинаковым ключом, чего не должно быть (на диаграмме — 18). Вам нужно удалить минимальный узел из правого поддерева, поскольку теперь он встал на место удаленного узла.
4. Наконец, надо возвратить ссылку на обновленный узел его родителю.

Заключение

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

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

Источник