Рубрики

Минимальный своп, необходимый для преобразования двоичного дерева в двоичное дерево поиска

Деревья, Сортировка

Учитывая представление массива Complete Binary Tree, т. Е. Если индекс i является родителем, индекс 2 * i + 1 является левым дочерним элементом, а индекс 2 * i + 2 является правым дочерним. Задача состоит в том, чтобы найти минимальное количество подкачки, необходимое для преобразования его в дерево двоичного поиска.

Примеры:

Input : arr[] = { 5, 6, 7, 8, 9, 10, 11 }
Output : 3
Binary tree of the given array:

Swap 1: Swap node 8 with node 5.
Swap 2: Swap node 9 with node 10.
Swap 3: Swap node 10 with node 7.

So, minimum 3 swaps are required.


Input : arr[] = { 1, 2, 3 }
Output : 1
Binary tree of the given array:

After swapping node 1 with node 2.

So, only 1 swap required.

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

Минимальное количество свопов, необходимое для сортировки массива

Сложность времени: O (n log n).

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

using namespace std;

  
// Обход бинарного дерева

void inorder(int a[], std::vector<int> &v, 

                        int n, int index)

{

    // если индекс больше или равен размеру вектора

    if(index >= n)

        return;

    inorder(a, v, n, 2 * index + 1);

      

    // вставляем элементы в вектор

    v.push_back(a[index]);

    inorder(a, v, n, 2 * index + 2);

}

  
// Функция поиска минимальных свопов для сортировки массива

int minSwaps(std::vector<int> &v)

{

    std::vector<pair<int,int> > t(v.size());

    int ans = 0;

    for(int i = 0; i < v.size(); i++)

        t[i].first = v[i], t[i].second = i;

      

    sort(t.begin(), t.end());

    for(int i = 0; i < t.size(); i++)

    {

        // второй элемент равен i

        if(i == t[i].second)

            continue;

        else

        {

            // обмен элементов

            swap(t[i].first, t[t[i].second].first);

            swap(t[i].second, t[t[i].second].second);

        }

          

        // Второе не равно i

        if(i != t[i].second)

            --i;

        ans++;

    }

    return ans;

}

  
// Код драйвера

int main()

{

    int a[] = { 5, 6, 7, 8, 9, 10, 11 };

    int n = sizeof(a) / sizeof(a[0]);

    std::vector<int> v;

    inorder(a, v, n, 0);

    cout << minSwaps(v) << endl;

}

  
// Этот код предоставлен code_freak

Выход:

3

Упражнение: Можем ли мы распространить это на обычное двоичное дерево, т. Е. На двоичное дерево, представленное с помощью левого и правого указателей и необязательно завершенное?

Эта статья предоставлена Anuj Chauhan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Минимальный своп, необходимый для преобразования двоичного дерева в двоичное дерево поиска

0.00 (0%) 0 votes