Двоичное дерево
Последнее обновление
Двоичное дерево — это иерархия, в которой каждый узел имеет не более двух потомков, называемых левым и правым потомком. Верхний узел — корень, узлы без потомков — листья, а число рёбер от корня до самого глубокого листа — это высота дерева. В отличие от двоичного дерева поиска, у обычного двоичного дерева нет правила упорядочивания — это только форма. Нажмите «воспроизвести» выше, чтобы увидеть, как дерево заполняется уровень за уровнем, а затем обходится симметрично (левый, узел, правый).
Двоичные деревья лежат в основе многих структур — двоичных деревьев поиска, куч, деревьев выражений и других. Обходы посещают каждый узел в определённом порядке: симметричный (in-order), прямой (pre-order) и обратный (post-order) — это три обхода в глубину, каждый полезен для своих задач.
Терминология
| Термин | Значение |
|---|---|
| Корень | Верхний узел, без родителя |
| Лист | Узел без потомков |
| Высота | Самый длинный путь от корня до листа (в рёбрах) |
| Глубина | Расстояние узла от корня |
| Полное | Все уровни заполнены, кроме, возможно, последнего, который заполняется слева направо |
Три обхода в глубину
| Обход | Порядок | Типичное применение |
|---|---|---|
| Симметричный (in-order) | Левый, узел, правый | Отсортированный вывод BST |
| Прямой (pre-order) | Узел, левый, правый | Копирование / сериализация дерева |
| Обратный (post-order) | Левый, правый, узел | Удаление / вычисление дерева |
Разобранный пример
Симметричный обход дерева, построенного из [4, 2, 6, 1, 3, 5] (заполненного уровень за уровнем):
| Шаг | В узле | Действие |
|---|---|---|
| 1 | 4 | Рекурсия в левое поддерево 4 до его посещения |
| 2 | 2 | Рекурсия в левое поддерево 2 до его посещения |
| 3 | 1 | Лист, нет левого потомка: посещаем 1, вывод [1] |
| 4 | 2 | Левое завершено: посещаем 2, вывод [1, 2], затем рекурсия вправо |
| 5 | 3 | Лист: посещаем 3, вывод [1, 2, 3] |
| 6 | 4 | Левое поддерево завершено: посещаем 4, вывод [1, 2, 3, 4], затем рекурсия вправо |
| 7 | 5 | Левый потомок 6, лист: посещаем 5, вывод [1, 2, 3, 4, 5] |
| 8 | 6 | Левое завершено, нет правого потомка: посещаем 6, вывод [1, 2, 3, 4, 5, 6] |
Когда использовать двоичное дерево
| Используйте, когда | Избегайте, когда |
|---|---|
| Нужно моделировать по своей природе иерархические данные (файловые системы, деревья выражений, DOM) | Данные плоские и подошёл бы список или массив — дерево лишь добавляет накладные расходы |
| Нужны упорядоченные операции и вы можете держать его сбалансированным (BST или самобалансирующееся дерево) | Нужен поиск по ключу за среднее O(1) — хеш-таблица превосходит любое дерево |
| Нужно обрабатывать структурированные данные в симметричном, прямом или обратном порядке | Узлы вставляются в отсортированном порядке в несбалансированный BST — он вырождается в список O(n) |
| Важны запросы по диапазону или упорядоченный обход, чего хеш-таблицы не дают | Память ограничена — каждый узел несёт два указателя на потомков помимо полезных данных |
Код Binary Tree
Чистая, готовая к запуску реализация Binary Tree на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Binary Tree на Python
Python
1from collections import deque2
3
4class Node:5 def __init__(self, value):6 self.value = value7 self.left = None8 self.right = None9
10
11def insert(root, value):12 # Level-order insert: fill the first empty child slot found13 if root is None:14 return Node(value)15 queue = deque([root])16 while queue:17 node = queue.popleft()18 if node.left is None:19 node.left = Node(value)20 return root21 queue.append(node.left)22 if node.right is None:23 node.right = Node(value)24 return root25 queue.append(node.right)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36 root = insert(root, value)37
38print("Root: ", root.value)39print("Inorder:", inorder(root))Код Binary Tree на JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinaryTree {10 constructor() {11 this.root = null;12 }13
14 // Insert at the first free spot, top to bottom (level order)15 insert(value) {16 const node = new Node(value);17 if (!this.root) {18 this.root = node;19 return;20 }21 const queue = [this.root];22 while (queue.length > 0) {23 const current = queue.shift();24 if (!current.left) {25 current.left = node;26 return;27 }28 if (!current.right) {29 current.right = node;30 return;31 }32 queue.push(current.left, current.right);33 }34 }35
36 inorder(node = this.root, out = []) {37 if (!node) return out;38 this.inorder(node.left, out);39 out.push(node.value);40 this.inorder(node.right, out);41 return out;42 }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));Код Binary Tree на Java
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 static class Node {6 int value;7 Node left, right;8 Node(int value) { this.value = value; }9 }10
11 static Node root;12
13 // Insert at the first free slot in level order (keeps the tree complete)14 static void insert(int value) {15 Node node = new Node(value);16 if (root == null) { root = node; return; }17 Queue<Node> queue = new ArrayDeque<>();18 queue.add(root);19 while (!queue.isEmpty()) {20 Node cur = queue.poll();21 if (cur.left == null) { cur.left = node; return; }22 if (cur.right == null) { cur.right = node; return; }23 queue.add(cur.left);24 queue.add(cur.right);25 }26 }27
28 // Inorder: left subtree, node, right subtree29 static void inorder(Node node, StringBuilder sb) {30 if (node == null) return;31 inorder(node.left, sb);32 sb.append(node.value).append(" ");33 inorder(node.right, sb);34 }35
36 public static void main(String[] args) {37 for (int v = 1; v <= 7; v++) insert(v);38 StringBuilder sb = new StringBuilder();39 inorder(root, sb);40 System.out.println("Root: " + root.value);41 System.out.println("Inorder: " + sb.toString().trim());42 }43}Код Binary Tree на C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else root->right = insert(root->right, value);14 return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19 if (node == nullptr) return;20 inorder(node->left);21 std::cout << node->value << " ";22 inorder(node->right);23}24
25int countNodes(const Node* node) {26 if (node == nullptr) return 0;27 return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31 Node* root = nullptr;32 for (int value : {8, 3, 10, 1, 6, 14, 4}) {33 root = insert(root, value);34 }35 std::cout << "In-order: ";36 inorder(root);37 std::cout << "\n";38 std::cout << "Node count: " << countNodes(root) << "\n";39 return 0;40}Код Binary Tree на C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* left;7 struct Node* right;8} Node;9
10Node* newNode(int value) {11 Node* n = malloc(sizeof(Node));12 n->value = value;13 n->left = n->right = NULL;14 return n;15}16
17Node* insert(Node* root, int value) {18 if (root == NULL) return newNode(value);19 if (value < root->value) root->left = insert(root->left, value);20 else root->right = insert(root->right, value);21 return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26 if (node == NULL) return;27 inorder(node->left);28 printf("%d ", node->value);29 inorder(node->right);30}31
32int countNodes(const Node* node) {33 if (node == NULL) return 0;34 return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38 int values[] = {8, 3, 10, 1, 6, 14, 4};39 Node* root = NULL;40 for (int i = 0; i < 7; i++) root = insert(root, values[i]);41 printf("In-order: ");42 inorder(root);43 printf("\n");44 printf("Node count: %d\n", countNodes(root));45 return 0;46}Часто задаваемые вопросы о двоичных деревьях
В чём разница между двоичным деревом и двоичным деревом поиска?
Двоичное дерево просто ограничивает каждый узел не более чем двумя потомками, без всякого упорядочивания. Двоичное дерево поиска добавляет правило, что всё в левом поддереве меньше, а всё в правом поддереве больше, что и делает поиск быстрым.
Что такое симметричный (in-order) обход?
Симметричный обход рекурсивно посещает левое поддерево, затем узел, затем правое поддерево. Для двоичного дерева поиска это даёт значения в порядке возрастания, поэтому это самый распространённый обход для демонстрации.
Что такое полное двоичное дерево?
У полного двоичного дерева все уровни полностью заполнены, кроме, возможно, последнего, который заполняется слева направо. Такая форма позволяет компактно хранить дерево в массиве (без указателей на потомков), именно так реализуются двоичные кучи.
Когда стоит использовать двоичное дерево вместо массива или хеш-таблицы?
Обращайтесь к дереву, когда ваши данные естественно иерархичны или когда нужны упорядоченные операции вроде запросов по диапазону и отсортированного обхода, чего хеш-таблицы предложить не могут. Если нужен только быстрый поиск по ключу без упорядочивания, среднее
O(1) обращение хеш-таблицы превосходит дерево, а для плоских данных массив проще и лучше работает с кешем.В чём разница между высотой и глубиной двоичного дерева?
Глубина измеряется от корня вниз до конкретного узла: число рёбер на пути от корня до этого узла. Высота измеряется от узла вниз до его самого глубокого листа, поэтому высота всего дерева — это глубина его самого глубокого узла. Дерево из одного узла имеет высоту
0, и его единственный узел также имеет глубину 0.Почему несбалансированное двоичное дерево работает так плохо?
Поиск, вставка и удаление в двоичном дереве поиска стоят
O(h), где h — высота. Когда ключи вставляются в отсортированном порядке, дерево превращается в прямую линию, поэтому h растёт до n, и каждая операция вырождается в O(n) — не лучше связного списка. Самобалансирующиеся деревья, такие как AVL или красно-чёрные, удерживают высоту на уровне O(log n), чтобы этого избежать.Связанные ресурсы
Больше визуализаций
