Árboles

Ejemplo de octavos de final - árbol binario

¿Qué es un árbol?

Elementos de un árbol

Raíz: A
Hijo (descendiente directo): B,C
Padre (ascendiente directo): A, B
Hoja (nodo terminal): D, F, G, C
Nodo interior: B, E
Grado de un nodo: 2
Grado de un árbol: 2
Nivel de un nodo: A(1), B(2), E(3), F(4)
Altura (profundidad): 4

Árbol completo

Número medio de accesos que voy a tener que hacer es la altura (h)

Caminos de búsqueda. Interno y Externo

LCI: longitud de un camino interno

Árbol Binario. Árbol de grado 2

De grado 2 significa que tiene 2 hijos

Árbol Binario Completo

Si quito el 12 o el 19 ya no es completo
Si los quito a la vez sigue siendo completo

Árbol Binario lleno

Complejidad: log(nodos+1) (en base 2 porque el grado es 2, pero si el grado fuera más sería más)

Árbol binario degenerado

Árbol Binario de Búsqueda (ABB)

Implementación de un ABB

Estructura de datos para definir un nodo

Lo vamos a llamar BSTNode

public class BSTNode<T extends Comparable<T>>{
	private T info;
	private BSTNode<T> left;
	private aBSTNode<T> right;
}

Estructura de datos para definir un árbol

Lo vamos a llamar BSTree

public class BSTree<T extends Comparable<T>>{
	private BSTNode<T> source;//la raíz
}

Añadir un nodo al árbol

Ejercicios

1

La complejidad es esa porque depende de la altura del árbol y del número de nodos

2 Buscar un nodo en un árbol

//Tiene complejidad log(n) en base 2
public BSTNode<T> searchNode(BSTNode<T> node){
	if(this.source == null)
		return null;
	if(node.compareTo(this.source) == 0)
		return this.source;
 
	return searchNodeRecursive(this.source, node);
}
 
private BSTNode<T> searchNodeRecursive(BSTNode<T> source, BSTNode<T> target){
	if(source == null)
		return null;
	if(source.compareTo(target) < 0)
		return searchNodeRecursive(source.getLeft(), target);
	else if(source.compareTo(target) > 0)
		return searchNodeRecursive(source.getRight(), target);
	else
		return source;
}

Eliminar un nodo del árbol

Buscar el máximo

public T buscarMaximo(BSTNode node){
	if(node == null)
		return null;
	if(node.getRight() == null)
		return node.info;
	return buscarMaximo(node.getRight());
}

Recorridos

Recorridos. Ejercicios

public String preOrder() {
	String cadena = recorridoPreOrderRecursivo(this.raiz);
	return cadena.substring(0, cadena.length() - 1);
}
 
private String recorridoPreOrderRecursivo(BSTNode<T> nodoraiz) {
	if (nodoraiz == null)// si la raíz es nula devolverá la cadena vacía
		return "";
	String cadena = nodoraiz.getInfo().toString();
	cadena += "\t";
	cadena += recorridoPreOrderRecursivo(nodoraiz.getLeft());
	cadena += recorridoPreOrderRecursivo(nodoraiz.getRight());
	return cadena;
	}