Cómo convertir un árbol binario en un árbol de búsqueda binario en el lugar, es decir, no podemos usar ningún espacio adicional

Question

Cómo convertir un árbol binario en un árbol de búsqueda binario en el lugar, es decir, no podemos usar ningún espacio adicional.

Answer 1

No da mucho para seguir, pero si el requisito es lo que creo que es, tiene un árbol binario ya creado y sentado en la memoria, pero no ordenado (la forma en que desea que se clasifique, de todas formas).

Estoy asumiendo que los nodos del árbol se parecen a

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

También estoy asumiendo que usted puede leer C

pesar de que podría sentarse a la vuelta preguntándose por qué este árbol fuera creado sin tener ha sido creado en orden ordenado que no nos sirve de nada, por lo que lo ignoraré y solo me ocuparé de ordenarlo.

El requisito de que no se use espacio extra es extraño. Temporalmente habrá espacio extra, solo en la pila. Voy a suponer que eso significa llamar malloc o algo así y también que el árbol resultante no tiene que usar más memoria que el árbol sin clasificar original.

La primera y más fácil solución es realizar un recorrido de preorden del árbol sin clasificar eliminando cada nodo de ese árbol y realizando una inserción ordenada en un árbol nuevo. Este es O (n + n log (n)), que es O (n log (n)).

Si esto no es lo que quieren y vas a tener que usar rotaciones y esas cosas ... ¡eso es horrible!

Pensé que podrías hacer esto haciendo una versión impar de un montón, pero me encontré con problemas. Otra cosa que sí me vino a la mente, que sería terriblemente lenta, sería hacer una versión extraña del tipo de burbuja en el árbol.

Para esto, cada nodo se compara y posiblemente se intercambia con cada uno de sus hijos directos (y por lo tanto también con su padre) repetidamente hasta que atraviesa el árbol y no encuentra ningún swaps necesarios.Hacer una clase de agitador (clasificación de burbuja que va de izquierda a derecha y de derecha a izquierda) funcionaría mejor, y después del pase inicial no tendrías que atravesar subárboles que no parecían desordenados con respecto a su padre .

Estoy seguro de que este algorthm fue pensado por alguien más antes que yo y tiene un nombre genial que simplemente no sé, o que es fundamentalmente defectuoso de alguna manera que no estoy viendo.

Proceder con los cálculos de tiempo de ejecución para la segunda sugerencia es bastante complicado. Al principio pensé que sería simplemente O (n^2), como el tipo de burbuja y agitador, pero no puedo convencerme de que la evitación transversal del subárbol podría no ganar lo suficiente como para hacerlo un poco mejor que O (n^2). Básicamente, los géneros de burbujas y agitadores también obtienen esta optimización, pero solo en los extremos donde la clasificación total se produce temprano y puede recortar los límites. Con esta versión de árbol, obtienes oportunidades para evitar trozos en el medio del conjunto también. Bueno, como dije, probablemente sea fatalmente defectuoso.

Answer 2

Un árbol binario generalmente es un árbol de búsqueda binaria, en cuyo caso no se requiere conversión.

Quizás necesite aclarar la estructura de lo que está convirtiendo. ¿Tu árbol fuente está desequilibrado? ¿No está ordenado por la tecla que desea buscar? ¿Cómo llegaste al árbol fuente?

Answer 3

Bueno, si esta es una pregunta de entrevista, lo primero que me tragaría (sin pensarlo) es esto: iterar todo el binario recursivamente y encontrar el elemento más pequeño. Sácalo del árbol binario. Ahora, repita el proceso donde itera todo el árbol y busca el elemento más pequeño, y lo agrega como elemento primario del último elemento encontrado (con el elemento anterior convirtiéndose en el hijo izquierdo del nodo nuevo). Repita tantas veces como sea necesario hasta que el árbol original esté vacío. Al final, te queda el peor árbol binario ordenado posible: una lista vinculada. Su puntero apunta al nodo raíz, que es el elemento más grande.

Este es un algoritmo horrible: O (n^2) tiempo de ejecución con la peor salida de árbol binario posible, pero es un punto de partida decente antes de llegar a algo mejor y tiene la ventaja de que usted puede escriba el código en unas 20 líneas en una pizarra.

Answer 4

Haga el recorrido inorden del árbol binario y almacene el resultado. ordena el resultado en orden a la izquierda forma el árbol de búsqueda binaria tomando el elemento medio de la lista ordenada como raíz (esto puede hacerse mediante búsqueda binaria). entonces obtenemos un árbol de búsqueda binaria equilibrado.

Answer 5

Haz el siguiente algoritmo para llegar a la solución.

1) encuentre el sucesor en orden sin utilizar ningún espacio.

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) Realice el recorrido sin espacio.

a) Encuentra el primer nodo de recorrido interno. Debería dejar a la mayoría de los hijos del árbol si los tiene, o a la izquierda del primer hijo de la derecha si lo tiene, o al propio hijo de la derecha. b) Usa el algoritmo anterior para descubrir el sucesor del primer nodo. c) Repita el paso 2 para todo el sucesor devuelto.

Usa el algoritmo de arriba 2 y haz el recorrido en orden en el árbol binario sin usar espacio extra. Forme el árbol de búsqueda binaria al realizar el recorrido. Pero la complejidad es O(N2) el peor caso.

Answer 6

pila de clasificación del árbol .. .. complejidad nlogn

Answer 7

Hacer el orden posterior de recorrido y desde que crear un árbol de búsqueda binaria.

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 8

Convertir Binary Tree a un lista- doblemente enlazada se puede hacer in situ en O (n)
luego clasificarla el uso de combinar especie, nlogn
Convertir la lista de nuevo a un árbol - O (n)

Solución nlogn simple.

Answer 9

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

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); 
}