← Назад к вопросам
Как в бинарном дереве поиска располагаются элементы
1.8 Middle🔥 111 комментариев
#Коллекции
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Ответ
Бинарное дерево поиска (BST — Binary Search Tree) — это структура данных, где элементы расположены по очень специфичному правилу, которое позволяет быстро искать элементы.
Основное правило BST
Для каждого узла:
- ВСЕ элементы в ЛЕВОМ поддереве < текущий узел
- ВСЕ элементы в ПРАВОМ поддереве > текущий узел
Пример BST
50
/ \
30 70
/ \ / \
20 40 60 80
/
10
Проверим правило:
50 (корень):
- Слева (30, 20, 10, 40) — ВСЕ < 50 ✓
- Справа (70, 60, 80) — ВСЕ > 50 ✓
30:
- Слева (20, 10) — ВСЕ < 30 ✓
- Справа (40) — ВСЕ > 30 ✓
Реализация BST на Java
public class BinarySearchTree<T extends Comparable<T>> {
private Node<T> root;
private static class Node<T> {
T value;
Node<T> left; // < value
Node<T> right; // > value
Node(T value) {
this.value = value;
}
}
// INSERT — вставка элемента
public void insert(T value) {
root = insert(root, value);
}
private Node<T> insert(Node<T> node, T value) {
if (node == null) {
return new Node<>(value);
}
int cmp = value.compareTo(node.value);
if (cmp < 0) {
// value меньше — идём влево
node.left = insert(node.left, value);
} else if (cmp > 0) {
// value больше — идём вправо
node.right = insert(node.right, value);
}
// Если равны — не вставляем дубликаты
return node;
}
// SEARCH — поиск элемента
public boolean contains(T value) {
return search(root, value) != null;
}
private Node<T> search(Node<T> node, T value) {
if (node == null) {
return null;
}
int cmp = value.compareTo(node.value);
if (cmp < 0) {
// Ищем в левом поддереве
return search(node.left, value);
} else if (cmp > 0) {
// Ищем в правом поддереве
return search(node.right, value);
} else {
// Нашли!
return node;
}
}
// DELETE — удаление элемента
public void delete(T value) {
root = delete(root, value);
}
private Node<T> delete(Node<T> node, T value) {
if (node == null) {
return null;
}
int cmp = value.compareTo(node.value);
if (cmp < 0) {
node.left = delete(node.left, value);
} else if (cmp > 0) {
node.right = delete(node.right, value);
} else {
// Нашли элемент для удаления
// Случай 1: нет детей (листовой узел)
if (node.left == null && node.right == null) {
return null;
}
// Случай 2: один ребёнок
if (node.left == null) return node.right;
if (node.right == null) return node.left;
// Случай 3: два ребёнка
// Находим наименьший элемент из правого поддерева
Node<T> minRight = findMin(node.right);
node.value = minRight.value;
// И удаляем его
node.right = delete(node.right, minRight.value);
}
return node;
}
private Node<T> findMin(Node<T> node) {
while (node.left != null) {
node = node.left;
}
return node;
}
}
Пример использования
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
// Вставляем элементы
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
// Ищем элементы
System.out.println(bst.contains(40)); // true
System.out.println(bst.contains(100)); // false
// Удаляем
bst.delete(30);
System.out.println(bst.contains(30)); // false
In-Order Traversal (упорядоченный обход)
Основное свойство: In-Order обход BST вернёт элементы в отсортированном порядке!
public void inOrder() {
inOrder(root);
System.out.println(); // Выведет: 10 20 30 40 50 60 70 80
}
private void inOrder(Node<T> node) {
if (node == null) return;
inOrder(node.left); // Левое поддерево
System.out.print(node.value + " "); // Текущий узел
inOrder(node.right); // Правое поддерево
}
Сложность операций
┌──────────────┬──────────────┬──────────────┐
│ Операция │ Best Case │ Worst Case │
├──────────────┼──────────────┼──────────────┤
│ Search │ O(log n) │ O(n) │
│ Insert │ O(log n) │ O(n) │
│ Delete │ O(log n) │ O(n) │
└──────────────┴──────────────┴──────────────┘
Best Case — сбалансированное дерево (высота = log n)
Worst Case — вырожденное в список (высота = n)
Сбалансированное vs Несбалансированное
Хорошее (сбалансированное):
50
/ \
30 70
/ \ / \
20 40 60 80
Высота = 3, поиск O(log 8) = O(3)
Плохое (вырожденное):
10
\
20
\
30
\
40
\
50
Высота = 5, поиск O(n) = O(5)
Self-Balancing BST (AVL, Red-Black)
Для обеспечения гарантированной O(log n) сложности используют самобалансирующиеся деревья:
AVL Tree — строго сбалансировано
// Высота левого и правого поддеревьев отличается не более чем на 1
int balanceFactor = getHeight(left) - getHeight(right);
if (Math.abs(balanceFactor) > 1) {
// Необходимен ротация!
}
Red-Black Tree — используется в Java HashMap, TreeMap
// Правила красно-чёрного дерева:
// 1. Каждый узел — красный или чёрный
// 2. Корень всегда чёрный
// 3. Листья (null) — чёрные
// 4. Красный узел не может иметь красных детей
// 5. Все пути от узла до листьев имеют одинаковое количество чёрных узлов
TreeMap в Java (реализация Red-Black Tree)
// TreeMap — это реализация SortedMap на основе Red-Black Tree
TreeMap<Integer, String> map = new TreeMap<>();
map.put(50, "fifty");
map.put(30, "thirty");
map.put(70, "seventy");
map.put(20, "twenty");
map.put(80, "eighty");
// Элементы хранятся в отсортированном порядке!
for (Integer key : map.keySet()) {
System.out.println(key); // Выведет: 20 30 50 70 80
}
// Поиск за O(log n)
String value = map.get(30); // O(log 5)
// Range операции
map.subMap(30, 70); // Элементы от 30 до 70
map.headMap(50); // Элементы < 50
map.tailMap(50); // Элементы >= 50
Сравнение: HashMap vs TreeMap
// HashMap — O(1) поиск, неупорядоченный
HashMap<Integer, String> hmap = new HashMap<>();
hmap.put(50, "fifty");
hmap.put(30, "thirty");
for (Integer key : hmap.keySet()) {
System.out.println(key); // Неопределённый порядок
}
// TreeMap — O(log n) поиск, отсортированный
TreeMap<Integer, String> tmap = new TreeMap<>();
tmap.put(50, "fifty");
tmap.put(30, "thirty");
for (Integer key : tmap.keySet()) {
System.out.println(key); // Всегда: 30, 50
}
Применение BST в реальных задачах
1. Автокomplete / Prefix search
// BST можно использовать для быстрого поиска по префиксу
public List<String> searchByPrefix(String prefix) {
List<String> result = new ArrayList<>();
searchByPrefix(root, prefix, result);
return result;
}
2. Диапазонные запросы
// Найти все элементы в диапазоне [min, max]
public List<Integer> rangeSearch(int min, int max) {
List<Integer> result = new ArrayList<>();
rangeSearch(root, min, max, result);
return result;
}
3. Найти k-й наименьший элемент
// Благодаря In-Order обходу
public Integer findKthSmallest(int k) {
Counter counter = new Counter();
return findKthSmallest(root, k, counter);
}
Визуализация вставок
Вставляем в порядке: 50, 30, 70, 20, 40, 60, 80
Шаг 1: insert(50)
50
Шаг 2: insert(30) — 30 < 50, идём влево
50
/
30
Шаг 3: insert(70) — 70 > 50, идём вправо
50
/ \
30 70
Шаг 4: insert(20) — 20 < 50, влево; 20 < 30, влево
50
/ \
30 70
/
20
И так далее...
Итог
Binary Search Tree:
- ✅ Основное правило: левое < родитель < правое
- ✅ In-Order обход: выдаёт элементы в отсортированном порядке
- ✅ Сложность: O(log n) для поиска, вставки, удаления (в среднем)
- ✅ Худший случай: O(n) при вырождении в список
- ✅ Решение: использовать самобалансирующиеся деревья (AVL, Red-Black)
- ✅ В Java: TreeMap, TreeSet используют Red-Black Tree
- ✅ Приложения: сортировка, диапазонные запросы, автокомплит