Clase 20

Delete de arbol binario de busqueda

Considerar posibilidades dependiendo de posicion

Nodo es hoja, solo se borra, su padre apunta a null

• Nodo con 1 hijo, padre de eliminado, toma su hijo
• Nodo con 2 hijos, Agarrar menor de la derecha, agarrar el mayor del izq, reemplazar la data,repetir procedure,0

Factor de Balance =altura del subarbol derecho- altura de subarbol izquierdo

Insertar

Usar ROtacion para con dicion de balanceo Solo los de la ruta, su factor de balanceo son afectados

Arboles AVL

la complejidad del arbol AVL es de O(logN), la diferencia de la profundidad de los subarboles de la raiz debe de ser maximo 1. El arbol AVL NO puede poseer subarboles NO AVL

*Factor de balanceo *= altura de subarbol derecho menos altura de subarbol izquierdo

Si al insertar se incumple la condicion de balanceo de AVL se hace una rotacion. Para saber si se afecto se debe ver si se afecto el valor de balanceo de los nodos de la ruta por la cual se paso

Metodos de rotación

• en los left left o right right, se les aplica una rotacion sencilla

• en los left right o right left, se les aplica una rotacion doble