Сбалансированные бинарные деревья

Давайте погрузимся в прекрасный мир сбалансированных бинарных деревьев!

Как мы видели в предыдущей статье, бинарные деревья помогают выполнять операции поиска. Однако то, как они расположены, существенно влияет на исполнение. Взгляните на следующее дерево:

Это соответствует определению BST: для каждого узла левый дочерний элемент имеет более низкое значение, а правый дочерний элемент имеет более высокое значение. Однако вы можете быстро увидеть, что есть только правильные дети. В таком случае, если вы хотите найти, существует ли крайнее правое значение, вам придется сделать столько сравнений, сколько узлов в дереве. В этом случае, чтобы найти 70, вам нужно будет сделать 5 сравнений.

Конечно, имея всего 5 значений в дереве, это не займет много времени. Но если бы у вас была такая же древовидная структура с сотнями миллионов значений, это заняло бы значительно больше времени.

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

Прежде чем перейти к определению, вот несколько интересных свойств бинарного дерева размера n:

• максимальная высота будет n — 1
• минимальная высота будет пол(log2(n))

Сбалансированные деревья

Сбалансированное бинарное дерево — это BST, обладающее следующими свойствами:

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

Сбалансированная версия предыдущего дерева будет выглядеть так:

Как видите, это дерево сбалансировано. Между левым и правым поддеревьями узла никогда не бывает разницы более 1. Здесь для поиска числа 70 требуется всего 3 сравнения. И это дерево имеет высоту 2, что является минимально возможной высотой для дерева из 5 узлов.

Теперь представьте дерево, содержащее миллион значений.

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

Это означает, что вам нужно будет выполнить максимум 19 операций, чтобы определить, существует ли значение в этом дереве. Довольно круто.

Проверить, сбалансировано ли дерево

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

Функция для этого будет сравнивать высоту. Но вместо использования функции высоты мы будем каждый раз вычислять и левую, и правую высоты и сравнивать их. Если разница равна 0 или 1 по модулю и оба поддерева сбалансированы, мы возвращаем фактическую высоту. В любом другом случае мы возвращаем -1.

Функция будет выглядеть так

function balanced_height(node: TreeNode)
    if node is null
        return  0
    endif
    const left = is_balanced(node.left)
    if left == -1
        return -1
    endif
    const right = is_balanced(node.right)
    if right == -1
        return -1
    endif
    if Math.abs(left - right) > 1
        return -1
    endif
    return Math.max(left, right) + 1

function is_balanced(node: TreeNode)
  return balanced_height(node) != 0

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

Сбалансированные деревья отлично подходят для быстрого поиска. Но что произойдет с ними, если вы начнете добавлять ценности?

Довольно легко увидеть, что если вы добавляете значения одно за другим, ваше дерево по-прежнему будет BST, но оно быстро перестанет быть сбалансированным.

К счастью, это можно отследить. Было создано много типов самосознательных деревьев. Что они делают, так это всякий раз, когда дерево становится несбалансированным, они выполняют новые типы операций, чтобы снова стать сбалансированным.

Мы называем такие деревья самобалансирующимися.

В следующей статье мы сосредоточимся на одном из них, дереве AVL.

Статьи по Теме: