Como converter um binário de árvore para árvore de busca binária no local, por exemplo, não podemos usar qualquer espaço extra

Question

Como converter um binário de árvore para árvore de busca binária no local, por exemplo, não podemos usar qualquer espaço extra.

Answer 1

Você não dá muito para continuar, mas se o requisito é o que eu acho que é, você já tem uma árvore binária criada e sentada na memória, mas não classificada (da maneira que você deseja que seja classificada, de qualquer maneira).

Estou assumindo que os nós da árvore parecem

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

Também estou assumindo que você pode ler C

Embora pudéssemos ficar sentados imaginando por que essa árvore foi criada sem ter sido criada em ordem classificada que não nos faz bem, então vou ignorá -la e apenas lidar com a classificação.

O requisito de que nenhum espaço extra seja usado é estranho. Temporariamente haverá espaço extra, mesmo que apenas na pilha. Vou assumir que isso significa que ligar para Malloc ou algo parecido e também que a árvore resultante não precisa usar mais memória do que a árvore não classificada original.

A primeira e mais fácil solução é fazer uma travessia de pré -encomenda da árvore não classificada, removendo cada nó daquela árvore e fazendo uma inserção classificada em uma nova árvore. Este é o (n+nlog (n)), que é O (nlog (n)).

Se não é isso que eles querem e você terá que usar rotações e outras coisas ..... isso é horrível!

Eu pensei que você poderia fazer isso fazendo uma versão estranha de um tipo de pilha, mas tive problemas. Outra coisa que veio à mente, que seria terrivelmente lenta, faria uma versão estranha do tipo de bolha na árvore.

Para isso, cada nó é comparado e possivelmente trocado por cada uma das crianças diretas (e, portanto, também com seus pais) repetidamente até que você atravessa a árvore e não encontre os swaps necessários. Fazer um tipo de agitador (tipo de bolha que vai para a esquerda para a direita e a direita para a esquerda), a versão disso funcionaria melhor e, após o passe inicial, você não precisaria atravessar as subárvores que não pareciam fora de ordem em relação aos pais .

Tenho certeza de que esse algorthm foi pensado por outra pessoa antes de mim e tem um nome legal que eu simplesmente não sei, ou que é fundamentalmente falho de alguma maneira que não estou vendo.

A criação dos cálculos em tempo de execução para a segunda sugestão é bastante complicada. No começo, eu pensei que seria simplesmente O (n^2), como tipos de bolhas e agitadores, mas não posso me satisfazer que a sugestão de travessia evasão pode não ganhar o suficiente para torná -lo um pouco melhor do que O (n^ 2). Essencialmente, os tipos de bolhas e agitadores também obtêm essa otimização, mas apenas nas extremidades onde a classificação total ocorre mais cedo e você pode reduzir os limites. Com esta versão em árvore, você obtém oportunidades para evitar pedaços no meio do conjunto também. Bem, como eu disse, provavelmente é fatalmente falho.

Answer 2

Converter a árvore binária em uma lista duplamente vinculada- pode ser feita no local em O (n)
Em seguida, classifique -o usando a mesclagem, nLogn
Converta a lista de volta para uma árvore - O (n)

Solução simples nLogn.

Answer 3

Faça a travessia da Postlering e, a partir disso, crie uma árvore de pesquisa binária.

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

Faça o seguinte algoritmo para alcançar a solução.

1) Encontre o sucessor em ordem sem usar nenhum espaço.

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) Faça em ordem Traversal sem usar o espaço.

a) Encontre o primeiro nó de travessia inorder. Deveria deixar a maioria das crianças da árvore, se tiver, ou à esquerda do primeiro filho direito, se tiver, ou a própria criança certa. b) Use acima do algoritmo para descobrir o sucessor inoder do primeiro nó. c) Repita a etapa 2 para todo o sucessor devolvido.

Use acima de 2 algoritmo e faça a travessia em ordem na árvore binária sem usar espaço extra. Forme a árvore de pesquisa binária ao fazer travessia. Mas a complexidade é O(N2) pior caso.

Answer 5

Bem, se essa é uma pergunta de entrevista, a primeira coisa que eu ficaria deixada escapar (com zero pensamento real) é o seguinte: iterar todo o binário recursivamente e encontrar o menor elemento. Tire -o da árvore binária. Agora, repita o processo em que você itera a árvore inteira e encontre o menor elemento e adicione -o como pai do último elemento encontrado (com o elemento anterior se tornando o filho esquerdo do novo nó). Repita quantas vezes for necessário até que a árvore original esteja vazia. No final, você fica com a pior árvore binária classificada - uma lista vinculada. Seu ponteiro está apontando para o nó raiz, que é o maior elemento.

Este é um algoritmo horrível - o (n^2), com a pior saída de árvore binária possível, mas é um ponto de partida decente antes de criar algo melhor e tem a vantagem de você ser capaz de escrever o código para Em cerca de 20 linhas em um quadro branco.

Answer 6

Uma árvore binária geralmente é Uma árvore de pesquisa binária, nesse caso, nenhuma conversão é necessária.

Talvez você precise esclarecer a estrutura do que está convertendo. Sua árvore de origem está desequilibrada? Não é ordenado pela chave em que você deseja pesquisar? Como você chegou à árvore de origem?

Answer 7

#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 8

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 9

Faça uma travessia de encomenda da árvore binária e guarde o resultado. Classifique o resultado na ordem de acidental, forma a árvore de pesquisa binária, pegando o elemento intermediário da lista classificada como root (isso pode ser feito usando a pesquisa binária). Então, somos uma árvore de pesquisa binária equilibrada.

Answer 10

heap de ordenação da árvore..nlogn complexidade..