¿Cómo inserta este código un nuevo nodo en un árbol binario?

Según tengo entendido, este árbol de búsqueda binaria tiene su estructura de nodo de la siguiente manera:

árbol de estructura
{
item_type x;
struct Tree * left;
struct Tree * right;
estructura Tree * parent;
}

Por lo tanto, un método de inserción asignará dinámicamente memoria para el nuevo nodo y almacenará los 4 elementos de datos (cualesquiera que sean: valores o dirección) en ese nodo. Es decir:

1. Almacene el valor del artículo en x.
2. Almacene la dirección del nodo secundario izquierdo: será NULL cuando inserte un nuevo nodo.
3. Almacene la dirección del nodo secundario derecho: será NULL cuando inserte un nuevo nodo.
4. Almacene la dirección del nodo primario del nuevo nodo.

Se insertará un nuevo nodo en el lugar correcto del árbol, lo que implica que el algoritmo debe incorporar la propiedad BST mientras se itera sobre el árbol. El método anterior adopta un enfoque basado en la recursividad para hacer esto.

Déjame contarte acerca de los dobles punteros antes de discutir este método:

Un puntero contiene una dirección de memoria de una variable (mismo tipo que el puntero)

1. int a = 10;
2. int * ptr = & a;
La segunda declaración anterior almacenó la dirección del entero ‘a’ en la variable de puntero ‘ptr’.

Para acceder a ‘a’ a través del puntero ‘ptr’, necesitamos desreferenciar el último. Dereferencia: vaya a la dirección a la que apunta el puntero y obtenga el valor.

Puede hacer * ptr para obtener el valor en la dirección a la que apunta el puntero.

Un puntero doble, como su nombre indica, será un “puntero a puntero”. En otras palabras, almacenará la dirección del puntero.

3. int ** ptr1 = & ptr;

La declaración anterior almacena la dirección de ‘ptr’ en ‘ptr1’.

Digamos que la dirección de la variable a es 1000
Digamos que la dirección de la variable de puntero es 2000

Entonces, el contenido de los punteros sería:

ptr tendrá 1000: almacena la dirección de la variable a.
ptr1 tendrá 2000: almacena la dirección de la variable de puntero ptr

Reglas similares de desreferenciación (usando el operador *) son aplicables ahora también.

* ptr significa ir y obtener el valor en la dirección 1000. El resultado sería 10.

* ptr1 significa ir y obtener el valor en la dirección 2000. El resultado sería 1000.

** ptr1 significa anidar las 2 operaciones anteriores en orden inverso: vaya y obtenga el valor en la dirección 2000. Esto nos da 1000. Ahora obtenga el valor en esta ubicación de memoria. Esto le dará el valor de la variable ‘a’ (10).

Volviendo al programa anterior:

Argumentos:

I: un puntero doble a la raíz de BST . Esto será NULL cuando el árbol aún no se haya inicializado y el primer nodo aún no se haya creado.

En algún lugar del programa, debe haber una variable ‘ Tree * root ‘ y esta es la raíz del BST. Es un puntero y la dirección de este puntero se pasa a la variable I (puntero doble) en el método de inserción.

Siguiendo los principios básicos de doble puntero anteriores: podemos decir que:

La variable ‘raíz’ almacena la dirección del nodo raíz. Será NULL si el árbol aún no se ha creado.

La variable ‘I’ almacena la dirección de la variable de puntero ‘root’. Por ejemplo:

Árbol * raíz = NULL;
insert (& root, x, NULL);

X : nuevo elemento de datos que se insertará en el nuevo nodo.

Parent : dirección del padre del nuevo nodo (que se creará). Tenga en cuenta que el padre de la raíz será NULL. Esto siempre se pasará como NULL a la función. Más tarde, durante las llamadas recursivas, su valor cambiará. Más tarde diré por qué.

Digamos que el árbol aún no se ha creado. Implica que el contenido de ‘root’ será NULL. No apunta a nada.

Digamos que la dirección de la variable del puntero ‘raíz’ es 1000.

1. La dirección del puntero raíz (1000) se pasará a I (puntero a raíz).
2. X tendrá algún elemento.
3. Los padres serán NULOS.

Verificamos si root es NULL o no. ¿Cómo verificamos esto?

Al desreferenciar el puntero doble I como * I, significa ir a la ubicación de memoria 1000 y obtener el valor. Si es NULL, implica que la raíz es NULL

La condición si (* I == NULL) verifica esto.

Ahora ingresa el bloque if, y crea un nuevo nodo asignando memoria del montón. La variable temporal ‘p’ almacena la dirección devuelta por malloc (digamos 2000) para el fragmento de memoria recientemente asignado. Luego almacena los datos requeridos en esa ubicación de memoria de la siguiente manera.

p-> elemento = x; (almacenar el artículo)
p-> left = p-> right = NULL; (cada nuevo nodo se insertará como hoja)
p-> parent = parent (que es NULL)

Ahora que se ha reservado una memoria para un nodo de árbol y se han almacenado datos en él, necesitamos actualizar nuestra estructura de datos de árbol.

El nodo creado anteriormente se convertirá en el nodo raíz. Significa que necesitamos almacenar (2000, que es la dirección de este nuevo nodo) en la variable de puntero ‘root’.

Como hacemos eso ? Recuerde que I (puntero doble) es un puntero a la raíz.

Simplemente desreferencia I como * I y asígnele el valor 2000.

La declaración (* I = p) hace esto: vaya a la ubicación de memoria 1000 y almacene el valor 2000.

Ahora acabamos de regresar.

Después de la primera llamada, el puntero ‘root’ tiene almacenada la dirección 2000. Tenemos una raíz para nuestro BST.

Ahora, se insertará el segundo elemento. Lo mismo que arriba:

1. La dirección del puntero raíz (1000) se pasará a I (puntero a raíz).
2. X tendrá algún elemento.
3. Los padres serán NULOS. Ahora te diré por qué.

Al ingresar al método, verificamos si root es NULL. La verificación falla. Por qué ?

if (* I == NULL) significa ir a la dirección 1000 y ver si el valor es NULL. No, no es. Es 2000, que no es igual a nulo.

No ingresamos el bloque if, y luego hacemos algunas comparaciones basadas en la propiedad BST típica y hacemos llamadas recursivas adecuadas con los argumentos apropiados.

1. Si el nuevo elemento a insertar es menor que la raíz, atravesamos el subárbol izquierdo.
1. Si el nuevo elemento a insertar es mayor que la raíz, atravesamos el subárbol derecho.

¿Cómo nos comparamos? (* I) -> artículo

(* I): significa ir a la ubicación de memoria 1000 (dirección del puntero raíz) y obtener el valor. Este valor es 2000 (ubicación de memoria de los datos del nodo raíz)

(* I) -> elemento – significa ir a la ubicación de memoria 2000 y obtener el valor de ‘elemento’.

Entonces puedes comparar como
si ((* I) -> elemento> X)
{hacer una llamada recursiva para la inserción en el subárbol izquierdo}
más
{hacer una llamada recursiva para la inserción en el subárbol derecho}

¿Cómo hacemos llamadas recursivas?

La verificación de condición anterior determinará en qué subárbol se realizará la inserción. Para poder hacer eso, debemos entender que:

1. A medida que hacemos llamadas recursivas en cualquiera de los subárboles (según lo determinado por la condición anterior), el árbol virtual que será examinado por la llamada recursiva tiene que ser diferente.

2. La llamada recursiva ya no puede funcionar con la misma raíz de nivel superior del BST. El hijo izquierdo o derecho (dependiendo de qué subárbol necesita ser examinado) de la raíz del nivel superior será tratado virtualmente como la raíz del árbol que será examinada por la llamada recursiva. Este procedimiento continuará mientras se realicen las llamadas recursivas y se encuentre el punto de inserción correcto en el árbol.

3. El padre ya no puede ser NULL. Era NULL solo para la raíz de nivel superior. Ahora que las llamadas recursivas examinarán un árbol “virtualmente” enraizado en un nodo diferente, el puntero principal ya no puede ser NULL. Seguirá cambiando a medida que la pila de llamadas de recursividad crezca.

4. Necesitamos actualizar los punteros del nodo primario al nodo secundario (uno recién creado) dependiendo de si el nuevo nodo se crea como un elemento secundario izquierdo o derecho de su elemento primario. Esta es la parte más importante para entender en las llamadas recursivas.

Recurrente para el subárbol izquierdo

insert (dirección del puntero apuntando al hijo izquierdo de la raíz actual, X, dirección de la raíz actual);

que se convierte en:

insertar (& ((* I) -> izquierda), X, * I);

& ((* I) -> left): esta es la dirección [puntero que apunta al hijo izquierdo de la raíz actual].

X: elemento

* I: Desreferenciar el puntero doble a la raíz virtual actual para obtener la dirección del fragmento de memoria que contiene los datos de esta raíz virtual. Esta dirección se almacenará como el contenido del puntero principal del nuevo nodo.

Este proceso se repetirá y los parámetros pasados se cambiarán a medida que la pila de recursividad crezca.

Recurrente para el subárbol correcto

insert (dirección del puntero apuntando al hijo derecho de la raíz actual, X, dirección de la raíz actual);

que se convierte en:

insertar (& ((* I) -> derecha), X, * I);

& ((* I) -> derecha): esta es la dirección [puntero que apunta al hijo derecho de la raíz actual].

X: igual que el anterior

* I: igual que el anterior

Espero que esto ayude. Avísame si quieres una explicación esquemática. Proporcionaré eso.

AlgoritmosÁrboles binariosEstructuras de datosProgramación informática

Si tengo una matriz compuesta de cadenas de dígitos y guiones, ¿cómo puedo usar Javascript para agregar la suma de cada dígito mientras omito los guiones?

¿Cómo determina el algoritmo de alimentación de Quora el contenido a mostrar?

¿Qué algoritmo se usa en el juego Fifa 13?

¿Cuál es el algoritmo de aprendizaje automático requerido para el asistente virtual?

¿Hay futuro para los sistemas embebidos o el diseño VLSI?

¿Por qué no puedo resolver mi Cubo de Rubik de 4 x 4 x 4 como un cubo de Rubik de 3 x 3 x 3 si ya he hecho los centros y los bordes?

Puede escribir muchos códigos para esto, quiero decir que hay toneladas de códigos para agregar un valor al árbol binario. Pero todos ellos tienen la misma idea en la raíz. Así que intentaré decirte algo al respecto.

El árbol binario tiene su propia clasificación en sus hojas hasta la raíz. Ponen los valores más pequeños a la izquierda y los greatres a la derecha. Entonces, cuando intentes leer todas las hojas de izquierda a derecha, verás que los números están creciendo.

Entonces, puedo decir que si intenta agregar un nuevo valor al árbol, puede verificar las reglas a continuación que escribí para usted.

* Compruebe si el valor en el nodo actual y un nuevo valor son iguales. Si es así, se encuentra un duplicado. De otra manera,
* Si un nuevo valor es menor que el valor del nodo
* Si un nodo actual no tiene hijo secundario, se ha encontrado un lugar para la inserción
* De lo contrario, maneje el niño izquierdo con el mismo algoritmo.
* Si un nuevo valor es mayor que el valor del nodo
* Si un nodo actual no tiene un hijo derecho, se ha encontrado un lugar para la inserción
* De lo contrario, maneje al niño correcto con el mismo algoritmo.

Ahora podemos mirar los punteros.
Como puede ver y saber (supongo), si tiene alguna variable con dos estrellas de puntero, puede decir que hay un valor en una variable, y hay un puntero que señala su dirección y otro puntero ese punto uno antes de que me apunten los punteros. Quiero decir que hay un montón de direcciones que se muestran una a otra, por lo que no hay necesidad de dejar de pensar.

Te sugiero que si quieres aprender buenos puntos sobre C / C ++ hay libros de Herbert Schildt que realmente apoyo, pero debes saber antes de leerlos, estos libros son realmente geniales, y hay una dirección web que puedes ver Un montón de tutoriales y algunos trucos 🙂 un libro más que si quieres aprender todo tipo de ejemplos sobre C / C ++, puedes hacer todos los ejercicios en Deitell & Deitell.

Siddharth Teotia

Para comprender la cuestión del doble puntero, debe tener en cuenta que en su implementación un árbol binario se modela como un puntero al nodo raíz. Es decir, el árbol tipo * representa todo el árbol. Bajo esta representación, el árbol vacío simplemente se representa como NULL.

Ahora, el problema es que cuando se inserta en un árbol vacío t (es decir, t es un árbol * cuyo valor es NULL), desea que t termine apuntando al nodo único del nuevo árbol. Por lo tanto, debe modificar el valor del puntero t. Como puede saber (o no), C tiene una semántica de paso por valor:

void inc_in_place(int x) { ++x; } int main() { int x = 0; inc_in_place(x); printf("x = %d\n", x); // Prints 0, not 1 return 0; }

Obtiene un cero porque inc_in_place recibe una copia de x, descartada tan pronto como abandona la función. Entonces, el truco cuando queremos modificar un parámetro pasado a un procedimiento es pasarle un puntero: obtendrá una copia del puntero, pero eso está bien porque la copia todavía apunta al parámetro que queremos modificar dentro del procedimiento :

void inc_in_place(int* x) { ++(*x); } int main() { int x = 0; inc_in_place(&x); printf("x = %d\n", x); // Prints 1 return 0; }

Y es por eso que tiene un puntero doble: dado que querrá modificar el puntero en caso de que sea NULL, debe pasar un puntero al árbol. Eso es todo, el árbol de tipos **. El primer asterisco es parte de la representación de la estructura de datos del árbol, el segundo es porque así es como se emula el paso por referencia en C.

El resto de la implementación es sencillo. Puede ver que si el árbol está vacío (* l == NULL), simplemente asignamos un nuevo nodo, inicializamos y modificamos l (* l = p) para que ahora apunte al nuevo nodo. De lo contrario, insertamos recursivamente en el subárbol izquierdo o derecho en consecuencia. Eventualmente llegaremos a un subárbol vacío, y dado que estamos pasando punteros a los subárboles (recuerde, escriba tree **), el nodo padre se actualizará correctamente para apuntar al nodo insertado. El tercer parámetro es el nodo padre, solo se usa para mantener un puntero al padre en cada nodo.

Orçun Yılmaz

More Interesting

¿Cuáles son los 100 deben resolver preguntas de SPOJ?

¿Cuál es el punto de usar programación dinámica cuando la complejidad de tiempo en la mayoría de los códigos es O (n ^ 2) (que no es tan bueno, es decir, usamos dobles para bucles incluso en DP)?

¿Qué estructuras de datos y algoritmos de programación heredados se enseñan en la universidad pero que no se usan después de la academia? ¿Aún debemos aprenderlos?

¿Qué es mejor entre la búsqueda binaria y el árbol de búsqueda binaria para buscar?

¿Cuáles son los parámetros que afectan el tiempo de ejecución de un algoritmo?

¿Cómo termina una imagen en la página principal de reddit o imgur?

¿Cuáles son los algoritmos más eficientes que resuelven de manera óptima un cubo de Rubik?

¿Qué tecnología utiliza X ?: ¿Cómo implementan las empresas de análisis (Mixpanel, KISSMetrics, etc.) el análisis de embudos?

¿Qué tan buena es la calidad de los problemas de HackerRank en comparación con los problemas de Topcoder, Codeforces, Codechef?

Alguien en mi escuela secundaria dijo que en realidad no puedo resolver un cubo de Rubik porque tengo que confiar en patrones (algoritmos). ¿Cuán verdadera es esta afirmación?