Что такое Сбалансированное двоичное дерево и как его проверить?

Автор оригинала: Pankaj Kumar.

В случае двоичных деревьев, если деревья перекошены, они становятся вычислительно неэффективными для выполнения операций.

Это является мотивацией для того, чтобы убедиться, что деревья не перекошены. Отсюда и необходимость в сбалансированных бинарных деревьях.

Что такое Сбалансированное двоичное дерево

Сбалансированные двоичные деревья являются вычислительно эффективными для выполнения операций.

Сбалансированное двоичное дерево будет соответствовать следующим условиям:

Абсолютная разница высот левого и правого поддеревьев в любом узле меньше 1.
Для каждого узла его левое поддерево представляет собой сбалансированное двоичное дерево.
Для каждого узла его правое поддерево представляет собой сбалансированное двоичное дерево.

Бинарные деревья, сбалансированные по высоте

Сбалансированные бинарные деревья также известны как сбалансированные по высоте бинарные деревья. Бинарные деревья, сбалансированные по высоте, могут быть обозначены HB(k), где k-разница между высотами левого и правого поддеревьев. “к” известно как коэффициент баланса.

Если для дерева коэффициент баланса (k) равен нулю, то это дерево известно как полностью сбалансированное двоичное дерево. Его можно обозначить как HB(0) .

Самобалансирующееся Двоичное Дерево Поиска

Если двоичное дерево поиска имеет коэффициент баланса, равный единице, то это AVL ( Адельсон-Вельский и Ландис) дерево. Это означает, что в дереве AVL разница между высотой левого поддерева и правого поддерева составляет не более единицы.

AVL дерево-это самобалансирующееся двоичное дерево поиска. В дереве AVL, если разница между левым и правым поддеревьями больше 1, он выполняет одно из следующих 4 вращений, чтобы сбалансировать себя:

Поворот влево
Поворот вправо
Поворот влево-Вправо
Поворот вправо-Влево

Как проверить, сбалансировано ли двоичное дерево?

Чтобы проверить, сбалансировано ли двоичное дерево, нам нужно проверить три условия:

Абсолютная разница между высотами левого и правого поддеревьев в любом узле должна быть меньше 1.
Для каждого узла его левое поддерево должно быть сбалансированным двоичным деревом.
Для каждого узла его правое поддерево должно быть сбалансированным двоичным деревом.

Нам понадобится функция, которая может вычислить высоту дерева. Один из способов сделать это-написать отдельную функцию для вычисления высоты и вызывать ее каждый раз, когда требуется высота. Это будет вычислительно неэффективно.

Лучшим способом реализации этого будет возврат высоты в той же функции.

Для каждого узла мы вернем -1, если он не сбалансирован, и высоту этого узла/поддерева, если он сбалансирован.

Алгоритм выглядит следующим образом:

Если узел -> возвращает 0
Проверьте левое поддерево. Если не сбалансировано -> вернуть -1
Проверьте правое поддерево. Если не сбалансировано -> вернуть -1
Абсолютное значение между высотами левого и правого поддеревьев. Если оно больше 1 -> верните -1.
Если дерево сбалансировано -> вернуть высоту

Псевдокод будет выглядеть следующим образом:

 private int balanceHeight (TreeNode currentNode)
    {
        if (currentNode == null)
        {
            return 0;
        }

        // checking left subtree
        int leftSubtreeHeight = balanceHeight (currentNode.left);
        if (leftSubtreeHeight == -1) return -1;
        // if left subtree is not balanced then the entire tree is also not balanced

        //checking right subtree
        int rightSubtreeHeight = balanceHeight (currentNode.right);
        if (rightSubtreeHeight == -1) return -1;
        // if right subtree is not balanced then the entire          tree is also not balanced

        //checking the difference of left and right subtree for current node
        if (Math.abs(leftSubtreeHeight - rightSubtreeHeight) > 1)
        {
            return -1;
        }
        //if it is balanced then return the height
        return (Math.max(leftSubtreeHeight, rightSubtreeHeight) + 1);
    }

Вы можете вызвать эту функцию в корне дерева, и если она возвращает что-либо, кроме -1, то это сбалансированное двоичное дерево. Если он возвращает -1, то это не сбалансированное двоичное дерево.

Вывод

В этом уроке мы рассмотрели сбалансированные двоичные деревья и как мы можем проверить, является ли дерево сбалансированным двоичным деревом. Надеюсь, вы поняли и получили удовольствие от обучения у нас.