Рубрики

Два узла BST поменялись местами, исправьте BST

Два узла дерева двоичного поиска (BST) меняются местами. Исправить (или исправить) BST.

Input Tree:
         10
        /  \
       5    8
      / \
     2   20

In the above tree, nodes 20 and 8 must be swapped to fix the tree.  
Following is the output tree
         10
        /  \
       5    20
      / \
     2   8

Обход по порядку следования BST создает отсортированный массив. Таким образом, простой метод заключается в сохранении обхода входного дерева во вспомогательном массиве. Сортировать вспомогательный массив. Наконец, вставьте элементы вспомогательного массива обратно в BST, сохраняя структуру BST такой же. Временная сложность этого метода составляет O (nLogn), а необходимое вспомогательное пространство — O (n).

Мы можем решить это за O (n) время и с помощью одного обхода данного BST . Поскольку обход по порядку следования BST всегда является отсортированным массивом, проблема может быть сведена к проблеме, когда два элемента отсортированного массива меняются местами. Есть два случая, которые нам нужно рассмотреть:

1. Поменяемые местами узлы не являются соседними в обходе порядка BST.

 For example, Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}. 
 The inorder traversal of the given tree is 3 25 7 8 10 15 20 5 

Если мы внимательно наблюдаем, во время обхода внутреннего порядка мы находим, что узел 7 меньше предыдущего посещенного узла 25. Здесь сохраняем контекст узла 25 (предыдущий узел). Опять же, мы находим, что узел 5 меньше предыдущего узла 20. На этот раз мы сохраняем контекст узла 5 (текущий узел). Наконец поменяйте местами значения двух узлов.

2. Переставленные узлы смежны в обходе порядка BST.

  For example, Nodes 7 and 8 are swapped in {3 5 7 8 10 15 20 25}. 
  The inorder traversal of the given tree is 3 5 8 7 10 15 20 25 

В отличие от случая # 1, здесь существует только одна точка, где значение узла меньше, чем предыдущее значение узла. например, узел 7 меньше, чем узел 8.

Как решить? Мы будем поддерживать три указателя, первый, средний и последний. Когда мы находим первую точку, где текущее значение узла меньше, чем предыдущее значение узла, мы обновляем первую с предыдущим узлом, а середину — текущим узлом. Когда мы находим вторую точку, где текущее значение узла меньше, чем предыдущее значение узла, мы обновляем последний с текущим узлом. В случае № 2 мы никогда не найдем второй пункт. Таким образом, последний указатель не будет обновлен. После обработки, если значение последнего узла равно нулю, два переставленных узла BST являются смежными .

Ниже приведена реализация данного кода.

C ++

// Два узла в BST поменялись местами, исправим BST.
#include <stdio.h>
#include <stdlib.h>

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node *left, *right;

};

  
// Утилита для замены двух целых чисел

void swap( int* a, int* b )

{

    int t = *a;

    *a = *b;

    *b = t;

}

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

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

struct node* newNode(int data)

{

    struct node* node = (struct node *)malloc(sizeof(struct node));

    node->data = data;

    node->left = NULL;

    node->right = NULL;

    return(node);

}

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

void correctBSTUtil( struct node* root, struct node** first,

                     struct node** middle, struct node** last,

                     struct node** prev )

{

    if( root )

    {

        // Повтор для левого поддерева

        correctBSTUtil( root->left, first, middle, last, prev );

  

        // Если этот узел меньше предыдущего, он нарушает

        // правило BST.

        if (*prev && root->data < (*prev)->data)

        {

            // Если это первое нарушение, пометьте эти два узла как

            // 'first' и 'middle'

            if ( !*first )

            {

                *first = *prev;

                *middle = root;

            }

  

            // Если это второе нарушение, пометить этот узел как последний

            else

                *last = root;

        }

  

        // Пометить этот узел как предыдущий

        *prev = root;

  

        // Повтор для правильного поддерева

        correctBSTUtil( root->right, first, middle, last, prev );

    }

}

  
// Функция для исправления данного BST, где два узла поменялись местами. Эта
// функция использует correctBSTUtil (), чтобы найти два узла и поменять местами
// узлы для исправления BST

void correctBST( struct node* root )

{

    // Инициализировать указатели, необходимые для correctBSTUtil ()

    struct node *first, *middle, *last, *prev;

    first = middle = last = prev = NULL;

  

    // Устанавливаем Пуатье, чтобы найти два узла

    correctBSTUtil( root, &first, &middle, &last, &prev );

  

    // Исправить (или исправить) дерево

    if( first && last )

        swap( &(first->data), &(last->data) );

    else if( first && middle ) // Смежные узлы поменялись местами

        swap( &(first->data), &(middle->data) );

  

    // иначе узлы не были поменяны местами, переданное дерево действительно BST.

}

  
/ * Утилита для печати обхода Inoder * /

void printInorder(struct node* node)

{

    if (node == NULL)

        return;

    printInorder(node->left);

    printf("%d ", node->data);

    printInorder(node->right);

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    / * 6

        / /

       10 2

      / / / /

     1 3 7 12

     10 и 2 поменялись местами

    * /

  

    struct node *root = newNode(6);

    root->left        = newNode(10);

    root->right       = newNode(2);

    root->left->left  = newNode(1);

    root->left->right = newNode(3);

    root->right->right = newNode(12);

    root->right->left = newNode(7);

  

    printf("Inorder Traversal of the original tree \n");

    printInorder(root);

  

    correctBST(root);

  

    printf("\nInorder Traversal of the fixed tree \n");

    printInorder(root);

  

    return 0;

}

Джава

// Java-программа для исправления BST
// если два узла поменялись местами

import java.util.*;

import java.lang.*;

import java.io.*;

  

class Node {

  

    int data;

    Node left, right;

  

    Node(int d) {

        data = d;

        left = right = null;

    }

}

  

class BinaryTree

{

    Node first, middle, last, prev;

      

    // Эта функция выполняет обход порядка

    // чтобы найти два переставленных узла.

    // Он устанавливает три указателя, первый, средний

    // и последний Если переставленные узлы

    // рядом друг с другом, затем сначала

    // и середина содержат результирующие узлы

    // Остальное, первый и последний содержат

    // результирующие узлы

    void correctBSTUtil( Node root)

    {

        if( root != null )

        {

            // Повтор для левого поддерева

            correctBSTUtil( root.left);

  

            // Если этот узел меньше чем

            // предыдущий узел, это

            // нарушаем правило BST.

            if (prev != null && root.data <

                                prev.data)

            {

                // Если это первое нарушение,

                // пометить эти два узла как

                // 'first' и 'middle'

                if (first == null)

                {

                    first = prev;

                    middle = root;

                }

  

                // Если это второе нарушение,

                // пометить этот узел как последний

                else

                    last = root;

            }

  

            // Пометить этот узел как предыдущий

            prev = root;

  

            // Повтор для правильного поддерева

            correctBSTUtil( root.right);

        }

    }

  

    // Функция для исправления данного BST где

    // два узла поменялись местами. Эта функция

    // использует correctBSTUtil (), чтобы узнать

    // два узла и меняются местами

    // исправить BST

    void correctBST( Node root )

    {

        // Инициализировать указатели, необходимые

        // для правильного BSTUtil ()

        first = middle = last = prev = null;

  

        // Установить пуанты, чтобы узнать

        // два узла

        correctBSTUtil( root );

  

        // Исправить (или исправить) дерево

        if( first != null && last != null )

        {

            int temp = first.data;

            first.data = last.data;

            last.data = temp; 

        }

        // Смежные узлы поменялись местами

        else if( first != null && middle !=

                                    null

        {

            int temp = first.data;

            first.data = middle.data;

            middle.data = temp;

        }

  

        // иначе узлы не были поменяны местами,

        // переданное дерево действительно BST.

    }

  

    / * Утилита для печати

     Обход Inoder * /

    void printInorder(Node node)

    {

        if (node == null)

            return;

        printInorder(node.left);

        System.out.print(" " + node.data);

        printInorder(node.right);

    }

  

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main (String[] args) 

    {

        / * 6

            / /

           10 2

          / / / /

         1 3 7 12

          

        10 и 2 поменялись местами

        * /

  

        Node root = new Node(6);

        root.left = new Node(10);

        root.right = new Node(2);

        root.left.left = new Node(1);

        root.left.right = new Node(3);

        root.right.right = new Node(12);

        root.right.left = new Node(7);

  

        System.out.println("Inorder Traversal"+

                        " of the original tree");

        BinaryTree tree = new BinaryTree();

        tree.printInorder(root);

  

        tree.correctBST(root);

  

        System.out.println("\nInorder Traversal"+

                          " of the fixed tree");

        tree.printInorder(root);

    }

}
// Этот код предоставлен Чхави


Выход:

Inorder Traversal of the original tree
1 10 3 6 7 2 12
Inorder Traversal of the fixed tree
1 2 3 6 7 10 12

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

Посмотрите это для различных тестовых примеров приведенного выше кода.

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

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

Два узла BST поменялись местами, исправьте BST

0.00 (0%) 0 votes