Arboles

Operaciones de árboles. Representación


Las rotaciones en árboles binarios son operaciones internas comunes utilizadas para mantener el balance perfecto (o casi perfecto) del árbol binario. Unárbol balanceado permite operaciones en tiempo logarítmico.
Las operaciones comunes en árboles son:
• Enumerar todos los elementos.
• Buscar un elemento.
• Dado un nodo, listar los hijos (si loshay).
• Borrar un elemento.
• Eliminar un subárbol (algunas veces llamada podar).
• Añadir un subárbol (algunas veces llamada injertar).
• Encontrar la raíz de cualquier nodo.
Por su parte, larepresentación puede realizarse de diferentes formas. Las más utilizadas son:
• Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.
• Representar el árbol con unarray donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array
Ejemplo de un árbol binario


Definición
Un árbol es una estructura no lineal enla que cada nodo puede apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.
Esto son definicionessimples. Pero las características que implican no lo son tanto.

Definiremos varios conceptos. En relación con otros nodos:
• Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol.En el ejemplo, 'L' y 'M' son hijos de 'G'.
• Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.
Los árboles con los que trabajaremostienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo queen realidad les da la apariencia de árboles.
En cuanto a la posición dentro del árbol:
• Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo,...