Arboles

Árboles Perfectamente Balanceados

Es aquel en el que para cada nodo en sus subárboles derecho e izquierdo difieren como máximo en 1.

Si conocemos los nodos (teórico):

Si no tenemos ni idea de la colocación de los nodos; se colocan de derecha a izquierda.

Árboles Binarios Ordenados según el Recorrido
Es aquel que para cada nodo se visita el nodo, su subárbol izquierdo y derecho en un orden establecido.

• Preorden: Visitar nodo antes que los subárboles.
• En orden: Visitar nodo después de un subárbol y antes que otro.
• Postorden: Visitar nodo después de los subárboles.

Árboles de Búsqueda Binarios
Es un árbol binario en el que dadas dos condiciones mutuamente excluyentes para cada nodo, todas las llaves de su subárbol izquierdo satisfacen una condición y todas las de su subárbol derecho la otra.

• Inserción: Se consulta si el dato es mayor o menor que la llave, decidiendo así si se prosigue la búsqueda por la izquierda o por la derecha. El procedimiento termina cuando se alcanza el puntero NIL, ya que esto querrá decir que el elemento no se ha encontrado y hay que insertarlo.
• Eliminación: Sustituir el nodo eliminado por el mayor menor, o sustituir el nodo eliminado por el menor mayor.

Árboles de Búsqueda Balanceados (AVL)
Todos los árboles perfectamente balanceados son AVL.

El árbol AVL cumple que en cada nodo las alturas de sus 2 subárboles difieren como máximo en 1

• Inserción en árboles AVL: Al insertar un nuevo nodo, hay que tener en cuenta el rebalanceo RR, RL, LR, LL
• Eliminación en árboles AVL: Se eliminan igual que los arboles binarios, pero con una diferencia, tenemos que hacer rebalanceo.