Поиск по сайту:

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


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

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

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

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

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

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

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

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

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

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

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

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

  • Вращение влево
  • Правильный поворот
  • Вращение влево-вправо
  • Вращение вправо-влево

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

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

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

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

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

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

Алгоритм следующий:

  • Если node == null -> вернуть 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, то это не сбалансированное двоичное дерево.

Заключение

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