Вот вы, родственная душа, структурирующая данные, которая, наверное, много слышала об этих жутких👹 самобалансирующихся деревьях, которые способны автоматически перебалансировать себя. Звучит как шарм, не так ли?🤩

Давайте узнаем, из чего они сделаны и как это сделать🧑‍💻

Оглавление:

  1. Введение о структурах данных
  2. Проблемы с деревьями
  3. Введение в AVL-деревья
  • фактор баланса: баланс && высота
  • вращения

4. Кодовая часть

5. Окончание

Коротко о деревьях

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

  • Обычные бинарные деревья
  • Двоичные деревья поиска (также известные как BST)
  • Кучи (мин./макс. кучи, кучи Фибоначчи и т. д.)
  • Trie (произносится как t-r-y)
  • Самобалансирующиеся деревья (наиболее известные из них AVL, Red-Black): они происходят от BST.

Зачем они нам нужны?

Например, вам нужно хранить данные и искать их. Какие есть альтернативы?

  • массив: поиск выполняется в среднем за O(n), когда мы просматриваем всю структуру, но все упорядочено
  • хэш-таблица: поиск выполняется в среднем за O(1), поскольку данные находятся внутри слотов памяти, которые не так называемые взаимные ” те. Но это не по заказу.
  • график:сложно/требует использования различных методов и& не идеально подходит для задач, где нужен быстрый поиск
  • наборы: неупорядочены как хэш-таблица. С моей точки зрения, они представляют собой смесь хеш-таблицы и массива, поскольку в них нет пар ключ-значение, как в первом, но они неупорядочены, как в последнем. Однако поиск выполняется за O(1), если вам нужно быстро проверить присутствие.
  • связные списки (двойные и одиночные):хороши для хранения данных, если вам нужен доступ к первому или последнему элементу. Кроме того, помимо массива, где вставка за O(n), так как вам нужно перестроить ссылки в памяти, здесь это намного быстрее, так как вы находите элемент и меняете ссылки с prev и next

Следовательно, что, если нам нужна структура данных для хранения элементов и быстрого их поиска? Деревья — вот ответ. Особенно, когда мы говорим о BST. Поиск/вставка/удаление выполняется за O(log n): мы уменьшаем вдвое поиск на каждом шаге, как и в бинарном поиске.

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

Проблемы с деревьями

Получается, нам вообще не нужна модификация BST? Увы, все намного сложнее😵

Познакомьтесь с асимметрией. Проще говоря, проблема с перекосом дерева в ту или иную сторону, что разрушает его красоту с поиском O(log n). На самом деле он деградирует до O(n).

         n
	/ \
       n   n
      /
     n
    /
   n

Итак, что мы можем с этим поделать? В общем, ничего🤷‍♂️ Но есть другая структура данных, или, скажем так, измененная, известная как самобалансирующаяся BST.

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

АВЛ-деревья

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

Баланс

Tl — левое поддерево, а Tr — правое поддерево.

Формула для роста: H = max(H(Tl), H(Tr)) + 1

Формула для баланса: B(n) = H(Tl) — H(Tr)

Для обучения рассмотрим приведенный ниже пример и рассчитаем. высота и баланс.

Важный момент🤚🤚: долгое время я не мог понять отношения между высотой и балансом. На самом деле они взаимосвязаны. Как? -› Продолжим

Имейте в виду, что высота одного узла равна 0, а отсутствие узла равно -1.

            3
	   / \
	  1   4
	 / \
	0   2

Высота:

  1. Н(0) = макс(-1,-1) + 1 = 0
  2. Н(2) = макс(-1,-1) + 1 = 0
  3. Н(3) = макс(0,0) + 1 = 1
  4. Н(4) = макс(-1,-1) + 1 = 0
  5. Н(3) = макс(1,0) + 1 = 2

Баланс:

  1. B(0) = -1-(-1) = 0
  2. B(2) = -1-(-1)= 0
  3. B(1)=0–0 = 0. Возьмите высоту 0 и высоту 2.
  4. B(4) = -1-(-1)=0
  5. В(3) = 1–0=0. Возьмите высоту 3 и высоту 4.

У нас сбалансированное дерево. Следующим шагом является наблюдение за несбалансированным:

             4
	    /
	   3
	  /
	 2
	/ \
       1   0

Высота:

  1. Н(1) = макс(-1,-1) + 1 = 0
  2. Н(0) = макс(-1,-1) + 1 = 0
  3. Н(2) = макс(0,0) + 1 = 1
  4. Н(3) = макс(1,-1) + 1 = 2
  5. Н(4) = макс(2,-1) + 1 = 3

После быстрого «глазного яблока» мы можем сделать вывод:

  1. B(1) = -1-(-1) = 0
  2. B(0) = -1 -(-1) = 0
  3. B(2) = 0-0 = 0. Возьмем высоту 1 и 0.
  4. B(3) = 1 -(-1) = 2. Возьмем высоту 2
  5. B(4) = 2-(-1) = 3. Возьмем высоту 3

Итак, это 3. Что это все-таки значит? Как мы можем это использовать?

Коэффициент баланса

Как правило, определенный баланс равен абс (1). Это означает, что если какая-то часть больше 1 или меньше -1 => асимметрия. Но почему у нас вообще есть положительный и отрицательный коэффициент баланса? Это связано с так называемой тяжестью.

Дерево с левым и правым — это дерево, поддерево которого наклонено в сторону одного из поддеревьев. Под поддеревьями я подразумеваю не root, а любые node с поддеревьями. т.е. на картинке выше узел 3 можно считать узлом с левым весом, а не только 4. Имейте это в виду.

Слева жирный: коэффициент положительного баланса больше 1

Справа жирный: отрицательный коэффициент баланса меньше -1

Вращения

Очевидный шаг — каким-то образом перебалансировать дерево, чтобы снова сбалансировать его, для этого мы здесь и собрались. Есть 4 основных способа сделать это:

  • Левое вращение (также известное как лево-левое)
  • Правое вращение (также известное как правое право)
  • Вращение влево-вправо
  • Вращение вправо-влево

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

Левое тяжелое дерево: правое вращение && вращение влево-вправо

Правое тяжелое дерево: вращение влево и вращение вправо-влево

После того, как мы определили их подгруппы, давайте углубимся в конкретные случаи их применения.

Правильный поворот

У нас есть следующее дерево, которое явно несбалансировано, 2 — это баланс, и мы хотим это исправить.

     3       2
    /	    / \
   2    => 1   3
  /
 1

Позвольте мне показать вам одну интересную схему:

           x
          / \
         y  purple
        / \
      red blue

Вот способ обращения с деревьями, который мне помог. Смотри, 3 — это х, 2 — это у, а 1 — красный. Вы знаете, как они будут выглядеть после правильного поворота?

      y
     / \
   red  x
       / \
     blue purple

Почему так? => напомню, что это форма BST, где левый угол меньше узла выше, а правый больше/равен. синий больше y, но меньше x. red меньше, чем x и y. фиолетовый больше x. Мы тянем y выше, помещаем x в правую часть, кладем синий слева от x, фиолетовый опускается справа от x, а красный тянет вверх слева от y (точно, это мало что меняет).

Следовательно, в приведенном выше примере мы тянем 2 вверх (это y), помещаем x вправо, красный, равный 1, остается прежним. Если справа от 2 было 2, куда оно пойдет? => сначала справа от 2, а затем слева от 3.

Поворот влево-вправо

            3       3     2
	   /       /     / \
	  1   =>  2  => 1   3 
	   \     /
	    2   1

Здесь мы не можем просто сделать правильное вращение. Почему? Давай попробуем:

    3       1
   /         \
  1   =>      3
   \         /
    2       2

Совсем не сбалансирован. Вот почему нам нужно сделать трюк и сначала сделать левое вращение для 1 и 2. После этого сделать правое вращение для всего дерева. Вы можете увидеть это на одну картинку раньше.

Не бойтесь, если вы не знаете, я предоставлю отрывок кода

Вращение влево

        1                2
	 \              / \
	  2      =>    1   3
	   \
	    3

Похоже на справа, но в зеркальном отображении.

До:

           x
          / \
      purple y 
            / \
          red blue

После:

        y
       / \
      x  blue
     / \
 purple red

Почему так? => фиолетовый — самый маленький. red больше, чем x, но меньше, чем y. синий — больше, чем x && y. После поворота все выглядит как справа.

Вращение вправо-влево

        1        1          2  
	 \        \        / \
	  3  =>    2   => 1   3
	 /          \
	2            3

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

Если у вас что-то не получается, напишите сообщение в комментариях, и я смогу вам помочь!🙌

Я знаю, что это было тяжело😓. Отдохните немного и посмотрите на следующую картинку…

Кодовая часть

Вы можете перейти по следующей ссылке на мой репозиторий, если хотите увидеть весь код, написанный на Python и Kotlin.



Самобалансирующиеся деревья/AVL_trees на главном · SleeplessChallenger/Самобалансирующиеся деревья
Объяснение и код для самобалансирующихся деревьев. Внесите свой вклад в разработку SleeplessChallenger/Self-Balancing-Tree с помощью…github.com



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

Представьте, что у нас есть следующее дерево, и 7 — это наш недавно добавленный узел.

      13
     /  \
   11   21
   /
  8
 /
7

Ясно, что дерево несбалансированное и тяжелое слева. Вспомните примечание выше: не только root служит x из схем в предыдущем секторе. В нашем случае это будет 11, что заметит разницу.

Этапы обработки метода:

Листовой узел — это узел, у которого нет левого или правого дочернего элемента.

1. Вставьте в правильную позицию новое значение в качестве узла LEAF
2. Обновите высоту
3. Проверьте баланс
4. По мере рекурсивного входа в дерево мы
возвращайтесь слой за слоем, обновляя высоту и проверяя
баланс. Следовательно, в один момент мы можем поймать несбалансированный материал

И мы поймали его в 11 🧐

Подожди, подожди, подожди... Как ты это заметил? Мне не дали ни копейки, как это работает😩

Отступление:

  1. Базовый случай: если node равно None, мы возвращаем наш новый узел.
  2. Прикрепляем его либо к левому, либо к правому дочернему элементу. В нашем случае:
8.left = Node(7)

3. Увеличиваем height на 1 и проверяем, что с балансом все в порядке
4. Снова возвращаемся на предыдущий слой на return root и здесь:

11.left = Node(8)

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

Возвращаясь из отступления

  1. Мы видим, что дерево смещено влево, поэтому мы вводим curr_balance > 1
  2. root в данном случае 11 . Нам нужно выяснить:
    является ли наш новый Node(7) > || < чем .left/.right из root.
    Как видим, он меньше, поэтому делаем только _right_rotate() . Обратите внимание на это ниже
  3. Для пояснения давайте воспользуемся нашими цифрами, чтобы облегчить жизнь. Мы вводим этот метод с 11 равным node
8 = 11.left
None = 8.right

# perform rotation
8.right = 11
11.left = None

4. Затем верните y_node в качестве нового корня для поддерева, а 11 переместится вправо от этого корня. Все как было описано в схемах.

Как вы видите, 8 выскакивает на один слой выше, увлекая за собой 7,
в то время как 11 добирается до .right перетягивания .right из 8, если такое
существует (в нашем случае это None)

Что, если...😲😲😲 мы хотим проиллюстрировать вращение влево-вправо.

  Other nodes
     /
    11
   /
  8
   \
    9

Здесь вместо 7 у нас Node(9)

Весь процесс с размещением узлов такой же. И мы даже снова замечаем проблему в 11. Как? Так:

  • На первой высоте:
    1. H(9) = max(-1,-1) + 1 = 0
    2. H(8) = max(-1, 0) + 1 = 1
    3. H(11) = max(1,-1) + 1 = 2
  • Далее баланс:
    1. B(8) = -1–0 = 0
    2. B(11) = 1-(-1)=2

И теперь вам не терпится увидеть все на схеме, чтобы прояснить ситуацию в голове:

Вы можете еще раз проверить в части влево-вправо, почему простое вращение влево не работает.

Сначала мы делаем _left_rotate() с 11.left, представленным как root. Обратите внимание на метод ниже:

Сравним рисунки и схемы:

9 = 8.right
None = 9.left

# perform rotation
9.left = 8
8.right = None

Это будет выглядеть примерно так:

         11
        /
       9
      /
     8
      \
       None

Затем мы возвращаем 9 как новый .left в 11. Далее мы выполняем _right_rotate() как описано ранее.

Для персональных тренировок: посмотрите на вращение left && вращение right-left

Очень сложная штука👺…

Еще один перерыв перед последним чанком🙌🏻

Удалить узел

Наконец, что, если мы хотим удалить узел? Как дереву удается все держать под контролем?🕵🏻‍♂️

Пример дерева:

# Some nodes
     /
    8
     \
      10
     /  \
    9   11

Представьте, 8 нужно удалить❌ Код ниже и после этого позвольте мне провести вас через него.

Что нужно сделать:

  1. Перемещайтесь рекурсивно, пока не наткнетесь на else в верхней части метода. Это означает, что мы нашли цель node
  2. Мы видим, что .left && .right не пусты, поэтому снова введите else
  3. вызовите ._get_min_value_node(node.right), где мы попытаемся найти наименьшее значение в правом поддереве из текущего удаляемого узла.
  4. Так как мы входим в этот метод с 10 корневым, проверка сначала будет основываться на нем: 10 != None и 10.left != None => снова вызовите этот метод с 10.left, что означает, что 9 будет root для следующего вызова.
  5. 9 != None НО 9.left == None =› вернуть 9 на верхний уровень
  6. Вернитесь к delete_node() и поставьте вместо node.value 8 -›9
  7. Далее нам нужно удалить 9 из этого правого поддерева. Собственно, те же действия, что и выше:
  • Обратите внимание, что мы вызываем delete_node на node.right (9.right который был 8.right)
  • node.left == None в delete_node() — это то место, где мы нажимаем и возвращаем None, поскольку 9.right — это None

8. Пересчитывайте баланс && рост для каждого root

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

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

Outro

Надеюсь, вы пережили это нелегкое путешествие🌊 Оно было определенно сложным, и я уверен, что у вас раскалывается голова🤯

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

PS: большое спасибо -›