> Что такое сбалансированное дерево (Go)

Сбалансированное дерево - это структура данных, в которой высота поддеревьев каждого узла отличается не более чем на заданную константу (обычно 1). Это гарантирует, что операции поиска, вставки и удаления выполняются за O(log n) в худшем случае, предотвращая вырождение в линейный список.

В Go сбалансированные деревья часто реализуются через AVL-деревья или красно-черные деревья. Например, в стандартной библиотеке container/ring нет сбалансированных деревьев, но их можно реализовать вручную. Вот пример простой проверки баланса для AVL-дерева:

GO
type Node struct {
    Key    int
    Value  interface{}
    Left   *Node
    Right  *Node
    Height int
}

func getHeight(n *Node) int {
    if n == nil {
        return 0
    }
    return n.Height
}

func isBalanced(n *Node) bool {
    if n == nil {
        return true
    }
    leftH := getHeight(n.Left)
    rightH := getHeight(n.Right)
    diff := leftH - rightH
    if diff < -1 || diff > 1 {
        return false
    }
    return isBalanced(n.Left) && isBalanced(n.Right)
}

В реальных проектах Go для сбалансированных деревьев часто используют сторонние библиотеки, такие как github.com/emirpasic/gods (с реализацией красно-черного дерева) или github.com/google/btree (B-дерево).