Освоение структур данных в Ruby — AVL Trees

Бинарные деревья поиска или же БТС для краткости, это структуры данных, предназначенные для выполнения быстрый поиск в больших наборах данных. Тема этого поста АВЛ-деревья особый вид самобалансирующийся BST назван в честь его создателей Адельсона-Вельского и Лэндиса, где разница высот между левым и правым поддеревьями (коэффициент баланса) всегда находится в диапазоне (-1..1), что дает нам O(log2 n) поисковых запросов.

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

Давайте начнем с рассмотрения того, как работает поиск.

Как работает поиск

В этой структуре данных поиск рекурсивно-потомковые операции сверху вниз; это означает, что они начинают с корневого узла и двигаются вниз до тех пор, пока не найдут ключ, который ищут, или пока не закончатся узлы.

Конечно, просмотр всего дерева был бы непомерно дорогим, но поскольку узлы гарантированно отсортированы, нам не нужно этого делать. Мы начинаем сверху, спускаясь влево или вправо в зависимости от того, как наш ключ сравнивается с текущим узлом.

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

Дерево AVL выглядит примерно так:

          4
         / \ 
        /   \ 
       2     6 
      / \    / \ 
     1   3  5   9 
                / \ 
               7  11

Теперь предположим, что мы хотим найти число 5.

Начиная с корневого узла, путь будет таким:

1. Is 5 == 4?No

2. Is 5 < 4?No. Move right.

3. Is 5 == 6?No

4. Is 5 < 6?Yes. Move left.

5. Is 5 == 5Yes. We found it!

*Примечание. Чтобы упростить процесс поиска, я не стал проверять «конец ветки».

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

Для небольшого количества элементов это не выглядит большой разницей; однако что интересно в деревьях AVL, так это то, что поиск выполняется за время O(log2 n); что обозначает они становятся экспоненциально лучше, чем линейный поиск, по мере роста набора данных.

Например, поиск элемента из миллиона в односвязном списке может потребовать до 1 000 000 обходы. Та же операция с деревьями AVL потребует примерно 20!

Как работают вставки

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

Вращение — это механизм перестановки частей дерева для восстановления его баланса без нарушения следующих свойств:

  • левый ключ < родительский ключ
  • родительский ключ < правый ключ

После того, как вращение завершено, коэффициент баланса всех узлов должны быть в сбалансированном диапазоне (-1..1).

В зависимости от расположения узла, который переводит дерево в несбалансированное состояние, мы должны применить один из этих поворотов (LL, LR, RR, RL). Давайте посмотрим на каждый из них.

ЛЛ (левый-левый)

Предположим, мы хотим добавить число 1 в следующее поддерево:

       /
      6 
     / \ 
    3   7 
   / \ 
 2     4
/ 
x

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

       / 
      6 
     / \ 
    3   7 
   / \ 
  2   4 
 / 
1

Все идет нормально; но теперь у нас есть проблема. После вставки нового узла коэффициент баланса корневого узла поддерева (6) стал +2, что означает, что мы должны сбалансировать дерево, прежде чем продолжить.

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

         / 
        6
       / \ 
  (L) 3   7 
     / \ 
(L) 2   4 
  /
1

В этом случае узел укоренен в левое поддерево левого поддерева узла дисбаланса; следовательно, мы должны сделать лево-левое вращение (ЛЛ).

ЛР (левый-правый)

Теперь давайте посмотрим на право-левое вращение (LR). Поворот, который мы должны применить, когда новый узел лежит на правое поддерево левого поддерева узла, который стал несбалансированным.

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

     / 
    6 
   / \ 
  3   7 
 / \
2   4
     \ 5 (*)

РР (право-право)

Третий вид ротации – это право-право вращение (RR). Это вращение происходит, когда новый узел включен правое поддерево правого поддерева неуравновешенного узла. Например, это произойдет, если мы вставим число 11 в следующее дерево.

   / 
  4 
 / \ 
3   6 
    / \ 
   5   9 
         \ 11 (*)

РЛ (право-лево)

Последний вид вращения – это право-левое вращение (RL). Вращение, которое происходит, когда новый узел лежит на правое поддерево левого поддерева узла, который стал несбалансированным.

После вставки числа 4 в следующее дерево мы должны выполнить поворот RL, чтобы восстановить его баланс.

    / 
   2 
  / \ 
 1   6 
    / \ 
   5   9 
  /
4 (*)

Интерфейс для деревьев AVL

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

Методы


Публичные методы AVL Tree.

Детали реализации

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

Давайте начнем с рассмотрения того, как узлы представлены в дереве AVL.


Атрибуты узла AVL.

*Примечание: чтобы коду было легко следовать, я не буду использовать бинарное дерево, которое мы построили в предыдущем посте. Я сделал прототип, используя этот код, и результат не был идеальным; В деревьях AVL много логики, которая в сочетании с B-деревьями показалась мне немного неуклюжей. Поэтому я думаю, что на этот раз будет лучше, если мы начнем с нуля.

Вставлять

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

Сложность этого метода составляет O(log2 n).

def insert key, data = nil
  @root = insert_and_balance(@root, key, data)
end

Вставка и баланс

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

Сложность этого метода составляет O(log2 n).

def insert_and_balance node, key, data = nil
  return Node.new key, data unless node

  if (key < node.key)
    node.left = insert_and_balance(node.left, key, data)
  elsif(key > node.key)
    node.right = insert_and_balance(node.right, key, data)
  else
    node.data = data
    node.deleted = false
  end

  balance(node)
end

Остаток средств

Этот метод уравновешивает поддерево с корнем в указанном узле. Этот метод, вероятно, самый сложный в этой структуре данных, потому что он отвечает за выбор правильного типа поворота на основе «тяжелости» дерева.

Дерево считается левосторонним, если его коэффициент баланса больше 1, или правосторонним, если он ниже -1.

Лучший способ следовать этому методу — просмотреть ASCII-представления каждого варианта использования в предыдущих разделах.

Сложность этого метода составляет O(log2 n).

def balance node
  set_height node
  if (height(node.left) - height(node.right) == 2)
    if (height(node.left.right) > height(node.left.left))
      return rotate_left_right(node)
    end
    return rotate_right(node)
  elsif (height(node.right) - height(node.left) == 2)
    if (height(node.right.left) > height(node.right.right))
      return rotate_right_left(node)
    end
    return rotate_left(node)
  end
  return node
end

Удалять

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

Этот метод называется «ленивым» удалением, потому что он малоэффективен.

Сложность этого метода составляет O(log2 n).

def remove key
  search(key)&.deleted = true
end

Этот метод запускает рекурсивный поиск потомков сверху вниз от корневого узла текущего дерева.

Сложность этого метода составляет O(log2 n).

def search key
  node = search_rec @root, key
  return node unless node&.deleted
end

Поиск записи

Ищет ключ в поддереве, которое начинается с указанного узла. Этот метод начинает поиск в заданном узле и спускается (рекурсивно), перемещаясь влево или вправо в зависимости от значений ключа, пока не найдет ключ или не дойдет до конца поддерева.

Сложность этого метода составляет O(log2 n).

def search_rec node, key
  return nil unless node
  return search_rec(node.left, key) if (key < node.key)
  return search_rec(node.right, key) if (key > node.key)
  return node
end

Установить высоту

Этот метод вычисляет и устанавливает высоту для указанного узла на основе высоты их левого и правого поддеревьев.

Сложность этого метода составляет O(1).

def set_height node
  lh = height node&.left
  rh = height node&.right
  max = lh > rh ? lh : rh
  node.height = 1 + max
end

Повернуть вправо

Этот метод выполняет правое вращение.

Сложность этого метода составляет O(1).

def rotate_right p
  q = p.left
  p.left = q.right
  q.right = p
  set_height p
  set_height q
  return q
end

Поверните влево

Этот метод выполняет левое вращение.

Сложность этого метода составляет O(1).

def rotate_left p
  q = p.right
  p.right = q.left
  q.left = p
  set_height p
  set_height q
  return q
end

Повернуть влево вправо

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

Сложность этого метода составляет O(1).

def rotate_left_right node
  node.left = rotate_left(node.left)
  return rotate_right(node)
end

Повернуть вправо влево

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

Сложность этого метода составляет O(1).

def rotate_right_left node
  node.right = rotate_right(node.right)
  return rotate_left(node)
end

Распечатать

Этот метод печатает содержимое дерева.

Так как он должен посетить все узлы дерева, сложность этого метода O (n).

def print
  print_rec @root, 0
end

def print_rec node, indent
  unless node puts "x".rjust(indent * 4, " ")
  return
end

puts_key node, indent
  print_rec node.left, indent + 1
  print_rec node.right, indent + 1
end

def puts_key node, indent
  txt = node.key.to_s
  if node.deleted txt += " (D)"
    puts txt.rjust(indent * 8, " ")
  else
    puts txt.rjust(indent * 4, " ")
  end
end

Когда использовать бинарные деревья поиска

Двоичные деревья поиска хорошо работают, когда нам приходится обрабатывать большие наборы данных в приложениях, где отношение чтения/записи составляет 10 > 1 или более. Если объем данных невелик или соотношение чтения/записи равномерно, лучше использовать хеш-таблицы или даже связанные списки.

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

Это был довольно длинный пост, надеюсь, вам понравится!

Вы можете получить исходный код отсюда.

В следующий раз, Графики. Следите за обновлениями.
Спасибо за чтение! Увидимся в следующий раз.

PS: Если вы являетесь участником программы Kindle Unlimited, вы можете прочитать немного отполированную версию этой серии_ бесплатно на вашем устройстве Kindle.


Структуры данных с нуля — Ruby Edition.

Похожие записи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *