Comment convertir un arbre binaire en arbre binaire de recherche en place, à savoir, nous ne pouvons pas utiliser d'espace supplémentaire

Question

Comment convertir un arbre binaire en arbre binaire de recherche en place, à savoir, nous ne pouvons pas utiliser d'espace supplémentaire.

Answer 1

Vous ne donnez pas grand chose à faire, mais si l'exigence est ce que je pense qu'il est, vous avez un arbre binaire déjà créé et assis dans la mémoire, mais pas trié (la façon dont vous voulez qu'il soit trié, de toute façon ).

Je suppose que les nœuds d'arbres ressemblent

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

Je suppose que vous pouvez lire C

Alors que nous pouvions asseoir se demander pourquoi cet arbre n'a jamais été créé sans avoir été créé pour nous qui ne Sorted fait pas de bien, donc je vais l'ignorer et juste traiter les trier.

L'exigence d'utiliser pas d'espace supplémentaire est impair. Temporairement il y aura un espace supplémentaire, si seulement sur la pile. Je vais supposer que cela signifie que l'appel malloc ou quelque chose comme ça et que l'arbre résultant doit pas utiliser plus de mémoire que l'arbre d'origine non triés.

La première et la solution la plus simple est de faire un parcours de pré-commande de l'arbre unsorted retirer chaque noeud de cet arbre et faisant une insertion triée dans un nouvel arbre. Ceci est O (n + n log (n)), qui est O (n log (n)).

Si ce n'est pas ce qu'ils veulent et vous allez devoir utiliser des rotations et des choses ..... c'est horrible!

Je pensais que vous pouvez le faire en faisant une version étrange d'une sorte de tas, mais je suis tombé sur des problèmes. Une autre chose qui ne viennent à l'esprit, ce qui serait horriblement lent, serait de faire une version étrange de tri à bulles sur l'arbre.

Pour ce chaque nœud est comparé et peut-être échangé avec chacun il y a des enfants directs (et donc aussi avec son parent) à plusieurs reprises jusqu'à ce que vous traversez l'arbre et ne trouvez aucune swaps nécessaires. Faire une sorte de shaker (bulle sorte que GOES gauche à droite et de droite à gauche) version de cela fonctionnerait mieux, et après le passage initial ne serait pas nécessaire de traverser vers le bas sous-arbres qui ne donnent l'ordre par rapport à son parent .

Je suis sûr que ce soit algorthm a été pensé par quelqu'un d'autre avant moi et a un nom cool que je ne sais pas, ou qu'il est fondamentalement erroné d'une certaine façon que je ne vois pas.

Venir avec les calculs d'exécution pour la deuxième suggestion est assez compliqué. Au début, je pensais que ce serait simplement O (n ^ 2), comme sortes de bulles et shaker, mais je ne peux pas me satisfaire que l'évitement sous-arbre traversal pourrait ne pas gagner assez pour faire un peu mieux que O (n ^ 2). Essentiellement sortes de bulles et shaker obtenir cette optimisation aussi, mais seulement aux extrémités où sortedness totale se produit au début et vous pouvez abattre les limites. Avec cette version de l'arbre que vous obtenez oppurtunities pour éviter éventuellement des morceaux au milieu de l'ensemble aussi bien. Eh bien, comme je l'ai dit, il est probablement vouée à l'échec.

Answer 2

Convertir Arbre binaire à un liste- doublement lié peut être fait inplace en O (n)
Ensuite, le tri en utilisant le tri par fusion, nlogn
Convertir la liste de retour à un arbre - O (n)

Solution simple nlogn.

Answer 3

Faites la Postorder Traversal et de ce créer un arbre de recherche binaire.

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

Faites algorithme suivant pour atteindre la solution.

1) trouver le successeur dans l'ordre sans utiliser l'espace.

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) Est-ce pour traversal sans utiliser l'espace.

a) Trouver le premier noeud de envue traversal. Il devrait plus laissé l'enfant de l'arbre si elle a, ou à gauche du premier enfant droit si elle a, ou droit de l'enfant lui-même. b) utiliser au-dessus de l'algorithme pour découvrir inoder successeur du premier noeud. c) Répétez l'étape 2 pour tout le successeur de retour.

Utilisez ci-dessus 2 algorithme et faire l'ordre dans traversal sur l'arbre binaire sans utiliser d'espace supplémentaire. Former l'arbre de recherche binaire durant traversal. Mais la complexité est O(N2) pire des cas.

Answer 5

Eh bien, si cela est une question d'entrevue, la première chose que je voudrais laisser échapper (avec zéro pensée réelle) est la suivante: itérer l'ensemble récursif binaire et et trouver le plus petit élément. Prenez-le de l'arbre binaire. Maintenant, répétez le processus où vous itérer l'arbre entier et de trouver l'élément le plus petit, et l'ajouter en tant que parent du dernier élément trouvé (à l'élément précédent devenir enfant gauche du nouveau nœud). Répétez autant de fois que nécessaire jusqu'à ce que l'arbre original est vide. A la fin, il vous reste la pire possible Sorted arbre binaire - une liste chaînée. Votre pointeur pointe vers le nœud racine, qui est le plus grand élément.

Ceci est un algorithme terrible tout autour - O (n ^ 2) Coucous la pire sortie d'arbre binaire possible, mais il est un point de départ décent avant de venir avec quelque chose de mieux et a l'avantage de vous être capable d'écrire le code pour en environ 20 lignes sur un tableau blanc.

Answer 6

Un arbre binaire habituellement est un arbre de recherche binaire, auquel cas aucune conversion est nécessaire.

Peut-être que vous avez besoin de clarifier la structure de ce que vous convertissez. Est votre source déséquilibrée? Est-il pas commandé par la clé que vous voulez rechercher sur? Comment êtes-vous arrivé à l'arbre source?

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

Faites afinde traversal de l'arbre binaire et stocker le résultat. trier les résultats par ordre acending former l'arbre de recherche binaire en prenant élément central de la liste triée en tant que root (cela peut faire en utilisant la recherche binaire). donc nous obtenons arbre binaire équilibré.

Answer 10

tas trier l'arbre .. complexité nlogn ..