Как преобразовать двоичное дерево в двоичное дерево поиска на месте, то есть мы не можем использовать лишний пробел

Question

Как преобразовать двоичное дерево в двоичное дерево поиска на месте, то есть мы не можем использовать дополнительное пространство

Answer 1

Преобразовать двоичное дерево в двусвязный список - можно сделать на месте в O (n)
Затем отсортируйте его с помощью сортировки слиянием, nlogn
Преобразовать список обратно в дерево - O (n)

Простое решение nlogn.

Answer 2

Вы не даете много, чтобы продолжить, но если требование такое, как я думаю, у вас есть двоичное дерево, уже созданное и хранящееся в памяти, но не отсортированное (так, как вы хотите, чтобы оно было отсортировано, в любом случае). ).

Я предполагаю, что узлы дерева выглядят как

struct tree_node {
    struct tree_node * left;
    struct tree_node * right;
    data_t data;
};

Я также предполагаю, что вы можете прочитать C

Хотя мы могли бы просто сидеть и задаться вопросом, почему это дерево когда-либо было создано, если оно не было создано в отсортированном порядке, которое не приносит нам никакой пользы, поэтому я проигнорирую его и просто займусь сортировкой.

Требование, чтобы не использовалось дополнительное пространство, является странным. Временно будет дополнительное место, если только в стеке. Я собираюсь предположить, что это означает, что вызов malloc или что-то в этом роде, а также что результирующее дерево должно использовать не больше памяти, чем исходное несортированное дерево.

Первое и самое простое решение - выполнить предварительный обход несортированного дерева, удалив каждый узел из этого дерева и выполнив сортированную вставку в новое дерево. Это O (n + n log (n)), то есть O (n log (n)).

Если это не то, что они хотят, и вам придется использовать повороты и прочее ..... это ужасно!

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

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

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

Приступить к расчетам времени выполнения для второго предложения довольно сложно. Сначала я подумал, что это будет просто O (n ^ 2), как пузыри и шейкеры, но я не могу убедить себя в том, что обход обхода поддерева может не выиграть достаточно, чтобы сделать его немного лучше, чем O (n ^ 2). По существу, сорта типа пузырьки и шейкеры тоже получают эту оптимизацию, но только на концах, где полная сортировка происходит рано, и вы можете сократить пределы. С этой версией дерева у вас есть возможность избежать кусков в середине набора. Ну, как я уже сказал, это, вероятно, смертельно опасно.

Answer 3

Выполните обход PostOrder и из этого создайте двоичное дерево поиска.

struct Node * newroot = '\0';

struct Node* PostOrder(Struct Node* root)
{
      if(root != '\0')
      {
          PostOrder(root->left);
          PostOrder(root->right);
          insertBST(root, &newroot);
      }
}

insertBST(struct Node* node, struct Node** root)
{
   struct Node * temp, *temp1;
   if( root == '\0')
   {
      *root == node;
       node->left ==  '\0';
       node->right == '\0';
   }
   else
   {
       temp = *root;
       while( temp != '\0')
       {
           temp1= temp;
           if( temp->data > node->data)
               temp = temp->left;
           else
               temp = temp->right;
       }
       if(temp1->data > node->data)
       {
           temp1->left = node;
       }
       else
       {
           temp1->right = node;
       }
       node->left = node->right = '\0';
    }
}

Answer 4

Выполните следующий алгоритм для достижения решения.

1) найти преемника по порядку без пробелов.

Node InOrderSuccessor(Node node)
{ 
    if (node.right() != null) 
    { 
        node = node.right() 
        while (node.left() != null)  
            node = node.left() 
        return node 
    }
    else
    { 
        parent = node.getParent(); 
        while (parent != null && parent.right() == node)
       { 
            node = parent 
            parent = node.getParent() 
        } 
        return parent 
    } 
} 

2) Выполнять в порядке обхода, не используя пробел.

а) Найдите первый узел обхода по порядку. Он должен оставить большинство потомков дерева, если оно имеет, или слева от первого правого потомка, если он есть, или самого правого потомка. б) Используйте приведенный выше алгоритм для определения преемника inoder первого узла. c) Повторите шаг 2 для всех возвращенных наследников.

Используйте вышеупомянутый алгоритм 2 и выполните обход по порядку на двоичном дереве, не используя дополнительное пространство. Формируйте бинарное дерево поиска при выполнении обхода. Но сложность O(N2) наихудший случай.

Answer 5

struct Node
{
    int value;
    Node* left;
    Node* right;
};

void swap(int& l, int& r)
{
    int t = l;
    l = r;
    r = t;
}

void ConvertToBST(Node* n, Node** max)
{
    if (!n) return;

    // leaf node
    if (!n->left && !n->right)
    {
        *max = n;
        return;
    }

    Node *lmax = NULL, *rmax = NULL;
    ConvertToBST(n->left, &lmax);
    ConvertToBST(n->right, &rmax);

    bool swapped = false;
    if (lmax && n->value < lmax->value)
    {
        swap(n->value, lmax->value);
        swapped = true;
    }

    if (rmax && n->value > rmax->value)
    {
        swap(n->value, n->right->value);
        swapped = true;
    }

    *max = n;
    if (rmax && rmax->value > n->value) *max = rmax;

    // If either the left subtree or the right subtree has changed, convert the tree to BST again
    if (swapped) ConvertToBST(n, max);
}

Answer 6

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;

struct tree_node {
    struct tree_node * left;
    struct tree_node * right;
    data_t data;
};

        /* a bonsai-tree for testing */
struct tree_node nodes[10] =
{{ nodes+1, nodes+2, 1}
,{ nodes+3, nodes+4, 2}
,{ nodes+5, nodes+6, 3}
,{ nodes+7, nodes+8, 4}
,{ nodes+9, NULL, 5}
,{ NULL, NULL, 6}
,{ NULL, NULL, 7}
,{ NULL, NULL, 8}
,{ NULL, NULL, 9}
        };

struct tree_node * harvest(struct tree_node **hnd)
{
struct tree_node *ret;

while (ret = *hnd) {
        if (!ret->left && !ret->right) {
                *hnd = NULL;
                return ret;
                }
        if (!ret->left ) {
                *hnd = ret->right;
                ret->right = NULL;;
                return ret;
                }
        if (!ret->right) {
                *hnd = ret->left;
                ret->left = NULL;;
                return ret;
                }
        hnd = (rand() &1) ? &ret->left : &ret->right;
        }

return NULL;
}

void insert(struct tree_node **hnd, struct tree_node *this)
{
struct tree_node *ret;

while ((ret= *hnd)) {
        hnd = (this->data  < ret->data ) ? &ret->left : &ret->right;
        }
*hnd = this;
}

void show(struct tree_node *ptr, int indent)
{
if (!ptr) { printf("Null\n"); return; }

printf("Node(%d):\n", ptr->data);
printf("%*c=", indent, 'L');  show (ptr->left, indent+2);
printf("%*c=", indent, 'R');  show (ptr->right, indent+2);
}

int main(void)
{
struct tree_node *root, *this, *new=NULL;

for (root = &nodes[0]; this = harvest (&root);  ) {
        insert (&new, this);
        }

show (new, 0);
return 0;
}

Answer 7

куча сортировки по дереву .. сложность nlogn ..

Answer 8

Выполнить обход порядка двоичного дерева и сохранить результат. отсортировать результат в порядке убывания сформируйте двоичное дерево поиска, взяв средний элемент отсортированного списка за корень (это можно сделать с помощью бинарного поиска). таким образом, мы получаем сбалансированное двоичное дерево поиска.

Answer 9

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

Это ужасный алгоритм в целом - время выполнения O (n ^ 2) с наихудшим из возможных выходных данных двоичного дерева, но это хорошая отправная точка перед тем, как придумать что-то лучшее, и вы можете написать код для этого в около 20 строк на доске.

Answer 10

Бинарное дерево обычно является бинарным деревом поиска, в этом случае преобразование не требуется.

Возможно, вам необходимо уточнить структуру того, из чего вы конвертируете. Ваше исходное дерево не сбалансировано? Разве это не заказано ключом, по которому вы хотите искать? Как вы пришли к исходному дереву?