Введение

Бинарное дерево поиска хранит значения в упорядоченном виде: левое поддерево каждого узла содержит меньшие значения, а правое поддерево — большие. Такой порядок делает поиск быстрым, но только если дерево остается примерно сбалансированным. Если вставлять значения в обычном бинарном дереве поиска в отсортированном порядке, оно вырождается в прямую линию, превращая каждый поиск в медленное линейное сканирование.

АВЛ-дерево решает эту проблему, автоматически поддерживая свою сбалансированность. После каждой вставки или удаления оно проверяет, не стал ли какой-либо узел перекошенным, и если да, выполняет небольшое локальное исправление, называемое поворотом, для восстановления баланса. Независимо от того, как вы его строите, АВЛ-дерево никогда не вырождается в линию.

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