Arboles de ordenamiento

Árbol 2-3
1. Explicar en qué consisten así como sus características principales.
2. Explicar el principio de funcionamiento

Una propiedad de los arboles es que todas las hojas están a la misma profundidad, la altura es log3(n) ≤ altura ≤ log2(n). Esta característica le permite conservar el balanceo tras insertar o borrar elementos, por lo que el algoritmo es casi tan rápido como en unárbol de búsqueda de altura mínima. Va creciendo hacia arriba y puede ser simulado utilizando arboles binarios.
r
I
D
r
I
C
D
Un árbol 2-3 puede tener una de las siguientes formas.

I<r<D I<r1<C<r 2 <D
En un árbol 2-3, los nodos internos han de tener 2 ò 3 hijos y todas las hojas han de estar al mismo nivel. De forma recursiva sepueden definir como:
A es un árbol 2-3 de altura h si:
* A es un árbol vacío (un árbol 2-3 de altura 0).
* A es de la forma (r, I, D), donde r es un nodo e I y D son árboles 2-3 de altura h – 1.
* A es de la forma (r, I, C, D), donde r es un nodo e I, C y D son árboles 2-3 de altura h-1.
Un árbol A es un árbol 2-3 de búsqueda de altura h si:
* Todos los elementos de I son menoresque r y todos los elementos de D son mayores que r.
* A es de la forma (r1, r2,I, C, D), donde r1 _ r2, I, Ac y D son árboles 2-3 de búsqueda de altura h-1 y todos los elementos de I son menores que r1, todos los elementos de C son mayores que r1 y menores que r2 y todos los elementos de D son mayores que r2.
Esta definición implica que el número de hijos de un nodo es siempre uno más que elnúmero de elementos que contiene ese nodo. En el caso de las hojas se permiten uno o dos elementos en el nodo.
INSERCION.
Para insertar un número (x) en el árbol se hace una búsqueda y se inserta en el último nodo visitado.
r

r1,r2

Inserta(x)
Si el nodo donde se inserta x tenía una sola llave (dos hijos), queda con dos llaves (tres hijos).

Inserta(x)
r1,r2

r1,
x
r2
Si el nododonde se inserta x tenis dos llaves, queda con tres llaves y se dice que está saturado, este problema se resuelve creando una nueva raíz en un nivel mas arriba.

ELIMINACIÓN.
El elemento a eliminar z esta en el nivel más bajo del árbol.
Eliminar(z)
r1

r1,z

El nodo donde se encuentra z contiene dos elementos, y el nodo queda con un solo elemento.

El nodo donde se encuentra z contiene unsolo elementos.
* Eliminar(z)
r
W,x
z
r
W,x

al eliminar z ese nodo queda sin elementos.

* Si el nodo hermano pose dos elementos, se le quita uno y se inserta como hijo de la raíz.
Eliminar(z)
r
W,x
z
x
W
r

* Pero si el nodo hermano contiene una sola llave, se le quita un elemento al padre y se le inserta aun nodo único

r
r
Eliminar(z)

X,r

x
z
xFuncionamiento.
* Cada  uno de los nodos, tiene uno o dos elementos.
* Todas las hojas están al mismo nivel.
* Todo nodo interno tiene dos o tres subárboles asociados.
* No existen elementos repetidos en el árbol.
* La raíz izquierda de cada nodo (elemento izquierdo) debe ser menor a la raíz derecha (elemento derecho).
* El subárbol izquierdo es un árbol 2-3 cuyos elementosson menores que la raíz izquierda.
* El subárbol central es un árbol 2-3 cuyos elementos son mayores que la raíz izquierda y menores que la raíz derecha.
* El subárbol derecho es un árbol 2-3 cuyos elementos son mayores que la raíz derecha.

3. Poner un ejemplo de funcionamiento

4. Determinar el orden de complejidad O de una búsqueda.

Los Arboles de búsqueda balanceados permitenrealizar las operaciones de búsqueda, inserción y borrado con complejidad O(log(n)).

5. Compararlos con los tipos de árboles de búsqueda estudiados en clases
* Los arboles- B crecen de abajo hacia arriba, así como los arboles-B 2-3.
* En el árbol-B tiene diferente orden y dependiendo de ese orden es el número de elementos en cada nodo. Y en el árbol-B 2-3, esto no aplica ya que...