Рубрики

Граф инверсий в массиве | Набор 2 (с использованием самобалансирующегося BST)

Число инверсий для массива указывает — насколько далеко (или близко) массив от сортировки. Если массив уже отсортирован, то счетчик инверсий равен 0. Если массив отсортирован в обратном порядке, то счетчик инверсий является максимальным.

    Two elements a[i] and a[j] form an inversion if 
     a[i] > a[j] and i < j. For simplicity, we may 
     assume that all elements are unique.

     Example:
     Input:  arr[] = {8, 4, 2, 1}
     Output: 6
     Given array has six inversions (8,4), (4,2),
     (8,2), (8,1), (4,1), (2,1).     

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

Сложность по времени в наивном подходе равна O (n 2 ), а в подходе, основанном на сортировке слиянием, — O (n Log n). В этом посте обсуждается еще один подход O (n Log n). Идея состоит в том, чтобы использовать самобалансирующееся дерево двоичного поиска, такое как красно-черное дерево , дерево AVL и т. Д., И дополнять его, чтобы каждый узел также отслеживал количество узлов в правом поддереве.

1) Create an empty AVL Tree.  The tree is augmented here 
   such that every node also maintains size of subtree 
   rooted with this node.

2) Initialize inversion count or result as 0.

3) Iterate from 0 to n-1 and do following for every 
   element in arr[i]
     a) Insert arr[i] into the AVL Tree.  The insertion 
        operation also updates result.  The idea is to
        keep counting greater nodes when tree is traversed
        from root to a leaf for insertion.  

4) Return result. 

Более подробное описание шага 3.a:
1) Когда мы вставляем arr [i], элементы из arr [0] в arr [i-1] уже вставляются в дерево AVL. Все, что нам нужно сделать, это подсчитать эти узлы.
2) Для вставки в дерево AVL мы проходим дерево от корня до листа, сравнивая каждый узел с arr [i []. Когда arr [i [меньше текущего узла, мы увеличиваем количество инверсий на 1 плюс количество узлов в правом поддереве текущего узла. Который в основном подсчитывает большее количество элементов слева от arr [i], то есть инверсий.

Ниже приведена реализация вышеуказанной идеи.

C ++

// Программа C ++ на основе дерева AVL для подсчета инверсии в массиве
#include<bits/stdc++.h>

using namespace std;

  
// Узел дерева AVL

struct Node

{

    int key, height;

    struct Node *left, *right;

    int size; // размер дерева с этим узлом

};

  
// Вспомогательная функция для получения высоты дерева с корнем N

int height(struct Node *N)

{

    if (N == NULL)

        return 0;

    return N->height;

}

  
// Функция полезности для размера дерева с корнем с N

int size(struct Node *N)

{

    if (N == NULL)

        return 0;

    return N->size;

}

  
/ * Вспомогательная функция, которая выделяет новый узел с данным ключом и

    NULL левый и правый указатели. * /

struct Node* newNode(int key)

{

    struct Node* node = new Node;

    node->key   = key;

    node->left   = node->right  = NULL;

    node->height = node->size = 1;

    return(node);

}

  
// Полезная функция для правого поворота поддерева с корнем у

struct Node *rightRotate(struct Node *y)

{

    struct Node *x = y->left;

    struct Node *T2 = x->right;

  

    // Выполнить вращение

    x->right = y;

    y->left = T2;

  

    // Обновление высоты

    y->height = max(height(y->left), height(y->right))+1;

    x->height = max(height(x->left), height(x->right))+1;

  

    // Обновить размеры

    y->size = size(y->left) + size(y->right) + 1;

    x->size = size(x->left) + size(x->right) + 1;

  

    // Возвращаем новый корень

    return x;

}

  
// Вспомогательная функция левого поворота поддерева с корнем x

struct Node *leftRotate(struct Node *x)

{

    struct Node *y = x->right;

    struct Node *T2 = y->left;

  

    // Выполнить вращение

    y->left = x;

    x->right = T2;

  

    // Обновление высоты

    x->height = max(height(x->left), height(x->right))+1;

    y->height = max(height(y->left), height(y->right))+1;

  

    // Обновить размеры

    x->size = size(x->left) + size(x->right) + 1;

    y->size = size(y->left) + size(y->right) + 1;

  

    // Возвращаем новый корень

    return y;

}

  
// Получить коэффициент баланса узла N

int getBalance(struct Node *N)

{

    if (N == NULL)

        return 0;

    return height(N->left) - height(N->right);

}

  
// Вставляет новый ключ в дерево, сгнившее с узла. Также обновления
// * результат (счет инверсии)

struct Node* insert(struct Node* node, int key, int *result)

{

    / * 1. Выполнить обычное вращение BST * /

    if (node == NULL)

        return(newNode(key));

  

    if (key < node->key)

    {

        node->left  = insert(node->left, key, result);

  

        // ОБНОВЛЕНИЕ СЧЕТА ВЕЛИКИХ ЭЛЕМЕНТОВ ДЛЯ КЛЮЧЕВОГО

        *result = *result + size(node->right) + 1;

    }

    else

        node->right = insert(node->right, key, result);

  

    / * 2. Обновление высоты и размера этого узла-предка * /

    node->height = max(height(node->left),

                       height(node->right)) + 1;

    node->size = size(node->left) + size(node->right) + 1;

  

    / * 3. Получить коэффициент баланса этого узла-предка в

          проверить, не стал ли этот узел несбалансированным * /

    int balance = getBalance(node);

  

    // Если этот узел становится несбалансированным, то есть

    // 4 случая

  

    // Левый левый регистр

    if (balance > 1 && key < node->left->key)

        return rightRotate(node);

  

    // правый правый случай

    if (balance < -1 && key > node->right->key)

        return leftRotate(node);

  

    // левый правый регистр

    if (balance > 1 && key > node->left->key)

    {

        node->left =  leftRotate(node->left);

        return rightRotate(node);

    }

  

    // Правый левый регистр

    if (balance < -1 && key < node->right->key)

    {

        node->right = rightRotate(node->right);

        return leftRotate(node);

    }

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
// Следующая функция возвращает счетчик инверсий в arr []

int getInvCount(int arr[], int n)

{

  struct Node *root = NULL;  // Создать пустое дерево AVL

  

  int result = 0;   // Инициализировать результат

  

  // Начиная с первого элемента, вставляем все элементы по одному

  // один в дереве AVL.

  for (int i=0; i<n; i++)

  

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

     // операция обновляет результат путем добавления количества элементов

     // больше, чем arr [i] слева от arr [i]

     root = insert(root, arr[i], &result);

  

  return result;

}

  
// Программа драйвера для тестирования выше

int main()

{

    int arr[] = {8, 4, 2, 1};

    int n = sizeof(arr)/sizeof(int);

    cout << "Number of inversions count are : "

         << getInvCount(arr,n);

    return 0;

}

python3

# Программа Python на основе дерева AVL для
# считать инверсию в массиве

  
# Полезная функция для получения высоты
# дерево с корнем из N

def height(N):

    if N == None

        return 0

    return N.height

  
# Функция полезности для размера
# дерево с корнем из N

def size(N):

    if N == None

        return 0

    return N.size

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

class newNode:

    def __init__(self, key):

        self.key = key 

        self.left = self.right = None

        self.height = self.size = 1

  
# Функция полезности для вращения вправо
# поддерево с корнем у

def rightRotate(y):

    x = y.left 

    T2 = x.right 

  

    # Выполнить вращение

    x.right =

    y.left = T2 

  

    # Обновление высоты

    y.height = max(height(y.left), 

                   height(y.right)) + 1

    x.height = max(height(x.left), 

                   height(x.right)) + 1

  

    # Обновление размеров

    y.size = size(y.left) + size(y.right) + 1

    x.size = size(x.left) + size(x.right) + 1

  

    # Возврат нового рута

    return x

  
# Утилита для левого поворота
# поддерево с корнем из x

def leftRotate(x):

    y = x.right 

    T2 = y.left 

  

    # Выполнить вращение

    y.left =

    x.right = T2 

  

    # Обновление высоты

    x.height = max(height(x.left), 

                   height(x.right)) + 1

    y.height = max(height(y.left), 

                   height(y.right)) + 1

  

    # Обновление размеров

    x.size = size(x.left) + size(x.right) + 1

    y.size = size(y.left) + size(y.right) + 1

  

    # Возврат нового рута

    return y

  
# Получить коэффициент баланса узла N

def getBalance(N):

    if N == None:

        return 0

    return height(N.left) - height(N.right)

  
# Вставляет новый ключ в загнившее дерево
# с узлом Также обновляет * результат (количество инверсий)

def insert(node, key, result):

      

    # 1. Выполните нормальное вращение BST

    if node == None

        return newNode(key)

  

    if key < node.key:

        node.left = insert(node.left, key, result) 

  

        # ОБНОВЛЕНИЕ СЧЕТА ВЕЛИКИХ ЭЛЕМЕНТОВ ДЛЯ КЛЮЧЕЙ

        result[0] = result[0] + size(node.right) + 1

    else:

        node.right = insert(node.right, key, result) 

  

    # 2. Обновление высоты и размера этого узла-предка

    node.height = max(height(node.left),    

                      height(node.right)) + 1

    node.size = size(node.left) + size(node.right) + 1

  

    # 3. Получите фактор баланса этого предка

    # узел, чтобы проверить, стал ли этот узел

    # несбалансированный

    balance = getBalance(node) 

  

    # Если этот узел становится несбалансированным,

    # тогда есть 4 случая

  

    # Левый левый корпус

    if (balance > 1 and key < node.left.key): 

        return rightRotate(node) 

  

    # Right Right Case

    if (balance < -1 and key > node.right.key):

        return leftRotate(node) 

  

    # Левый Правый Корпус

    if balance > 1 and key > node.left.key:

        node.left = leftRotate(node.left) 

        return rightRotate(node)

  

    # Правый левый корпус

    if balance < -1 and key < node.right.key:

        node.right = rightRotate(node.right) 

        return leftRotate(node)

  

    # вернуть (неизмененный) указатель узла

    return node

  
# Следующая функция возвращает
# число инверсий в обр []

def getInvCount(arr, n):

    root = None # Создать пустое дерево AVL

  

    result = [0] # Инициализировать результат

  

    # Начиная с первого элемента, вставьте все

    # элементов по одному в дереве AVL.

    for i in range(n): 

  

        # Обратите внимание, что адрес результата передается

        # как результат обновления операции вставки

        # добавление количества элементов больше чем

        # arr [i] слева от arr [i]

        root = insert(root, arr[i], result) 

  

    return result[0]

  
Код водителя

if __name__ == '__main__':

    arr = [8, 4, 2, 1

    n = len(arr) 

    print("Number of inversions count are :",

                         getInvCount(arr, n))

  
# Этот код предоставлен PranchalK


Выход:

Number of inversions count are : 6

Временная сложность вышеупомянутого решения составляет O (n Log n), поскольку вставка AVL занимает O (Log n) время.

Подсчет инверсий с использованием Set в C ++ STL.

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

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

Рекомендуемые посты:

Граф инверсий в массиве | Набор 2 (с использованием самобалансирующегося BST)

0.00 (0%) 0 votes