advertisement

Arboles 2-3 Insertar Eliminar

63 %
37 %
advertisement
Information about Arboles 2-3 Insertar Eliminar
ing

Published on November 23, 2007

Author: evansbv

Source: slideshare.net

Description

Arboles 2-3 Insertar Eliminar
advertisement

ESTRUCTURA DE DATOS II ÁRBOLES 2-3 UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIA PROFESOR: Ing. Evans Balcazar Veizaga

PROFESOR:

Ing. Evans Balcazar Veizaga

Árboles 2-3: Los árboles 2-3 son árboles cuyos nodos internos pueden contener hasta 2 elementos (todos los árboles vistos con anterioridad pueden contener sólo un elemento por nodo), y por lo tanto un nodo interno puede tener 2 o 3 hijos, dependiendo de cuántos elementos posea el nodo. De este modo, un nodo de un árbol 2-3 puede tener una de las siguientes formas:

Los árboles 2-3 son árboles cuyos nodos internos pueden contener hasta 2 elementos (todos los árboles vistos con anterioridad pueden contener sólo un elemento por nodo), y por lo tanto un nodo interno puede tener 2 o 3 hijos, dependiendo de cuántos elementos posea el nodo.

De este modo, un nodo de un árbol 2-3 puede tener una de las siguientes formas:

Árboles 2-3 – Representación: Un árbol 2-3 puede ser simulado utilizando árboles binarios. Una propiedad de los árboles 2-3 es que todas las hojas están a la misma profundidad , es decir, los árboles 2-3 son árboles perfectamente balanceados . La siguiente figura muestra un ejemplo de un árbol 2-3:

Un árbol 2-3 puede ser simulado utilizando árboles binarios.

Una propiedad de los árboles 2-3 es que todas las hojas están a la misma profundidad , es decir, los árboles 2-3 son árboles perfectamente balanceados . La siguiente figura muestra un ejemplo de un árbol 2-3:

Insercion 2-3 : Para insertar un elemento X en un árbol 2-3 se realiza una búsqueda infructuosa y se inserta dicho elemento en el último nodo visitado durante la búsqueda, lo cual implica manejar dos casos distintos: Caso 1 : Si el nodo donde se inserta X tenía una sola llave (dos hijos), ahora queda con dos llaves (tres hijos).

Para insertar un elemento X en un árbol 2-3 se realiza una búsqueda infructuosa y se inserta dicho elemento en el último nodo visitado durante la búsqueda, lo cual implica manejar dos casos distintos:

Insercion 2-3 : Para insertar un elemento X en un árbol 2-3 se realiza una búsqueda infructuosa y se inserta dicho elemento en el último nodo visitado durante la búsqueda, lo cual implica manejar dos casos distintos: Caso 2 : Si el nodo donde se inserta X tenía dos llaves (tres hijos), queda transitoriamente con tres llaves (cuatro hijos) y se dice que está saturado ( overflow ). El problema se resuelve a nivel de X y Z , pero es posible que el nodo que contiene a Y ahora este saturado. En este caso, se repite el mismo prodecimiento anterior un nivel más arriba. Finalmente, si la raíz es el nodo saturado, éste se divide y se crea una nueva raíz un nivel más arriba. Esto implica que los árboles 2-3 crecen "hacia arriba".

Para insertar un elemento X en un árbol 2-3 se realiza una búsqueda infructuosa y se inserta dicho elemento en el último nodo visitado durante la búsqueda, lo cual implica manejar dos casos distintos:

El problema se resuelve a nivel de X y Z , pero es posible que el nodo que contiene a Y ahora este saturado. En este caso, se repite el mismo prodecimiento anterior un nivel más arriba. Finalmente, si la raíz es el nodo saturado, éste se divide y se crea una nueva raíz un nivel más arriba. Esto implica que los árboles 2-3 crecen "hacia arriba".

Ejemplo de Insercion 2-3 : El problema se resuelve a nivel de X y Z , pero es posible que el nodo que contiene a Y ahora este saturado. En este caso, se repite el mismo prodecimiento anterior un nivel más arriba. Finalmente, si la raíz es el nodo saturado, éste se divide y se crea una nueva raíz un nivel más arriba. Esto implica que los árboles 2-3 crecen "hacia arriba".

El problema se resuelve a nivel de X y Z , pero es posible que el nodo que contiene a Y ahora este saturado.

Eliminacion 2-3 : Sin perder generalidad se supondrá que el elemento a eliminar, Z , se encuentra en el nivel más bajo del árbol. Si esto no es así, entonces el sucesor y el predecesor de Z se encuentran necesariamente en el nivel más bajo ; En este caso basta con borrar uno de ellos y luego escribir su valor sobre el almacenado en Z . La eliminación también presenta dos posibles casos: Caso 1: El nodo donde se encuentra Z contiene dos elementos. En este caso se elimina Z y el nodo queda con un solo elemento.

Sin perder generalidad se supondrá que el elemento a eliminar, Z , se encuentra en el nivel más bajo del árbol. Si esto no es así, entonces el sucesor y el predecesor de Z se encuentran necesariamente en el nivel más bajo ;

Eliminacion 2-3 : Sin perder generalidad se supondrá que el elemento a eliminar, Z , se encuentra en el nivel más bajo del árbol. Si esto no es así, entonces el sucesor y el predecesor de Z se encuentran necesariamente en el nivel más bajo ; Caso 2-A : El nodo donde se encuentra Z contiene un solo elemento. En este caso al eliminar el elemento Z el nodo queda sin elementos ( underflow ). Si el nodo hermano posee dos elementos, se le quita uno y se inserta en el nodo con underflow .

Sin perder generalidad se supondrá que el elemento a eliminar, Z , se encuentra en el nivel más bajo del árbol. Si esto no es así, entonces el sucesor y el predecesor de Z se encuentran necesariamente en el nivel más bajo ;

Eliminacion 2-3 : Sin perder generalidad se supondrá que el elemento a eliminar, Z , se encuentra en el nivel más bajo del árbol. Si esto no es así, entonces el sucesor y el predecesor de Z se encuentran necesariamente en el nivel más bajo ; Caso 2-B : Si el nodo hermano contiene solo una llave, se le quita un elemento al padre y se inserta en el nodo con underflow . Si esta operación produce underflow en el nodo padre, se repite el procedimiento anterior un nivel más arriba. Finalmente, si la raíz queda vacía, ésta se elimina.

Sin perder generalidad se supondrá que el elemento a eliminar, Z , se encuentra en el nivel más bajo del árbol. Si esto no es así, entonces el sucesor y el predecesor de Z se encuentran necesariamente en el nivel más bajo ;

Practica 1: En un árbol 2-3 inicialmente vacío, insertar los elementos 20, 35, 50, 43, 12, 22,13, 14 y 52

En un árbol 2-3 inicialmente vacío, insertar los elementos 20, 35, 50, 43, 12, 22,13, 14 y 52

Practica 1: Insertar en el siguiente árbol 2-3 los elementos: 80, 40 y 70

Insertar en el siguiente árbol 2-3 los elementos: 80, 40 y 70

GRACIAS INF-310 Estructura de Datos II

Add a comment

Related pages

Árboles 2-3, 2-3-4 by Ernesto Lenin Fonseca Almerida on Prezi

Árbol 2-3 Ahora se quiere insertar el 38.. Se divide la “Hoja” y el 39 se mueve hacia arriba Método de Eliminar ... Eliminar en árboles 2-3-4
Read more

Codigo Arbol 234 en Java (operaciones de Insertar, Borrar ...

... este codigo con las tres operaciones basicas que son insertar, ... de Arboles Binarios ... de Búsqueda, Eliminar un Nodo ...
Read more

Programar árboles binarios parte 2 – Eliminar Nodos | Ser ...

Las diferentes formas de eliminar nodos ... http://serprogramador.es/programacion/programar-arboles-binarios ... adjunto el archivo de insertar ...
Read more

SEED - Arbol 1-2-3

Requerimientos funcionales implementados para Arboles 1-2-3: RF1 ... del Árbol 1-2-3. RF3 - Insertar nuevos datos ... Eliminar datos de un Árbol 1-2-3, ...
Read more

Árbol 2-3 - Wikipedia, la enciclopedia libre

A la hora de insertar un nuevo dato en un árbol 2-3 se hace de forma que se mantenga el equilibrio en el árbol. ... Ejemplo de eliminar :
Read more

Arbol 1-2-3

Un árbol 1-2-3 es un árbol n-ario de orden tres. ... * @see uniandes.cupi2.collections.arbol.IArbolOrdenado#insertar ... public Nodo1_2_3 eliminar ...
Read more