Representacion y manipulacion de arboles.

Esta en una tarea extra, sobre arboles binarios, es informacion de wikipedia, me despejo las dudas.

Un árbol binario de búsqueda es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática.


Todo árbol vacío es un árbol binario de búsqueda.
Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
• En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo
almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol binario
de búsqueda.

• En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo
almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario
de búsqueda.

Puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos.

El interés de los árboles binarios de búsqueda (ABB) radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.
Dependiendo de las necesidades del usuario que trate con una estructura de este tipo se podrá permitir la igualdad estricta en alguno, en ninguno o en ambos de los subárboles que penden de la raíz. Permitir el uso de la igualdad provoca la aparición de valores dobles y hace la búsqueda más compleja.
BUSQUEDALa búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica. El maximo número de comparaciones que necesitaríamos para saber si un elemento se encuentra en un árbol binario de búsqueda estaría entre [log2(N+1)] y N, siendo N el número de nodos. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.



Ejemplo de versión iterativa en el lenguaje de programación C, suponiendo que estamos buscando una clave alojada en un nodo donde está el correspondiente "dato" que precisamos encontrar:


data Buscar_ABB(abb t,clave k)
{
abb p;
dato e;
e=NULL;
p=t;
if (!estaVacio(p))
{
while (!estaVacio(p) && (p->k!=k) )
{
if (k < p->k)
{
p=p->l;
}
if (p->k < k)
{
p=p->r;
}
}
if (!estaVacio(p) &&(p->d!=NULL) )
{
e=copiaDato(p->d);
}
}
return e;
}

Inserción
La inserción es similar a la búsqueda y se puede dar una solución tanto iterativa como recursiva. Si tenemos inicialmente como parámetro un árbol vacío se crea un nuevo nodo como único contenido el elemento a insertar. Si no lo está, se comprueba si el elemento dado es menor que la raíz del árbol inicial con lo que se inserta en el subárbol izquierdo y si es mayor se inserta en el subárbol derecho. De esta forma las inserciones se hacen en las hojas.


Como en el caso de la búsqueda puede haber varias variantes a la hora de implementar la inserción en el TAD (Tipo Abstracto de Datos), y es la decisión a tomar cuando el elemento (o clave del elemento) a insertar ya se encuentra en el árbol, puede que éste sea modificado o que sea ignorada la inserción. Es obvio que esta operación modifica el ABB perdiendo la versión anterior del mismo.

PROC InsertarABB(árbol:TABB; dato:TElemento)

VARIABLES
ele:TElemento
INICIO
SI (ABBVacío(árbol)) ENTONCES
árbol <- NUEVO(TNodoABB)
árbol^.izq <- NULO
árbol^.der <- NULO
árbol^.elem <- dato


EN OTRO CASO


ele = InfoABB(árbol)
SI (dato.clave < ele.clave) ENTONCES
InsertarABB(árbol^.izq, dato)

EN OTRO CASO


InsertarABB(árbol^.dch, dato)
FINSI
FINSI
FIN

Eliminacion:
La operacion de borrado es mas complicada, que las de busqueda e insercion.
Hay varios casos que tomar en cuenta:
*Borrar un nodo sin hijos o nodo hoja, solo se borra y se establece a nulo el apuntado de su padre.
*Borrar un nodo con un subarbol hijo: se borra elnodo y se asigna su subarbol hijo como subarbol su padre.*Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo.


Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho).


ya repasando entiendo un poco mejor.
esta informacion la encontre en : wikipedia// arboles binarios