En una BST dos nodos se intercambian aleatoriamente, necesitamos encontrar esos dos nodos y volver a intercambiarlos

Question

Dado un árbol de búsqueda binaria, en el que se intercambian dos nodos. Así que tenemos que encontrar esos dos nodos y volver a intercambiarlos (tenemos que intercambiar los nodos, no los datos)

He intentado hacer esto haciendo una matriz adicional que tiene el recorrido intermedio del árbol y también guarda la puntero a cada nodo Luego solo cruzamos la matriz y encontramos los dos nodos que están en el orden, ahora estos dos nodos se buscan en el árbol y luego se intercambian

Así que mi pregunta es cómo resolver este problema en O (1) espacio ?

Answer 1

In order traversal en una BST le da un recorrido en los elementos, ordenados.
Puede utilizar un recorrido en orden, encontrar los dos elementos fuera de lugar (almacenarlos en dos punteros) y cambiarlos.

Este método en realidad está creando la matriz que describió sobre la marcha, sin crearla realmente.

Sin embargo, tenga en cuenta que el consumo de espacio no es O(1), es O(h) donde h es la altura del árbol, debido a la traza de la pila. Si el árbol está equilibrado, será O(logn)

Answer 2

Dependiendo de la BST, esto se puede hacer en O (1).

Por ejemplo, si los nodos del árbol tienen un puntero a sus padres, puede usar la implementación descrita en la sección nonRecrusiveInOrderTraversal de la página de Wikipedia para Tree_traversal.

Como otra posibilidad, si BST se almacena como una matriz unidimensional, en lugar de punteros entre nodos, simplemente puede caminar sobre la matriz (y hacer los cálculos para determinar el padre e hijos de cada nodo).

Mientras realiza la travesía/caminata, verifique si el elemento actual está en el lugar correcto.

Si no lo está, entonces puede ver dónde debe estar en el árbol e intercambiar con el elemento en esa ubicación. (tenga cuidado si la raíz está en el lugar equivocado).

Answer 3

Podemos modificar el método isBST() de la siguiente manera para intercambiar esos 2 nodos intercambiados aleatoriamente y corregirlos.

/* Returns true if the given tree is a binary search tree 
(efficient version). */ 
int isBST(struct node* node) 
{ 
    struct node *x = NULL; 
    return(isBSTUtil(node, INT_MIN, INT_MAX,&x)); 
} 

/* Returns true if the given tree is a BST and its 
    values are >= min and <= max. */ 
int isBSTUtil(struct node* node, int min, int max, struct node **x) 
{ 

    /* an empty tree is BST */ 
    if (node==NULL) 
    return 1; 

    /* false if this node violates the min/max constraint */ 
    if (node->data < min || node->data > max) { 
    if (*x == NULL) { 
     *x = node;//same the first incident where BST property is not followed. 
    } 
    else { 
     //here we second node, so swap it with *x. 
     int tmp = node->data; 
     node->data = (*x)->data; 
     (*x)->data = tmp; 

    } 
    //return 0; 
    return 1;//have to return 1; as we are not checking here if tree is BST, as we know it is not BST, and we are correcting it. 
    } 
    /* otherwise check the subtrees recursively, 
    tightening the min or max constraint */ 
    return 
    isBSTUtil(node->left, min, node->data-1, x) && // Allow only distinct values 
    isBSTUtil(node->right, node->data+1, max, x); // Allow only distinct values 
}