Ответ
Сложность поиска в бинарном дереве поиска (Binary Search Tree, BST) зависит от его сбалансированности:
- Средний/Лучший случай (для сбалансированного дерева): O(log n), где
n— количество узлов. На каждом шаге алгоритм отбрасывает примерно половину оставшегося поддерева. - Худший случай (для вырожденного дерева — "списка"): O(n). Это происходит, когда каждый узел имеет только одного потомка, и дерево по сути становится линейным связным списком.
Пример рекурсивного поиска в BST на Swift:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val }
}
func search(in root: TreeNode?, value: Int) -> Bool {
// Базовый случай: узел пуст или значение найдено
guard let node = root else { return false }
if node.val == value { return true }
// Рекурсивный случай: идем в левое или правое поддерево
if value < node.val {
return search(in: node.left, value: value)
} else {
return search(in: node.right, value: value)
}
}
// Использование
let root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
print(search(in: root, value: 5)) // true
print(search(in: root, value: 12)) // falseДля гарантированной производительности O(log n) используются самобалансирующиеся деревья (AVL, Красно-черные).
Ответ 18+ 🔞
Давай разберем эту тему про поиск в дереве, но без занудства, а как есть, с душой и примерами.
Представь себе, что у тебя есть дерево, но не простое, а бинарное и поисковое. Идея гениальная, как три копейки: в корне сидит число, слева от него — всё, что меньше, справа — всё, что больше. Красота, да? Искать в таком — одно удовольствие... но только если оно не кривое, блядь.
Вот смотри: если дерево сбалансированное (ветки примерно одной длины, как у приличной елки), то на каждом шаге ты отбрасываешь половину оставшихся узлов. Сложность — O(log n), то есть очень быстро. Это лучший случай, мечта.
А теперь представь, что какое-то чудо построило это дерево как односторонний список. Например, вставляли числа 1, 2, 3, 4 по порядку. Получилась не елка, а хер знает что — палка одна, все узлы только вправо торчат. Это вырожденный случай. Искать в таком — O(n), потому что придется пройтись по всем, как по линейному списку. Короче, пиздец, а не дерево.
Вот тебе код на Swift, как искать рекурсивно. Смотри, тут всё честно:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val }
}
func search(in root: TreeNode?, value: Int) -> Bool {
// Базовый случай: узел пуст или значение найдено
guard let node = root else { return false }
if node.val == value { return true }
// Рекурсивный случай: идем в левое или правое поддерево
if value < node.val {
return search(in: node.left, value: value)
} else {
return search(in: node.right, value: value)
}
}
// Использование
let root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
print(search(in: root, value: 5)) // true
print(search(in: root, value: 12)) // falseВсё просто: если пришли в пустоту — false, если нашли — true, не нашли — идем налево или направо в зависимости от значения. Ёпта, даже обезьяна поймёт.
Но чтобы этот O(log n) был не только в мечтах, а всегда, придумали самобалансирующиеся деревья — AVL, красно-черные и прочие. Они сами себя подкручивают, чтобы не превратиться в ту самую кривую палку. Вот это уже серьёзно, блядь. Без них в продакшене — ни ногой, иначе в один прекрасный день поиск упрётся в O(n), и все накроется медным тазом.