6926135
Description
Mind Map by LUIS FERNANDO JUAREZ JIMENEZ, updated more than 1 year ago
|
|
Created by LUIS FERNANDO JUAREZ JIMENEZ
about 8 years ago
|
|
unidades 5,6 y 7
- arboles y busqueda
- Se trata de árboles de orden 2 en los que
se cumple que para cada nodo, el valor
de la clave de la raíz del subárbol
izquierdo es menor que el valor de la
clave del nodo y que el valor de la clave
raíz del subárbol derecho es mayor que
el valor de la clave del nodo. Árbol
binario de búsqueda
- ^ El repertorio de operaciones que se pueden
realizar sobre un ABB es parecido al que
realizábamos sobre otras estructuras de datos,
más alguna otra propia de árboles: Buscar un
elemento. Insertar un elemento. Borrar un
elemento. Movimientos a través del árbol:
Izquierda. Derecha. Raiz. Información:
Comprobar si un árbol está vacío. Calcular el
número de nodos. Comprobar si el nodo es
hoja. Calcular la altura de un nodo. Calcular la
altura de un árbol.
- ^ El repertorio de operaciones que se pueden
realizar sobre un ABB es parecido al que
realizábamos sobre otras estructuras de datos,
más alguna otra propia de árboles: Buscar un
elemento. Insertar un elemento. Borrar un
elemento. Movimientos a través del árbol:
Izquierda. Derecha. Raiz. Información:
Comprobar si un árbol está vacío. Calcular el
número de nodos. Comprobar si el nodo es
hoja. Calcular la altura de un nodo. Calcular la
altura de un árbol.
- Se trata de árboles de orden 2 en los que
se cumple que para cada nodo, el valor
de la clave de la raíz del subárbol
izquierdo es menor que el valor de la
clave del nodo y que el valor de la clave
raíz del subárbol derecho es mayor que
el valor de la clave del nodo. Árbol
binario de búsqueda
- busqueda de un elemento
- ^ Partiendo siempre del nodo raíz, el modo
de buscar un elemento se define de forma
recursiva. Si el árbol está vacío, terminamos
la búsqueda: el elemento no está en el
árbol. Si el valor del nodo raíz es igual que
el del elemento que buscamos, terminamos
la búsqueda con éxito. Si el valor del nodo
raíz es mayor que el elemento que
buscamos, continuaremos la búsqueda en
el árbol izquierdo. Si el valor del nodo raíz
es menor que el elemento que buscamos,
continuaremos la búsqueda en el árbol
derecho. El valor de retorno de una función
de búsqueda en un ABB puede ser un
puntero al nodo encontrado, o NULL, si no
se ha encontrado.
- ^ Partiendo siempre del nodo raíz, el modo
de buscar un elemento se define de forma
recursiva. Si el árbol está vacío, terminamos
la búsqueda: el elemento no está en el
árbol. Si el valor del nodo raíz es igual que
el del elemento que buscamos, terminamos
la búsqueda con éxito. Si el valor del nodo
raíz es mayor que el elemento que
buscamos, continuaremos la búsqueda en
el árbol izquierdo. Si el valor del nodo raíz
es menor que el elemento que buscamos,
continuaremos la búsqueda en el árbol
derecho. El valor de retorno de una función
de búsqueda en un ABB puede ser un
puntero al nodo encontrado, o NULL, si no
se ha encontrado.
- inserccion de un elementlo
- Para insertar un elemento nos basamos en el algoritmo de
búsqueda. Si el elemento está en el árbol no lo insertaremos. Si no
lo está, lo insertaremos a continuación del último nodo visitado.
Necesitamos un puntero auxiliar para conservar una referencia al
padre del nodo raíz actual. El valor inicial para ese puntero es NULL.
Padre = NULL nodo = Raiz Bucle: mientras actual no sea un árbol
vacío o hasta que se encuentre el elemento. Si el valor del nodo raíz
es mayor que el elemento que buscamos, continuaremos la
búsqueda en el árbol izquierdo: Padre=nodo,
nodo=nodo->izquierdo. Si el valor del nodo raíz es menor que el
elemento que buscamos, continuaremos la búsqueda en el árbol
derecho: Padre=nodo, nodo=nodo->derecho. Si nodo no es NULL, el
elemento está en el árbol, por lo tanto salimos. Si Padre es NULL, el
árbol estaba vacío, por lo tanto, el nuevo árbol sólo contendrá el
nuevo elemento, que será la raíz del árbol. Si el elemento es menor
que el Padre, entonces insertamos el
- Para insertar un elemento nos basamos en el algoritmo de
búsqueda. Si el elemento está en el árbol no lo insertaremos. Si no
lo está, lo insertaremos a continuación del último nodo visitado.
Necesitamos un puntero auxiliar para conservar una referencia al
padre del nodo raíz actual. El valor inicial para ese puntero es NULL.
Padre = NULL nodo = Raiz Bucle: mientras actual no sea un árbol
vacío o hasta que se encuentre el elemento. Si el valor del nodo raíz
es mayor que el elemento que buscamos, continuaremos la
búsqueda en el árbol izquierdo: Padre=nodo,
nodo=nodo->izquierdo. Si el valor del nodo raíz es menor que el
elemento que buscamos, continuaremos la búsqueda en el árbol
derecho: Padre=nodo, nodo=nodo->derecho. Si nodo no es NULL, el
elemento está en el árbol, por lo tanto salimos. Si Padre es NULL, el
árbol estaba vacío, por lo tanto, el nuevo árbol sólo contendrá el
nuevo elemento, que será la raíz del árbol. Si el elemento es menor
que el Padre, entonces insertamos el
Media attachments
Want to create your own Mind Maps for free with GoConqr? Learn more.