Arboles - SergioRiosC/Datos-1 GitHub Wiki

Arboles Binarios

• Un arbol es una estructura de datos jerarquica, es decir, la forma en la que se conectan los objs permite identificar niveles de importancia
• Los arboles se componen de nodos cada nodo contiene un dato y una o mas referencias a otros nodos
• En un arbol binario, cada nodo tiene a lo sumo dos nodos
• Existen arboles N-arios, en los que los nodos pueden tener mas de dos nodos
• Un arbol binario de busqueda (BST) cumple la condicion:
  • El hijo derecho es mayor que la raiz
  • El hijo izquierdo es menor que la raiz
    *Estas condiciones se cumplen en cualquier parte del arbol
    Como se define un nodo en java?
    class Nodo{ int element; Nodo right; Nodo left; }
    Como se define el arbol?
    Class BST { Nodo root =null; boolean isEmpty(){ return root==null; }
    Como se busca en el arbol?
    boolean contains(int e){ return this.contains(e,root);
    }
    private boolean contains(int element, Nodo current){ if(current==null){ return false; }else if(element<current.element){ return contains(element, current.left); }else if(element>current.element){ return contains(element,current.right); }else{ return true; } } `
    Como encontrar el menor?

public Nodo findMin(){ return this.findMin(this.root); } private findMin(Nodo current){ if(current==null){ return null; }else if (current.left==null){ return current; }else{ return findMin(current.left); }}

Como se inserta en un arbol?
public void insert(int e){ root=this.insert(e,this.root); } private insert(int e, Nodo current){ if(current ==null){ return new Nodo(e); }else if(e<current.element){ current.left=insert(e, current.left); }else{ current.right=insert(e, current.right) } return current; }
Como se elimina el elemento?
hay 3 posibles escenarios

• el nodo por elimenar es una hoja:
  en este caso simpremente se "corta" la referencia
• Si el nodo por elimnar tiene un solo hijo:
  En este caso se "salta" el nodo por elininar y su hijpo lo reemplaza
• Si el nodo por eliminar tiene dos hijos:
  en este caso se busca el elemento menor en el subarbol derecho o el mayor en el subarbol izquierdo
  Se copia el elemento encontrado en el nodo por eliminar
  Se ejecuta el proceso de eliminar a partir de la posicion en la que se cpioel elemento que se encontro
  Nodo remove(int e, Nodo c){ if(c==null){ return null; }else if(e<c.value){ c.left=remove(e,c.left); }else if(c.left==null&&c.right!=null){ c.value=findMin(c.right); c.right=remove(c.value,c.right) }else{ c=c.left=null ? c.left:c.right} return c;}

---

Arboles AVL

• Uno de los supuestos de los arboles que proveen busquedas rapidas
• Dependiendo del orden de incersion se puede obtener un arbol como:
  0-0-0-0-0-0
  Que susede en este caso?
• Se pierde la rapidez para buscar y se resuelve a una busqueda secuencial
• AVL significa Adelson-Velski y Landis
• Es un arbol binario de busqueda con una condicion de balance para asegurar que la profundidad sea optima
• La altura a la izq no puede diferir en mas de 1 compuesto a la derecha

Como se insta en AVL?

• Igual que un BST
• Puede resultar en una violacion del balance
• En case sde violacion se aplica una rotacion

---

Arboles B

• Arboles n-arios
• Optimizados para estar almacenados en el disco
  -Los arboles vistos hasta el momento, asumen que esta en memoria completamente
• No es factible si hay muchos datos
• EL problema de tener una estrutura en disco es la latencia asociada a estos
• Los discos son sumamente lentos en comparacion a la memoria
• Los B-trees estan optimizados para no tener tantas operaciones en el disco
• Los B-trees reducen la profundidad del arbol
• Siempre esta balanceado
• Los nodos se llaman paginas
• A excepcion de la raiz, los nodos siempre estan medio llenos
• Un B-tree de orden m tiene las siguientes caracteristicas:
• -Todas las hojas estan en el mismo nivel
• -Todos los nodos tienen a lo sumo m ramas(y m-1 llaves)
• -Como minimo cada nodo (excepto la raiz) tienen al menos m/2 ramas

---

Arboles de expresion

• Una expresion es una secuencia de tokens (componentes lexicos que siguen una estructura especifica)
• Un arbol de expresion es un arbol binario con las siguientes propiedades
• -cada hoja es un operando
• -cada raiz son operadores
• -cada subarbol es una subexpresion
• Los compiladores usan arboles de expresion extensamente
• Para convertie un arbol a espresion, simplemente se debe recorrer el arbol con algunas de las siguientes formas
• -Infijo (hijo izq, raiz, hijo derecho)
• -Postfijo(Izquierdo,Derecho, raiz)
• -Prefijo( raiz, izquierdo, derecho)
  infijo(nodo){ if(nodo!=null){ if(nodo==operador){ print'('; } infijo(nodo izq) print nodo valor infijo(nodo derecho) if(nodo==operador){ print')' }}