Arboles

Árbol: estructura no lineal y dinámica de datos. Dinámica: puede cambiar durante la ejecución de un programa. No lineal: a cada elemento del árbol pueden seguirle varios elementos. Están formadospor un conjunto de nodos y un conjunto de aristas que conectan pares de nodos.
Operaciones básicas
 Insertar
 Buscar
 Eliminar
 Ir a la raíz
 Recorrer
Árboles binarios
Un árbol binario eso bien vacío o consta de una raíz, un hijo árbol binario izquierdo y otro derecho. Los árboles binarios de búsqueda permiten inserciones y acceso a los elementos en tiempo logarítmico. Los árbolesbinarios llamados colas con prioridad soportan acceso y eliminación del mínimo de una colección de elementos.
Operación “recorrer”
Los recorridos pueden ser en preorden, postorden o inorden (ordensimétrico). Todos son O(N).
public void preOrder(SList aList)
{
aList.addElement(value);
left.preOrder(aList);
right.preOrder(aList);
}
public void inOrder(SList aList)
{left.inOrder(aList);
aList.addElement(value);
right.inOrder(aList);
}
public void posOrder(SList aList)
{
left.posOrder(aList);
right.posOrder(aList);
aList.addElement(value);}
Árboles binarios perfectamente equilibrados
La eficiencia de las operaciones depende exclusivamente de la altura del árbol. Para un árbol de N nodos perfectamente equilibrado el coste de accesoes de orden logarítmico: O(log N). Sin embargo, se dice que si el árbol crece o decrece descontroladamente, el rendimiento puede disminuir considerablemente, siendo para el caso más desfavorable(insertar un conjunto de claves ordenadas en forma ascendente o descendente) el coste de acceso: O(N). En un árbol binario perfectamente equilibrado, el número de nodos en el subárbol izquierdo y elnúmero de nodos en el subárbol derecho, difieren como mucho en una unidad, y los subárboles son también equilibrados
[editar]Árboles equilibrados
Un procedimiento de inserción que siempre restaure la...