Iron Core. Часть 3: Бессмертная командная строка

Публикуем перевод третьей статьи из серии (первая часть, вторая), посвящённой информационным технологиям в авиаперевозках. Сегодня поговорим о режиме командной строки системы Amadeus, работа в которой опирается на язык, созданный для телетайпов. Этот язык до сих пор обеспечивает огромный процент бронирований билетов во всём мире — как тех, что выполняются различными агентствами, так и тех, что делаются посредством GDS.

https://habr.com/ru/companies/wunderfund/articles/1046431/

Алгоритмы и Структуры данных

Вращение в AVL-деревьях

Двойные повороты - достаточно сложная тема, но я нашел достаточно хорошее объяснение этому. Обратите ваше внимание на картинку. В данном случае представлено вращение влево-вправо.

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

Есть аналогичное вращение вправо-влево, только оно с точностью наоборот. Сначала вращение вправо, а после уже влево!

Data Science: Алгоритмы и Структуры данных

Возвращаем прямой формат контента по тематике канала. Полностью пересмотрели подход к постам.

Надеемся, что вам будет полезно.

Задача: переместить нули в конец

Дан массив случайных чисел, необходимо переместить все нули данного массива в конец. Например, если задан массив 1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, необходимо его изменить к виду: 1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0.

Порядок остальных элементов должен остаться прежним. Сложность O(n), а пространство О(1)

Data Science: Алгоритмы и Структуры данных

Алгоритм решения задачи

Есть куча способов решить данную задачу. Ниже я приведу простой и интересный способ решить ее.

Пройдитесь по заданному массиву слева направо. Во время обхода поддерживайте количество ненулевых элементов в массиве (к примеру в счетчике count). Для каждого ненулевого элемента gjvtcnbnt элемент в arrcount и увеличьте сам count.

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

Data Science: Алгоритмы и Структуры данных

Решение задачи через один только проход

Да, эту задачу можно решить также и тупо одним проходом, нам снова понадобиться count(счетчик). Только теперь, кроме него нам нужна дополнительная функция swap(которая меняет местами элементы)

Итого у нас будет изначально count = 0 и цикл от начала до конца нашего массива. Мы будем проверять, если наш текущий элемент не равен 0, мы будем менять местами count элемент и элемент на текущей i-ой позиции:

for i in range(0, n):
if (arr[i] != 0):
   arr[count], arr[i] = arr[i], arr[count]
    count+=1

Data Science: Алгоритмы и Структуры данных

Двоичное дерево поиска

Двоичное дерево поиска(BST) - дерево, в котором все узлы следуют свойствам:

1. Левое поддерево узла имеет ключ, меньше или равный ключу его родительского узла

2. Правое поддерево узла имеет ключ больше, чем ключ родительского узла.

Таким образом дерево делит все свои поддеревью на два сегмента: левое и правое поддеревья. Есть еще одно определение данного дерева:

leftsubtree(keys) =< node(key) =< rightsubtree(keys)

Data Science: Алгоритмы и Структуры данных