Найти замененные узлы в BST

Question

Я пытаюсь написать программу, которая может обнаружить и распечатать два узла в BST, которые были поменяны местами.

В трехуровневом дереве я приблизился к решению, используя этот подход.

If (!AllSubTreeAreValid())
{
//Nodes swapped on same side of main root node
}
else
{
  int max = getMax(root->left);
  int min = getMin(root->right);
  if(max > root->data || min < root->data )
  {
     //Nodes swapped on different sides of main root node
     //Print max and min values

  }
else 
{
 //No node swappped
}
}

//Helper functions
int GetMaxEle(TreeNode* tree)
{
    while(tree->right!=NULL)
    {
        tree=tree->right;
    }
    return tree->info;
}

int GetMinEle(TreeNode* tree)
{
    while(tree->left!=NULL)
    {
        tree=tree->left;
    }
    return tree->info;
}

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

             20

      15            30

   10    17       25     33

9  16  12  18  22  26  31  34

Находясь в правом поддереве корневого узла 15, значение 12 еще больше (нарушение).

Находясь в левом поддереве корневого узла 15, 16 еще больше (нарушение).

Итак, 16, 12 - это замененные элементы в приведенном выше BST. Как мне найти их через программу?

Answer 1

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

Давайте сначала посмотрим, как это сделать для простого отсортированного массива, а затем будем использоватьнаш алгоритм построения чего-то, что работает на деревьях.Интуитивно понятно, что если мы начнем с отсортированного массива, а затем поменяем местами два (не равных!) Элемента, то получится, что некоторое количество элементов в массиве будет неуместным.Например, учитывая массив

1 2 3 4 5

Если мы поменяем местами 2 и 4, мы получим этот массив:

1 4 3 2 5

Как бы мы обнаружили, что 2 и 4 поменялись местами здесь?Ну, так как 4 является наибольшим из двух элементов и был поменялся местами, он должен быть больше, чем оба элемента вокруг него.Точно так же, поскольку 2 поменялся местами, он должен быть меньше, чем оба элемента вокруг него.Отсюда можно сделать вывод, что 2 и 4 поменялись местами.

Однако это не всегда работает правильно.Например, предположим, что мы меняем 1 и 4:

4 2 3 1 5

Здесь 2 и 1 меньше, чем их соседние элементы, а 4 и 3 больше, чем их.Из этого мы можем сказать, что два из этих четырех так или иначе были обменены, но не ясно, какие из них мы должны поменяться местами.Однако, если мы возьмем самое большое и самое маленькое из этих значений (1 и 4 соответственно), мы получим пару, которая была поменяна местами.

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

• Наибольший локальный максимум в массиве.
• Наименьший локальный минимум в массиве.

Эти два элемента отсутствуютместа и должны быть поменяны местами.

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

              20
         /         \
      15             30
     /   \         /   \ 
   10    17      25     33
  / |   /  \    /  \    |  \
9  16  12  18  22  26  31  34

Если мы линеаризуем это в массив, мы получим

9 10 16 15 12 17 18 20 22 25 26 30 31 33 34

Обратите внимание, что 16 больше, чем окружающие его элементы, и что 12 меньшечем его.Это немедленно говорит нам о том, что 12 и 16 поменялись местами.

Следовательно, простым алгоритмом для решения этой проблемы было бы выполнить обход дерева по порядку, чтобы линеаризовать его в последовательность, такую ​​как vector или deque, затем сканировать эту последовательность, чтобы найти наибольший локальный максимум и наименьший локальный минимум.Это будет выполняться за время O (n), используя пространство O (n).Более хитрым, но более экономичным по площади алгоритмом было бы отслеживать только три узла одновременно - текущий узел, его предшественника и его преемника - что уменьшает использование памяти до O (1).

Надеюсьэто помогает!

Answer 2

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

int GetMax(TreeNode* tree) {
    int max_right, max_left, ret;

    ret = tree->data;
    if (tree->left != NULL) {
        max_left = GetMax(tree->left);
        if (max_left > ret)
            ret = max_left;
    }
    if (tree->right != NULL) {
        max_right = GetMax(tree->right);
        if (max_right > ret)
            ret = max_right;
    }

    return ret;
}

int GetMin(TreeNode* tree) {
    int min_right, min_left, ret;

    ret = tree->data;
    if (tree->left != NULL) {
        min_left = GetMin(tree->left);
        if (min_left < ret)
            ret = min_left;
    }
    if (tree->right != NULL) {
        min_right = GetMin(tree->right);
        if (min_right < ret)
            ret = min_right;
    }

    return ret;
}

void print_violations(TreeNode* tree) {
    if ((tree->left != NULL) && (tree->right != NULL)) {
        int max_left = GetMax(tree->left);
        int min_right = GetMin(tree->right);
        if (max_left > tree->data && min_right < tree->data) {
            printf("Need to swap %d with %d\n", max_left, min_right);
        }
    }
    if (tree->left != NULL)
        print_violations(tree->left);
    if (tree->right != NULL)
        print_violations(tree->right);
}

Это медленнее, но оно печатает все поменянные им свопы.Может быть изменен для печати всех нарушений (например, если (max_left> tree-> data) печатать нарушение).Вы можете улучшить производительность, если добавите два поля в TreeNode, предварительно рассчитав max и min для этого поддерева.

Answer 3

Полагаю, ваш getMin et getMax работает с гипотезами о том, что дерево является BST, поэтому

T getMax(tree) {
  return tree -> right == null 
    ? tree -> value 
    : getMax(tree -> right);
}

(или эквивалентный код с циклом).Если это так, ваш код проверяет не более трех значений в дереве.Даже если getMax и getMin обойдут полное дерево, чтобы получить фактический максимум / мин, вы все равно будете основывать свой тест только на двух сравнениях.Если вы хотите проверить, что ваше дерево удовлетворяет свойству BST, очевидно, что вам нужно проверить все значения.Достаточно сравнить каждый узел с его родителем.

void CheckIsBst(Tree *tree) {
  if (tree -> left != null) {
    if (tree -> left -> value > tree -> value) {
      // print violation
    }
    CheckIsBst(tree -> left);   
  }
  // same with -> right, reversing < to > in the test
}

Редактировать : это было неправильно, см. Комментарий.Я считаю, что это нормально.

void checkIsBst(Tree *Tree, Tree *lowerBound, Tree *upperBound) {
  if(lowerBound!= null && lowerBound -> value > tree -> Value) {
    //violation
  }
  // same for upper bound, check with <
  if (tree -> left != null) {
    if (tree -> left -> value > tree -> value) {
      // print violation
     }
     CheckIsBst(tree -> left, lowerBound, tree);   
  }
  // same for right, reversing comparison 
  // setting lowerBound to tree instead of upperBound
}

Вызов из корня с нулевыми границами