Библиотека Go-разработчика | Golang: “🌴 Деревья поиска на Go: вставка, поиск, удаление BST

🌴 Деревья поиска на Go: вставка, поиск, удаление

BST — двоичное дерево поиска. Простая идея: левый потомок всегда меньше родителя, правый — больше. Это даёт поиск за O(log n), но только если дерево сбалансировано. Об этом — в конце поста.

Структура узла

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

type BST struct {
    Root *Node
}

Вставка

Идём по дереву вниз: если значение меньше текущего узла — налево, больше — направо. Когда упёрлись в nil — вставляем:

func (t *BST) Insert(val int) {
    t.Root = insert(t.Root, val)
}

func insert(node *Node, val int) *Node {
    if node == nil {
        return &Node{Val: val}
    }
    if val < node.Val {
        node.Left = insert(node.Left, val)
    } else if val > node.Val {
        node.Right = insert(node.Right, val)
    }
    return node
}

Дубликаты здесь просто игнорируются. Можно добавить счётчик в узел, если нужно их хранить.

Поиск

Та же логика, что и вставка, но вместо создания узла возвращаем результат:

func (t *BST) Search(val int) bool {
    return search(t.Root, val)
}

func search(node *Node, val int) bool {
    if node == nil {
        return false
    }
    if val == node.Val {
        return true
    }
    if val < node.Val {
        return search(node.Left, val)
    }
    return search(node.Right, val)
}

Удаление

Три случая:
- узел без потомков — просто удаляем
- узел с одним потомком — заменяем им
- узел с двумя потомками — находим минимальный элемент правого поддерева (in-order successor), ставим его на место удалённого

func (t *BST) Delete(val int) {
    t.Root = deleteNode(t.Root, val)
}

func deleteNode(node *Node, val int) *Node {
    if node == nil {
        return nil
    }
    if val < node.Val {
        node.Left = deleteNode(node.Left, val)
    } else if val > node.Val {
        node.Right = deleteNode(node.Right, val)
    } else {
        if node.Left == nil {
            return node.Right
        }
        if node.Right == nil {
            return node.Left
        }
        // Находим минимум в правом поддереве
        min := findMin(node.Right)
        node.Val = min.Val
        node.Right = deleteNode(node.Right, min.Val)
    }
    return node
}

func findMin(node *Node) *Node {
    for node.Left != nil {
        node = node.Left
    }
    return node
}

Обходы

Три классических варианта, каждый даёт узлы в разном порядке:

// In-order: левый → корень → правый (отдаёт отсортированный список)
func inOrder(node *Node) {
    if node == nil {
        return
    }
    inOrder(node.Left)
    fmt.Println(node.Val)
    inOrder(node.Right)
}

// Pre-order: корень → левый → правый (удобен для копирования дерева)
func preOrder(node *Node) {
    if node == nil {
        return
    }
    fmt.Println(node.Val)
    preOrder(node.Left)
    preOrder(node.Right)
}

// Post-order: левый → правый → корень (удобен для удаления дерева)
func postOrder(node *Node) {
    if node == nil {
        return
    }
    postOrder(node.Left)
    postOrder(node.Right)
    fmt.Println(node.Val)
}

Где ломается BST

Если вставлять элементы по порядку — 1, 2, 3, 4, 5 — дерево вырождается в связный список. Поиск становится O(n) вместо O(log n):

Именно для этого придумали самобалансирующиеся деревья.

💬 Разбирать механизм, который не даёт дереву деградировать?

📍 Навигация: Вакансии • Задачи • Собесы • Канал в Max

🐸 Библиотека Go-разработчика

#ReadySetGo