Смотреть алгоритм анимации: Сбалансированное бинарное дерево поиска AVL Tree

Java алгоритм структура данных

Эта статья приняла участие"Проект "Звезда раскопок"", чтобы выиграть творческий подарочный пакет и бросить вызов творческим поощрительным деньгам

«Добро пожаловать для обсуждения в области комментариев, официальный представитель NuggetsПроект «Звезда раскопок»После мероприятия в комментариях будет разыграно 100 штук Наггетсов.Подробнее о лотерее читайте в статье о мероприятии».

Введение

Сбалансированное бинарное дерево поиска — это особый вид бинарного дерева поиска. Почему существует сбалансированное бинарное дерево поиска?

Рассмотрим частный случай бинарного дерева поиска.Если все узлы в бинарном дереве поиска являются правыми узлами, то бинарное дерево поиска вырождается в связанный список. В результате временная сложность поиска становится равной O(n), где n — количество узлов в бинарном дереве поиска.

Сбалансированное бинарное дерево поиска для решения этой возникающей проблемы заключается в ограничении высоты дерева, что уменьшит временную сложность O (logn).

Особенности компании АВЛ

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

Если коэффициент баланса = 0, это означает, что это полностью сбалансированное бинарное дерево.

Если коэффициент баланса = 1, то дерево является сбалансированным бинарным деревом AVL.

То есть коэффициент баланса AVL не может быть больше 1.

Давайте посмотрим на пример AVL:

Подводя итог, AVL — это сначала бинарное дерево поиска, а затем бинарное сбалансированное дерево.

Строительство АВЛ

Учитывая особенности AVL, давайте посмотрим, как устроена AVL.

public class AVLTree {

    //根节点
    Node root;

    class Node {
        int data; //节点的数据
        int height; //节点的高度
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

Точно так же AVL также состоит из различных узлов, и каждый узел имеет несколько атрибутов данных, левый и правый.

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

Есть два вспомогательных метода, один из которых заключается в получении заданной высоты узла:

//获取给定节点的高度
    int height(Node node) {
        if (node == null)
            return 0;
        return node.height;
    }

И получить баланс факторов:

//获取平衡因子
    int getBalance(Node node) {
        if (node == null)
            return 0;
        return height(node.left) - height(node.right);
    }

АВЛ поиск

Метод поиска AVL такой же, как и у бинарного дерева поиска.

Давайте сначала рассмотрим на интуитивном примере, как искать узел 7 в AVL:

Основные этапы поиска:

  1. Начиная с корневого узла 15, сравните размер корневого узла и значение поиска.
  2. Если значение поиска меньше, чем значение узла, то рекурсивно искать левое дерево
  3. Если значение поиска больше, чем значение узла, то рекурсивно ищите правильное дерево.
  4. Если узел совпадает, он будет возвращен напрямую.

Соответствующий Java-код выглядит следующим образом:

//搜索方法，默认从根节点搜索
    public Node search(int data){
        return search(root,data);
    }

    //递归搜索节点
    private Node search(Node node, int data)
    {
        // 如果节点匹配，则返回节点
        if (node==null || node.data==data)
            return node;

        // 节点数据大于要搜索的数据，则继续搜索左边节点
        if (node.data > data)
            return search(node.left, data);

        // 如果节点数据小于要搜素的数据，则继续搜索右边节点
        return search(node.right, data);
    }

Вставка АВЛ

Вставка AVL аналогична вставке BST, но после вставки дерево может быть не сбалансировано, поэтому нам нужно выполнить шаг перебалансировки.

Посмотрите интуитивно понятную анимацию:

Логика вставки следующая:

  1. Начиная с корневого узла, сравните данные узла с данными, которые нужно вставить.
  2. Если вставляемые данные меньше, чем данные узла, рекурсивная вставка левого поддерева
  3. Если вставляемые данные больше, чем данные узла, то рекурсивная вставка правого поддерева
  4. Если корневой узел пуст, вставьте текущие данные в качестве корневого узла.

После вставки данных нам нужно сделать ребалансировку.

Логика ребалансировки следующая:

  1. Найдите первый несбалансированный узел вверх от вставленного узла, который мы обозначаем как z
  2. Z вращение корень поддерева, чтобы получить сбалансированное дерево.

В зависимости от дерева с корнем z у нас есть четыре поворота:

  • слева-налево:

Если это лево-левое дерево, то достаточно правого вращения.

Какие шаги, чтобы повернуть направо?

  1. Найдите левый узел y узла z
  2. Корневой узел как повернутый y
  3. z как правый узел y
  4. Правый узел y действует как левый узел z
  5. обновить высоту z

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

Node rightRotate(Node node) {
        Node x = node.left;
        Node y = x.right;

        // 右旋
        x.right = node;
        node.left = y;

        // 更新node和x的高度
        node.height = max(height(node.left), height(node.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        // 返回新的x节点
        return x;
    }
  • right-right:

Если это дерево справа-направо, ему нужно пройти левый поворот:

Шаги для левого вращения точно противоположны шагам для правого вращения:

  1. Найти правильный узел узла Z Y Y
  3. z как левый узел y
  4. Левый узел y действует как правый узел z
  5. обновить высоту z

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

//左旋
    Node leftRotate(Node node) {
        Node x = node.right;
        Node y = x.left;

        //左旋操作
        x.left = node;
        node.right = y;

        // 更新node和x的高度
        node.height = max(height(node.left), height(node.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        // 返回新的x节点
        return x;
    }
  • лево право:

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

  • право лево:

Если это право-левый формат, вам нужно сначала выполнить правое вращение, преобразовать его в право-правый формат, а затем выполнить левое вращение.

Теперь вопрос, как судить, какого формата дерево? Мы можем судить, получив коэффициент баланса и сравнив вновь вставленные данные:

  1. Если баланс> 1, то мы находимся в случае Лево-лево или Лево-право, В это время нам нужно сравнить размер вновь вставленных данных и node.left.data

    Если data

    Если данные> node.left.data, это означает, что слева направо, вам нужно повернуть node.left влево, а затем повернуть узел вправо

  2. Если баланс node.right.data, это означает, что это случай Right Right, и вам нужно только повернуть его влево.

    Если данные

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

//插入新节点，从root开始
    public void insert(int data){
        root=insert(root, data);
    }

    //遍历插入新节点
    Node insert(Node node, int data) {

        //先按照普通的BST方法插入节点
        if (node == null)
            return (new Node(data));

        if (data < node.data)
            node.left = insert(node.left, data);
        else if (data > node.data)
            node.right = insert(node.right, data);
        else
            return node;

        //更新节点的高度
        node.height = max(height(node.left), height(node.right)) + 1;

        //判断节点是否平衡
        int balance = getBalance(node);

        //节点不平衡有四种情况
        //1.如果balance>1,那么我们在Left Left或者left Right的情况，这时候我们需要比较新插入的data和node.left.data的大小
        //如果data < node.left.data，表示是left left的情况，只需要一次右旋即可
        //如果data > node.left.data，表示是left right的情况，则需要将node.left进行一次左旋，然后将node进行一次右旋
        //2.如果balance<-1,那么我们在Right Right或者Right Left的情况，这时候我们需要比较新插入的data和node.right.data的大小
        //如果data > node.right.data，表示是Right Right的情况，只需要一次左旋即可
        //如果data < node.left.data，表示是Right left的情况，则需要将node.right进行一次右旋，然后将node进行一次左旋

        //left left
        if (balance > 1 && data < node.left.data)
            return rightRotate(node);

        // Right Right
        if (balance < -1 && data > node.right.data)
            return leftRotate(node);

        // Left Right
        if (balance > 1 && data > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Left
        if (balance < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        //返回插入后的节点
        return node;
    }

Удаление АВЛ

Удаление и вставка AVL аналогичны.

Сначала удалить по обычному BST, а потом еще и ребалансировку делать надо.

Посмотрите интуитивно понятную анимацию:

После удаления возможны 4 случая ребалансировки узлов:

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

    Если коэффициент баланса левого узла >=0, это означает, что он левый левый, и требуется только одно правое вращение.

    Если коэффициент баланса левого узла

  2. Если баланс

    Если коэффициент баланса правого узла

    Если коэффициент баланса правого узла > 0, что указывает на случай правого левого, то необходимо провести узел.правый декстрозу, и сразу узел L

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

Node delete(Node node, int data)
    {
        //Step 1. 普通BST节点删除
        // 如果节点为空，直接返回
        if (node == null)
            return node;

        // 如果值小于当前节点，那么继续左节点删除
        if (data < node.data)
            node.left = delete(node.left, data);

        //如果值大于当前节点，那么继续右节点删除
        else if (data > node.data)
            node.right = delete(node.right, data);

       //如果值相同，那么就是要删除的节点
        else
        {
            // 如果是单边节点的情况
            if ((node.left == null) || (node.right == null))
            {
                Node temp = null;
                if (temp == node.left)
                    temp = node.right;
                else
                    temp = node.left;

                //没有子节点的情况
                if (temp == null)
                {
                    node = null;
                }
                else // 单边节点的情况
                    node = temp;
            }
            else
            {  //非单边节点的情况
                //拿到右侧节点的最小值
                Node temp = minValueNode(node.right);
                //将最小值作为当前的节点值
                node.data = temp.data;
                // 将该值从右侧节点删除
                node.right = delete(node.right, temp.data);
            }
        }

        // 如果节点为空，直接返回
        if (node == null)
            return node;

        // step 2: 更新当前节点的高度
        node.height = max(height(node.left), height(node.right)) + 1;

        // step 3: 获取当前节点的平衡因子
        int balance = getBalance(node);

        // 如果节点不再平衡，那么有4种情况
        //1.如果balance>1,那么我们在Left Left或者left Right的情况，这时候我们需要比较左节点的平衡因子
        //如果左节点的平衡因子>=0，表示是left left的情况，只需要一次右旋即可
        //如果左节点的平衡因<0，表示是left right的情况，则需要将node.left进行一次左旋，然后将node进行一次右旋
        //2.如果balance<-1,那么我们在Right Right或者Right Left的情况，这时候我们需要比较右节点的平衡因子
        //如果右节点的平衡因子<=0，表示是Right Right的情况，只需要一次左旋即可
        //如果右节点的平衡因子>0，表示是Right left的情况，则需要将node.right进行一次右旋，然后将node进行一次左旋
        // Left Left Case
        if (balance > 1 && getBalance(node.left) >= 0)
            return rightRotate(node);

        // Left Right Case
        if (balance > 1 && getBalance(node.left) < 0)
        {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Right Case
        if (balance < -1 && getBalance(node.right) <= 0)
            return leftRotate(node);

        // Right Left Case
        if (balance < -1 && getBalance(node.right) > 0)
        {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

Кодовый адрес этой статьи:

learn-algorithm

Эта статья включена вWoohoo. Floyd Press.com/11-AhusbandorIT и…

Самая популярная интерпретация, самая глубокая галантерея, самые краткие уроки и множество трюков, о которых вы не знаете, ждут вас!

Добро пожаловать, чтобы обратить внимание на мой официальный аккаунт: «Программируйте эти вещи», разбирайтесь в технологиях, лучше поймите себя!

Категории