Ответ
Поиск в сбалансированном бинарном дереве поиска (например, AVL или красно-чёрном) имеет среднюю и худшую временную сложность O(log n), где n — количество узлов.
Почему O(log n)? Сбалансированность гарантирует, что высота дерева пропорциональна логарифму числа элементов. Каждый шаг поиска делит пространство поиска примерно пополам.
Пример на C#:
public class BinarySearchTree
{
public class Node
{
public int Key;
public Node Left, Right;
public Node(int item) => Key = item;
}
// Рекурсивный поиск
public Node Search(Node root, int key)
{
// Базовый случай: узел не найден или найден
if (root == null || root.Key == key)
return root;
// Ключ меньше корня -> ищем в левом поддереве
if (key < root.Key)
return Search(root.Left, key);
// Иначе ищем в правом
return Search(root.Right, key);
}
}Контраст с несбалансированным деревом: В вырожденном случае (например, когда узлы добавляются по порядку) дерево превращается в связный список, и сложность поиска деградирует до O(n). Сбалансированные деревья (AVL, красно-чёрные) автоматически перестраиваются при вставке/удалении, чтобы избежать этого.
Ответ 18+ 🔞
Давай разберем эту тему про деревья, а то некоторые думают, что это про яблони во дворе.
Ну вот представь: есть у тебя дерево, но не простое, а бинарное и сбалансированное. Это как если бы ты свои носки в комоде не просто в кучу кидал, а аккуратно по парам и по цветам разложил. Ищешь синий носок — открыл один ящик, потом половину отложил, потом ещё половину... и вот он, сука, нашёлся! Всё потому, что каждый раз ты отбрасываешь к хуям кучу ненужных вариантов.
Так вот, сложность поиска в таком правильном дереве — O(log n). Это значит, что даже если у тебя там миллион записей, тебе надо сделать всего-то около 20 шагов. Логарифм, блядь! Магия! Дерево-то сбалансированное, высота у него растёт овердохуища медленнее, чем количество узлов.
А теперь смотри на этот код, тут всё просто:
public class BinarySearchTree
{
public class Node
{
public int Key;
public Node Left, Right;
public Node(int item) => Key = item;
}
// Рекурсивный поиск
public Node Search(Node root, int key)
{
// Базовый случай: узел не найден или найден
if (root == null || root.Key == key)
return root;
// Ключ меньше корня -> ищем в левом поддереве
if (key < root.Key)
return Search(root.Left, key);
// Иначе ищем в правом
return Search(root.Right, key);
}
}Работает по принципу "разделяй и властвуй". Ищешь число — сравнил с корнем, пошёл налево если меньше, направо если больше. И так рекурсивно, пока не упрёшься либо в нужный узел, либо в пустоту.
А теперь, внимание, соль земли: если дерево несбалансированное, то это пиздец, а не структура. Представь, что ты добавляешь числа по порядку: 1, 2, 3, 4... Дерево вырождается в обычный связный список, длинный такой, кривой. И чтобы найти четвёрку, тебе придётся пройтись по всем предыдущим, то есть O(n). Полный ахтунг!
Поэтому умные дядьки придумали AVL и красно-чёрные деревья. Они как заботливые родители — следят, чтобы детишки-узлы не росли кособоко. После каждой вставки или удаления там идёт перебалансировка, подкрутка, чтобы дерево не превратилось в ту самую грёбаную верёвку из узлов.
Короче, смысл в том, что log n — это охуенно быстро, а n — это уже повод задуматься, что ты делаешь не так. Вот и вся философия, если в двух словах.