Ответ
Бинарное дерево поиска (BST) — это структура данных, где для каждого узла выполняется строгое правило: все значения в левом поддереве меньше значения узла, а все значения в правом — больше.
Алгоритм поиска:
- Начать с корневого узла.
- Сравнить искомое значение с ключом текущего узла.
- Если значения совпадают — узел найден.
- Если искомое значение меньше — перейти к левому дочернему узлу и повторить шаг 2.
- Если искомое значение больше — перейти к правому дочернему узлу и повторить шаг 2.
- Если дочерний узел, к которому нужно перейти, отсутствует (
nil), значит, искомого значения в дереве нет.
Реализация на Go (рекурсивный и итеративный подходы):
package main
type Node struct {
Value int
Left *Node
Right *Node
}
// Рекурсивный поиск
func SearchRecursive(node *Node, target int) *Node {
if node == nil || node.Value == target {
return node
}
if target < node.Value {
return SearchRecursive(node.Left, target)
}
return SearchRecursive(node.Right, target)
}
// Итеративный поиск (более эффективен по памяти)
func SearchIterative(root *Node, target int) *Node {
current := root
for current != nil {
if target == current.Value {
return current
}
if target < current.Value {
current = current.Left
} else {
current = current.Right
}
}
return nil
}Сложность алгоритма:
- В среднем/лучшем случае:
O(log n)— для сбалансированного дерева, так как на каждом шаге мы отсекаем половину оставшихся узлов. - В худшем случае:
O(n)— для несбалансированного (вырожденного) дерева, которое превращается в связный список.
Ответ 18+ 🔞
Вот же ёпта, бинарное дерево поиска! Это ж как в жизни, блядь: всё, что слева — меньше тебя, всё, что справа — больше. Порядок, сука, а не жизнь!
Представь, что ты ищешь ключи от хаты в этой своей, блядь, куче хлама. Алгоритм-то, внатуре, простой, как три копейки:
- Начинаешь с корня, с самого главного узла, блядь.
- Смотришь: а ключ-то, который ищешь, такой же, как у этого узла? Если да — охуенно, нашёл, пиздец!
- Если твой ключ меньше — значит, надо рыться слева, там где всякая хуйня помельче валяется.
- Если больше — ну, понятно, направо, там где покрупнее.
- И так, пока либо не наткнёшься на свои ключи, либо не упрёшься в пустоту — и тогда нихуя не найдёшь, расходимся.
А вот как это выглядит на языке Го, который, блядь, как швейцарские часы, строгий и быстрый:
package main
type Node struct {
Value int
Left *Node
Right *Node
}
// Поиск рекурсивный — красиво, но если дерево глубокое, можно стек, блядь, переполнить
func SearchRecursive(node *Node, target int) *Node {
if node == nil || node.Value == target {
return node // либо нашёл, либо нихуя
}
if target < node.Value {
return SearchRecursive(node.Left, target) // иди налево, сказку слушай
}
return SearchRecursive(node.Right, target) // иди направо, коня потеряешь
}
// Поиск итеративный — вот это по-взрослому, без этих ваших рекурсивных выебонов
func SearchIterative(root *Node, target int) *Node {
current := root
for current != nil {
if target == current.Value {
return current // наконец-то, ебать!
}
if target < current.Value {
current = current.Left // поворачиваем налево
} else {
current = current.Right // поворачиваем направо
}
}
return nil // проехали, хуй с горы, ничего нет
}Ну а теперь про скорость, блядь, самое интересное:
- Если дерево нормальное, сбалансированное — то красота,
O(log n). На каждом шаге половину мусора отбрасываешь, как умный человек. - А если дерево кривое, выродилось в ёбаный список — вот тут пиздец,
O(n). Придётся всё подряд перебирать, как последнему дебилу. Вот за что я не люблю несбалансированные деревья — сплошное разочарование, в рот меня чих-пых!