Что такое сбалансированное бинарное дерево и зачем оно нужно?

Ответ

Да, бинарное дерево может и должно быть сбалансированным для эффективной работы.

Сбалансированное бинарное дерево — это такое дерево, у которого для любой его вершины высота левого и правого поддеревьев отличается не более чем на 1.

Зачем это нужно?
Главная цель сбалансированности — гарантировать, что основные операции (поиск, вставка, удаление) будут выполняться за логарифмическое время O(log n). В несбалансированном (вырожденном) дереве, которое превращается в связный список, эти операции могут занимать линейное время O(n), что сводит на нет все преимущества бинарного дерева.

Примеры самобалансирующихся деревьев:

АВЛ-дерево (AVL tree)
Красно-чёрное дерево (Red-Black Tree)

Пример проверки сбалансированности на Go:

// Структура узла дерева
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Функция проверяет, сбалансировано ли дерево
func isBalanced(root *TreeNode) bool {
    // Если checkHeight вернула -1, дерево не сбалансировано
    return checkHeight(root) != -1
}

// Рекурсивная функция для проверки высоты и баланса
// Возвращает высоту поддерева, если оно сбалансировано, иначе -1
func checkHeight(node *TreeNode) int {
    if node == nil {
        return 0
    }

    leftHeight := checkHeight(node.Left)
    if leftHeight == -1 { // Если левое поддерево уже не сбалансировано
        return -1
    }

    rightHeight := checkHeight(node.Right)
    if rightHeight == -1 { // Если правое поддерево уже не сбалансировано
        return -1
    }

    // Проверяем разницу высот
    if leftHeight - rightHeight > 1 || rightHeight - leftHeight > 1 {
        return -1
    }

    // Возвращаем максимальную высоту + 1
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}