AVL-дерево. Начало.

Прежде чем погружаться в понятия и код, разберемся с базой: что это и зачем.

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

AVL-дерево, в свою очередь, - самобалансирующаяся разновидность бинарного дерева поиска.

Что это значит?

Это значит, что в AVL-дереве за гарантированное O(log N) выполняются:

- вставка
- удаление
- поиск.

Фантастические показатели! В AVL-дереве с ~1.000.000 элементов поиск будет выполнен, в худшем случае, за 20 операций. Гарантированно.

Обычное бинарное дерево поиска не похвастается такими показателями. Почему? Если последовательно добавлять элементы по возрастанию или убыванию, BST радостно выродится в связанный список.

Цена производительности - сложность. AVL-дерево сходу поймет далеко не каждый программист, а на доске напишет разве что человек дождя. Если данные нужно часто вставлять и удалять, то появляются дополнительные накладки на вращения. Эту проблему решают Красно-Чёрные деревья, более популярный вид сбалансированных структур.

В следующем посте я опишу основные сущности и операции, а после перейдем к коду.

#AVL #деревья #структурыДанных

AVL-дерево. Сущности и методы.

Элементарные и не очень составляющие структуры, такие как поля класса, я называю сущностями. Действия над ними - методами.

Сущности AVL-дерева, помимо типичных для BST:

- height: поле отдельно взятой ноды, описывающее количество нисходящих нод от неё до листа. По высоте root-ноды дерева определяется и высота дерева (а по высоте - N в log N). Используется для вычисления balance factor.
- balance factor: поле отдельно взятой ноды, описывающее разницу между высотами её правого и левого поддеревьев. Это как весы. Нормальный вес колеблется в пределах [-1, 0, 1]; показатели выше или ниже вызывают вращения дерева.

Методы AVL-дерева:

- обычные для BST операции вставки, удаления, поиска, получения минимального и максимального элементов. Вставка и удаление отличаются тем, что после рекурсивного вызова описаны действия над высотой и balance factor-ом, а также балансировка. Рекурсия помогает обойти дерево в высоту в обратном порядке: это ключ к пониманию балансировки деревьев. Обратный обход можно сделать и явно, с помощью итерации и стека, но я не вижу в этом смысла: код усложнится, а выигрыша по скорости нет.
- balance: метод, внутри которого вызываются вращения.
- setbalanceFactor: вычисляет показатель этого поля.
- setHeight: устанавливает изначальный показатель высоты ноды.
- updateHeight: обновляет высоту на основе высот потомков.
- rotate: вращают дерево. Бывают четырёх видов: влево, вправо, вправо-влево, влево-вправо.

В следующем посте покажу дерево, а после - подробно опишу методы.

#AVL #деревья #структурыДанных

AVL-дерево. Код

Прежде чем разбирать методы, посмотрим на готовое дерево:

class AVLNode {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
        this.height = 1;
        this.balanceFactor = 0;
    }
}

class AVLTree {
    constructor() {
        this.root = null;
    }

    search(key) {
        const _search = (node, key) => {
            if(!node) {
                return null;
            }

            if(node.key === key) {
                return node;
            }

            if(key > node.key) {
                return _search(node.right, key);
            }

            return _search(node.left, key);
        }

        return _search(this.root, key);
    }

    /** обоабатывает случаи с null-нодами */
    getHeight(node) {
        return node ? node.height : 0;
    }

    setBalanceFactor(node) {
        node.balanceFactor = this.height(node.left) - this.height(node.right);
        return node;
    }

    /** Вычисляет высоту ноды на основе двух потомков  */
    updateHeight(node) {
        node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
    }

    rotateRight(x) {
        const y = x.left;
        const T2 = y.right;

        y.right = x;
        x.left = T2;

        this.updateHeight(x);
        this.updateHeight(y)

        return y;
    }

    rotateLeft(x) {
        const y = x.right;
        const T2 = y.left;

        y.left = x;
        x.right = T2;

        this.updateHeight(x);
        this.updateHeight(y)

        return y;
    }

    rotateRightLeft(x) {
        x.right = this.rotateRight(x.right)
        return this.rotateLeft(x);
    }

    rotateLeftRight(x) {
        x.left = this.rotateLeft(x.left)
        return this.rotateRight(x);
    }

    balance(node, key) {
        const balanceFactor = node.balanceFactor;

        if(balanceFactor < -1) {
            if(key > node.right.key) {
                return this.rotateLeft(node);
            }
            return this.rotateRightLeft(node);
        } else if(balanceFactor > 1 ) {
            if(key < node.left.key) {
                return this.rotateRight(node);
            }
            return this.rotateLeftRight(node);
        }

        return node;
    }


    add(key) {
        const _add = (node, key) => {
            if(node === null) {
                return new AVLNode(key);
            }

            if(node.key > key) {
                node.left = _add(node.left, key, node);
            } else if(node.key < key) {
                node.right = _add(node.right, key, node);
            }

            this.updateHeight(node);
            this.setBalanceFactor(node);

            return this.balance(node, key)
        }

        this.root = _add(this.root, key, null);
        return this;
    }

    delete(key) {
        const _delete = (node, key) => {
            if(!node) {
                return node;
            }

            if(node.key > key) {
                node.left = _delete(node.left, key)
            } else if(node.key < key) {
                node.right = _delete(node.right, key)
            } else {
                if(!node.left) {
                    return node.right;
                }
                if(!node.right) {
                    return node.left;
                }

                const theBiggerLeft = this.getMax(node.left);
                node.key = theBiggerLeft.key;
                node.left = _delete(node.left, theBiggerLeft.key)
            }

            this.updateHeight(node);
            this.setBalanceFactor(node);
            return this.balance(node);
        }

        this.root = _delete(this.root, key);
        return this;
    }

    getMin(node) {
        if(!node.left) {
            return node;
        }
        return this.getMin(node.left)
    }

    getMax(node) {
        if(!node.right) {
            return node;
        }
        return this.getMax(node.right)
    }
}

#AVL #деревья #структурыДанных

AVL-дерево. Методы, часть 1

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

- getHeight(node)
Возвращает либо значение height для текущей ноды, либо 0, если нода является листом (null).

- updateHeight(node)
Докидывает +1 к вершине ноды на пути обратной рекурсии.

- setBalanceFactor(node)
На основе вершин потомков вычисляет balanceFactor, по которому алгоритм определяет, нужно ли вращение. Возвращает ноду для удобства.

#AVL #деревья #структурыДанных