Ответ
Бинарное дерево поиска (Binary Search Tree, BST) — это бинарное дерево, обладающее следующим ключевым свойством (инвариантом):
Для любого узла
X:
- Все значения в левом поддереве меньше значения
X.- Все значения в правом поддереве больше значения
X.
Это свойство позволяет выполнять эффективный поиск, вставку и удаление элементов.
Реализация вставки в BST (Java):
class BinarySearchTree {
class Node {
int key;
Node left, right;
Node(int key) { this.key = key; }
}
Node root;
// Рекурсивная вставка
Node insert(Node node, int key) {
if (node == null) return new Node(key); // Базовый случай
if (key < node.key)
node.left = insert(node.left, key); // Идём влево
else if (key > node.key)
node.right = insert(node.right, key); // Идём вправо
// Если key == node.key, элемент уже существует (дубликаты могут быть запрещены)
return node;
}
}Важные характеристики:
- Сложность операций: В среднем O(log n), если дерево сбалансировано. В худшем случае (дерево вырождается в линейный список) — O(n).
- Сбалансированные варианты: Для гарантии логарифмической сложности используются расширения BST: AVL-деревья, Красно-чёрные деревья, B-деревья.
- Обход In-order даёт элементы в отсортированном порядке.
Ответ 18+ 🔞
Да ты посмотри на эту штуку, блядь! Бинарное дерево поиска, ёпта! Выглядит как обычное дерево, но с приколом, который мозг выносит, если вдуматься.
Представь себе любого узла X. Так вот, вся левая его родня — это такие скромняги, которые меньше его самого. А правая — это выскочки, которые больше. И так от корня до каждой последней ветки! Это ж надо было додуматься, в рот меня чих-пых! Из-за этой простой хуйни поиск, вставка и удаление становятся быстрыми, как угорелые.
Вот, глянь, как эту красоту в Java впендюрить:
class BinarySearchTree {
class Node {
int key;
Node left, right;
Node(int key) { this.key = key; }
}
Node root;
// Рекурсивная вставка
Node insert(Node node, int key) {
if (node == null) return new Node(key); // Базовый случай
if (key < node.key)
node.left = insert(node.left, key); // Идём влево
else if (key > node.key)
node.right = insert(node.right, key); // Идём вправо
// Если key == node.key, элемент уже существует (дубликаты могут быть запрещены)
return node;
}
}Работает просто: пришло число — пошли с корня сравнивать. Меньше — налево, больше — направо. Дошли до пустоты — вот тебе и дом родной, новый узел. Красота, блядь!
Но тут, сука, есть нюанс, ёпта! Всё это летает со скоростью O(log n), только если дерево сбалансированное, то есть не кривое. А если его кормить отсортированными числами подряд, то оно выродится в обычный линейный список, и все операции будут тормозить как говно в проруби — O(n). Пиздец, а не эффективность.
Поэтому умные дядьки придумали сбалансированные варианты: AVL-деревья, Красно-чёрные деревья, B-деревья. Там уже свои, ёбаные, правила балансировки, чтобы эта хуйня не перекашивалась.
И вишенка на торте: если обойти это дерево In-order'ом (слева-узел-справа), то на выходе получишь все значения уже отсортированными! Вообще ни хуя себе, да? Дерево само за тебя сортирует, пока ты в него что-то пихаешь. Ёперный театр, гениально и просто.