6.1 Definicin^Un rbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.Tambin se suele dar una definicin recursiva: un rbol es una estructura en compuesta por un dato y varios rboles.Esto son definiciones simples. Pero las caractersticas que implican no lo son tanto.

rbolDefiniremos varios conceptos. En relacin 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 trabajaremos tienen otra caracterstica importante: cada nodo slo puede ser apuntado por otro nodo, es decir, cada nodo slo tendr un padre. Esto hace que estos rboles estn fuertemente jerarquizados, y es lo que en realidad les da la apariencia de rboles.En cuanto a la posicin dentro del rbol: Nodo raz:nodo que no tiene padre. Este es el nodo que usaremos para referirnos al rbol. En el ejemplo, ese nodo es el 'A'. Nodo hoja:nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'. Nodo rama:aunque esta definicin apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categoras anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.Otra caracterstica que normalmente tendrn nuestros rboles es que todos los nodos contengan el mismo nmero de punteros, es decir, usaremos la misma estructura para todos los nodos del rbol. Esto hace que la estructura sea ms sencilla, y por lo tanto tambin los programas para trabajar con ellos.Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo.Un rbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llamarbol completo.En una cosa, los rboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raz de un rbol completo.Existen otros conceptos que definen las caractersticas del rbol, en relacin a su tamao: Orden: es el nmero potencial de hijos que puede tener cada elemento de rbol. De este modo, diremos que un rbol en el que cada nodo puede apuntar a otros dos es deorden dos, si puede apuntar a tres ser deorden tres, etc. Grado: el nmero de hijos que tiene el elemento con ms hijos dentro del rbol. En el rbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con ms de tres hijos. Nivel: se define para cada elemento del rbol como la distancia a la raz, medida en nodos. El nivel de la raz es cero y el de sus hijos uno. As sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3. Altura: la altura de un rbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un rbol puede considerarse a su vez como la raz de un rbol, tambin podemos hablar de altura de ramas. El rbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.Los rboles de orden dos son bastante especiales, de hecho les dedicaremos varios captulos. Estos rboles se conocen tambin comorboles binarios.Frecuentemente, aunque tampoco es estrictamente necesario, para hacer ms fcil moverse a travs del rbol, aadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en direccin a la raz, y no slo hacia las hojas.Es importante conservar siempre el nodorazya que es el nodo a partir del cual se desarrolla el rbol, si perdemos este nodo, perderemos el acceso a todo el rbol.El nodo tpico de un rbol difiere de los nodos que hemos visto hasta ahora para listas, aunque slo en el nmero de nodos. Veamos un ejemplo de nodo para crear rboles de orden tres:struct nodo { int dato; struct nodo *rama1; struct nodo *rama2; struct nodo *rama3;};O generalizando ms:#define ORDEN 5

struct nodo { int dato; struct nodo *rama[ORDEN];};6.2 Declaraciones de tipos para manejar rboles en C^Para C, y basndonos en la declaracin de nodo que hemos visto ms arriba, trabajaremos con los siguientes tipos:typedef struct _nodo { int dato; struct _nodo *rama[ORDEN];} tipoNodo; typedef tipoNodo *pNodo;typedef tipoNodo *Arbol;Al igual que hicimos con las listas que hemos visto hasta ahora, declaramos un tipotipoNodopara declarar nodos, y un tipopNodopara es el tipo para declarar punteros a un nodo.Arboles el tipo para declarar rboles de ordenORDEN.

rbolEl movimiento a travs de rboles, salvo que implementemos punteros al nodo padre, ser siempre partiendo del nodo raz hacia un nodo hoja. Cada vez que lleguemos a un nuevo nodo podremos optar por cualquiera de los nodos a los que apunta para avanzar al siguiente nodo.En general, intentaremos que exista algn significado asociado a cada uno de los punteros dentro de cada nodo, los rboles que estamos viendo son abstractos, pero las aplicaciones no tienen por qu serlo. Un ejemplo de estructura en rbol es el sistema de directorios y ficheros de un sistema operativo. Aunque en este caso se trata de rboles con nodos de dos tipos, nodos directotio y nodos fichero, podramos considerar que los nodos hoja son ficheros y los nodos rama son directorios.Otro ejemplo podra ser la tabla de contenido de un libro, por ejemplo de este mismo curso, dividido en captulos, y cada uno de ellos en subcaptulos. Aunque el libro sea algo lineal, como una lista, en el que cada captulo sigue al anterior, tambin es posible acceder a cualquier punto de l a travs de la tabla de contenido.Tambin se suelen organizar en forma de rbol los organigramas de mando en empresas o en el ejrcito, y los rboles genealgicos.rbolesAntes de comenzar a trabajar sobre rboles es importante estudiarrecursividad

Contenidos

1. 1Introduccin2. 2Visin Recursiva3. 3Ejemplo de un rbol en python4. 4Recorridos1. 4.1Profundidad Primero2. 4.2Ancho Primero5. 5Cdigo fuenteIntroduccinAlgunas definiciones: Un rbol es unaestructura de datos enlazadaque organiza elementosen forma jerrquica. Es decir, hay una relacin padre/hijos. Cada nodo puede tener ms de un hijo, peroun solo padre. Existe un nodo que no tiene padre denominadoraiz. Los nodos que no tienen hijos se denominanhojas Un rbol es deorden N(o N-ario) cuando la mxima cantidad de hijos que puede tener un nodo es N. Laprofundidadde un rbol es ladistancia(saltos entre nodos)desde la raiz hasta la hoja ms lejana.

Visin RecursivaCada rama de un rbol puede ser visto como un sub-rbol. De esta forma, el rbol genealgico de la abuela Bouvier est compuesto por el rbol de Marge, el de Patty y el de Selma. Esto repercute en el estilo de programacin: todas las funciones que recorren o modifican el rbol hacen uso de caractersticas recursivas. Esto significa que a veces el trmino nodo y rbol se usan indistintamente, lo cual puede causar confusin al desprevenido.Ejemplo de un rbol en pythondefinicinHaciendo uso de la nocin recursiva de un rbol, podemos definir un rbol como la unin de un elemento y sus ramas.classArbol: def__init__(self, elemento): self.hijos = [] self.elemento = elemento

agregar elementosUna forma de agregar elementos podra ser:abuela = "Jacqueline Gurney"marge = "Marge Bouvier"patty = "Patty Bouvier"selma = "Selma Bouvier"bart = "Bart Simpson"lisa = "Lisa Simpson"maggie = "Maggie Simpson"ling = "Ling Bouvier"

arbol = Arbol(abuela)agregarElemento(arbol, patty, abuela)agregarElemento(arbol, selma, abuela)agregarElemento(arbol, ling, selma)agregarElemento(arbol, marge, abuela)agregarElemento(arbol, bart, marge)agregarElemento(arbol, lisa, marge)agregarElemento(arbol, maggie, marge)

Para lo cual necesitamos escribir el mtodo agregarElemento que recibe el rbol, el elemento a agregar, y el padre de dicho elemento. Este mtodo obtiene el sub-rbol que contiene al elemento padre y le agrega una nueva rama (rbol) con el nuevo elemento.Es importante entender que la bsqueda del sub-rbol debe ser recursiva. La condicin de corte es si el elemento est en el rbol actual, si no se busca en cada uno de los hijos.

defagregarElemento(arbol, elemento, elementoPadre): subarbol = buscarSubarbol(arbol, elementoPadre); subarbol.hijos.append(Arbol(elemento))

defbuscarSubarbol(arbol, elemento): ifarbol.elemento == elemento: returnarbol forsubarbolinarbol.hijos: arbolBuscado = buscarSubarbol(subarbol, elemento) if(arbolBuscado != None): returnarbolBuscado return None

Profundidad y grado La profundidad de un rbol es 1 + la profundidad del hijo ms profundo El grado es el maximo entre la cantidad de sus hijos directos y el grado de sus hijosdefprofundidad(arbol): iflen(arbol.hijos) == 0: return1 return1 + max(map(profundidad,arbol.hijos))

defgrado(arbol): returnmax(map(grado, arbol.hijos) + [len(arbol.hijos)])

RecorridosRecorrer un rbol significa comenzar avisitar a cada uno de los elementos(tanto al elemento de la raiz como a los elementos de sus descendientes). A veces se realiza porque se quiere ejecutar algo por cada uno u otras veces es porque se est buscando uno en particular.Existen dos maneras de recorrer un rbol: profundidad primero y ancho primero.

Profundidad PrimeroEsta forma es la ms sencilla: consiste enexplorar toda una rama antes de pasar a la siguiente. Es decir, hasta no terminar de recorrer toda la rama de marge, no iniciar con Patty.Ac un diagrama que muestra el rden de recorrido sobre un rbol:

En el mtodo que vimos anteriormente debuscarSubArbolestamos usando esta estrategia para encontrar el elemento. A continuacin un ejemplo de una funcin de orden superior que ejecuta sobre cada elemento del rbol:defejecutarProfundidadPrimero(arbol, funcion): funcion(arbol.elemento) forhijoinarbol.hijos: ejecutarProfundidadPrimero(hijo, funcion)

Al utilizarlo con una funcin que imprime un elemento :defprintElement(element): printelementejecutarProfundidadPrimero(arbol, printElement)

podemos ver el siguiente resultado:Jacqueline GurneyPatty BouvierSelma BouvierLing BouvierMarge BouvierBart SimpsonLisa SimpsonMaggie Simpson

Ancho PrimeroEsta forma es un poco ms compleja pero puede ser conveniente dependiendo del problema. En nuestro ejemplo ir recorriendo generacin a generacin: Primero la abuela, luego todas las hijas, y luego todos los nietos.Ac otro diagrama a modo esquemtico:

Para poder resolver este algoritmo, es necesario retrasar la ejecucin de la funcin sobre los hijos hasta que no se haya terminado de ejecutar todos los hermanos/primos. Por eso se usa una cola (Primero que entra, Primero que sale) para lograr esto. Cuando se visita a un nodo, ejecuta la funcin, agrega sus hijos a la cola, y luego llama a la funcin recursiva pero en lugar de hacerlo sobre algn hijo suyo (como haca profundidad primero) lo hace sobre el prximo de la cola, que seguramente es un alguien de su nivel si an quedan o el primero del prximo nivel.defejecutarAnchoPrimero(arbol, funcion, cola = deque()): funcion(arbol.elemento) if(len(arbol.hijos) > 0): cola.extend(arbol.hijos) if(len(cola) != 0): ejecutarAnchoPrimero(cola.popleft(), funcion, cola) Se usa de la siguiente manera:defprintElement(element):printelement

ejecutarAnchoPrimero(arbol, printElement)

Veamos paso a paso que ocurre:

Invocacin:1Elemento: JackelineConsolaCola

Jacqueline GurneyPatty BouvierSelma BouvierMarge Bouvier

Invocacin:2Elemento: PattyNo tiene hijos, por lo tanto no agrega elementos a la colaConsolaCola

Jacqueline GurneyPatty BouvierSelma BouvierMarge Bouvier

Invocacin:3Elemento: SelmaAgrega a Ling a la colaConsolaCola

Jacqueline GurneyPatty BouvierSelma BouvierMarge BouvierLing Bouvier

Invocacin:4Elemento: MargeAgrega a Bart, Lisa y MaggieConsolaCola

Jacqueline GurneyPatty BouvierSelma BouvierMarge BouvierLing BouvierBart SimpsonLisa SimpsonMaggie Simpson

Invocacin:5Elemento: LingConsolaCola

Jacqueline GurneyPatty BouvierSelma BouvierMarge BouvierLing BouvierBart SimpsonLisa SimpsonMaggie Simpson

Invocacin:6Elemento: BartConsolaCola

Jacqueline GurneyPatty BouvierSelma BouvierMarge BouvierLing BouvierBart SimpsonLisa SimpsonMaggie Simpson

Invocacin:7Elemento: LisaConsolaCola

Jacqueline GurneyPatty BouvierSelma BouvierMarge BouvierLing BouvierBart SimpsonLisa SimpsonMaggie Simpson

Invocacin:8Elemento: MaggieConsolaCola

Jacqueline GurneyPatty BouvierSelma BouvierMarge BouvierLing BouvierBart SimpsonLisa SimpsonMaggie Simpson

from _2_arboles import *

def printElement(element): print element

abuela = "Jacqueline Gurney"marge = "Marge Bouvier"patty = "Patty Bouvier"selma = "Selma Bouvier"bart = "Bart Simpson"lisa = "Lisa Simpson"maggie = "Maggie Simpson"ling = "Ling Bouvier"

arbol = Arbol(abuela)agregarElemento(arbol, patty, abuela)agregarElemento(arbol, selma, abuela)agregarElemento(arbol, ling, selma)agregarElemento(arbol, marge, abuela)agregarElemento(arbol, bart, marge)agregarElemento(arbol, lisa, marge)agregarElemento(arbol, maggie, marge)

print profundidad(arbol)print grado(arbol)

## PROFUNDIDAD#

ejecutarProfundidadPrimero(arbol, printElement)

## ANCHO#

ejecutarAnchoPrimero(arbol, printElement)

otrafrom collections import deque

class Arbol: def __init__(self, elemento): self.elemento = elemento self.hijos = []

def agregarElemento(arbol, elemento, elementoPadre): subarbol = buscarSubarbol(arbol, elementoPadre); subarbol.hijos.append(Arbol(elemento))

def buscarSubarbol(arbol, elemento): if arbol.elemento == elemento: return arbol for subarbol in arbol.hijos: encontrado = buscarSubarbol(subarbol, elemento) if encontrado != None: return encontrado return None # Exceptions

def profundidad(arbol): if len(arbol.hijos) == 0: return 1 profundidades = map(profundidad, arbol.hijos) return 1 + max(profundidades)

def grado(arbol): return max(map(grado, arbol.hijos) + [len(arbol.hijos)])

## RECORRIDOS#

def ejecutarProfundidadPrimero(arbol, funcion): funcion(arbol.elemento) for hijo in arbol.hijos: ejecutarProfundidadPrimero(hijo, funcion)

def ejecutarAnchoPrimero(arbol, funcion, cola = deque()): funcion(arbol.elemento) if (len(arbol.hijos) > 0): cola.extend(arbol.hijos) if (len(cola) != 0): ejecutarAnchoPrimero(cola.popleft(), funcion, cola)from collections import deque

class Arbol: def __init__(self, elemento): self.elemento = elemento self.hijos = []

def agregarElemento(arbol, elemento, elementoPadre): subarbol = buscarSubarbol(arbol, elementoPadre); subarbol.hijos.append(Arbol(elemento))

def buscarSubarbol(arbol, elemento): if arbol.elemento == elemento: return arbol for subarbol in arbol.hijos: encontrado = buscarSubarbol(subarbol, elemento) if encontrado != None: return encontrado return None # Exceptions

def profundidad(arbol): if len(arbol.hijos) == 0: return 1 profundidades = map(profundidad, arbol.hijos) return 1 + max(profundidades)

def grado(arbol): return max(map(grado, arbol.hijos) + [len(arbol.hijos)])

## RECORRIDOS#

def ejecutarProfundidadPrimero(arbol, funcion): funcion(arbol.elemento) for hijo in arbol.hijos: ejecutarProfundidadPrimero(hijo, funcion)

def ejecutarAnchoPrimero(arbol, funcion, cola = deque()): funcion(arbol.elemento) if (len(arbol.hijos) > 0): cola.extend(arbol.hijos) if (len(cola) != 0): ejecutarAnchoPrimero(cola.popleft(), funcion, cola)

rbol binario de bsquedaUnrbol binario de bsquedatambin llamados BST (acrnimo delinglsBinarySearchTree) es un tipo particular derbol binarioque presenta unaestructura de datosen forma derbolusada eninformtica.ndice[ocultar] 1Descripcin 2Implementacin en Python 3Operaciones 3.1Bsqueda 3.2Insercin 3.3Borrado 3.4Otras Operaciones 3.5Recorridos 4Tipos de rboles binarios de bsqueda 5Comparacin de rendimiento 6Buscando el rbol binario de bsqueda ptimo 7Vase tambin 8Referencias 9Enlaces externosDescripcin[editar]Un rbol binario de bsqueda (ABB) es unrbol binariodefinido de la siguiente forma:

rbol binariola mayora de los rboles binarios son de bsquedaUn rbol binario no vaco, de raz R, es un rbol binario de bsqueda si: En caso de tener subrbol izquierdo, la raz R debe ser mayor que el valor mximo almacenado en el subrbol izquierdo, y que el subrbol izquierdo sea un rbol binario de bsqueda. En caso de tener subrbol derecho, la raz R debe ser menor que el valor mnimo almacenado en el subrbol derecho, y que el subrbol derecho sea un rbol binario de bsqueda.

Un rbol binario de bsqueda de tamao 9 y profundidad 3, con raz 8 y hojas 1, 4, 7 y 13Para una fcil comprensin queda resumido en que es un rbol binario que cumple que el subrbol izquierdo de cualquier nodo (si no est vaco) contiene valores menores que el que contiene dicho nodo, y el subrbol derecho (si no est vaco) contiene valores mayores.Para estas definiciones se considera que hay una relacin de orden establecida entre los elementos de los nodos. Que cierta relacin est definida, o no, depende de cadalenguaje de programacin. De aqu se deduce que puede haber distintos rboles binarios de bsqueda para un mismo conjunto de elementos.La altura h en el peor de los casos es siempre el mismo tamao que el nmero de elementos disponibles. Y en el mejor de los casos viene dada por la expresin, donde ceil indica redondeo por exceso.El inters de los rboles binarios de bsqueda (ABB) radica en que surecorrido en inordenproporciona los elementos ordenados de forma ascendente y en que la bsqueda de algn elemento suele ser muy eficiente.Dependiendo de las necesidades del usuario que trate con una estructura de este tipo, se podr permitir la igualdad estricta en alguno, en ninguno o en ambos de los subrboles que penden de la raz. Permitir el uso de la igualdad provoca la aparicin de valores dobles y hace la bsqueda ms compleja.Un rbol binario de bsqueda no deja de ser un caso particular de rbol binario, as usando la siguiente especificacin de rbol binario enmaude: fmod ARBOL-BINARIO {X :: TRIV}is sorts ArbolBinNV{X} ArbolBin{X} . subsort ArbolBinNV{X} < ArbolBin{X} . *** generadores op crear : -> ArbolBin{X} [ctor] . op arbolBin : X$Elt ArbolBin{X} ArbolBin{X} -> ArbolBinNV{X} [ctor] . endfmpodemos hacer la siguiente definicin para un rbol binario de bsqueda (tambin en maude): fmod ARBOL-BINARIO-BUSQUEDA {X :: ORDEN} is protecting ARBOL-BINARIO{VOrden}{X} . sorts ABB{X} ABBNV{X} . subsort ABBNV{X} < ABB{X} . subsort ABB{X} < ArbolBin{VOrden}{X} . subsort ABBNV{X} < ArbolBinNV{VOrden}{X} . *** generadores op crear : -> ArbolBin{X} [ctor] . op arbolBin : X$Elt ArbolBin{X} ArbolBin{X} -> ArbolBinNV{X} [ctor] . endfmcon la siguienteteoradeorden: fth ORDEN is protecting BOOL . sort Elt . *** operaciones op _ Bool . endfthpara que un rbol binario pertenezca al tipo rbol binario de bsqueda debe cumplir la condicin de ordenacin siguiente que ira junto al mdulo ARBOL-BINARIO-BUSQUEDA: var R : X$Elt . vars INV DNV : ABBNV{X} . vars I D : ABB{X} . mb crear : ABB{X} . mb arbolBin(R, crear, crear) : ABBNV{X} . cmb arbolBin(R, INV, crear) : ABBNV{X} if R > max(INV) . cmb arbolBin(R, crear, DNV) : ABBNV{X} if R < min(DNV) . cmb arbolBin(R, INV, DNV) : ABBNV{X} if (R > max(INV)) and (R < min(DNV)) . ops min max : ABBNV{X} -> X$Elt . eq min(arbolBin(R, crear, D)) = R . eq min(arbolBin(R, INV, D)) = min(INV) . eq max(arbolBin(R, I, crear)) = R . eq max(arbolBin(R, I, DNV)) = max(DNV) .Implementacin en Python[editar]class nodo: izq , der, dato = None, None, 0 def __init__(self, dato): # crea un nodo self.izq = None self.der = None self.dato = datoclass arbolBinario: def __init__(self): # inicializa la raiz self.raiz = None def agregarNodo(self, dato): # crea un nuevo nodo y lo devuelve return nodo(dato) def insertar(self, raiz, dato): # inserta un dato nuevo en el rbol if raiz == None: # si no hay nodos en el rbol lo agrega return self.agregarNodo(dato) else: # si hay nodos en el rbol lo recorre if dato k!=k) ) { if (k < p->k) { p=p->l; } if (p->k < k) { p=p->r; } } if (!estaVacio(p) &&(p->d!=NULL) ) { e=copiaDato(p->d); } } return e;}Vase ahora la versin recursiva en ese mismo lenguaje:int buscar(tArbol *a, int elem){ if (a == NULL) { return 0; } else if (a->clave < elem) { return buscar(a->hDerecho, elem); } else if (a->clave > elem) { return buscar(a->hIzquierdo, elem); } else { return 1; }}Otro ejemplo enPython:def buscar(raiz, clave):# busca el valor clave dentro del arbolif raiz == None: print 'No se encuentra'else: # if clave == raiz.dato:print 'El valor ',clave,' se encuentra en el ABB' elif clave < raiz.dato: # lado izquierdoreturn buscar(raiz.izq, clave) else:# lado derechoreturn buscar(raiz.der, clave)EnPascal:Function busqueda(T:ABR, y: integer):ABRbegin if (T=nil) or (^T.raiz=y) then busqueda:=T; else if (^T.raiz Bool . var R R1 R2 : X$Elt . vars I D : ABB{X} . eq esta?(R, crear) = false . eq esta?(R1, arbolBin(R2, I, D)) = if R1 == R2 then true else if R1 < R2 then esta?(R1, I) else esta?(R1, D) fi fi .Insercin[editar]La insercin es similar a la bsqueda y se puede dar una solucin tanto iterativa como recursiva. Si tenemos inicialmente comoparmetroun rbol vaco se crea un nuevo nodo como nico contenido el elemento a insertar. Si no lo est, se comprueba si el elemento dado es menor que la raz del rbol inicial con lo que se inserta en el subrbol izquierdo y si es mayor se inserta en el subrbol derecho.

Evolucin de la insercin del elemento "5" en un ABB.Como en el caso de la bsqueda puede haber varias variantes a la hora de implementar la insercin en el TAD (Tipo Abstracto de Datos), y es la decisin a tomar cuando el elemento (o clave del elemento) a insertar ya se encuentra en el rbol, puede que ste sea modificado o que sea ignorada la insercin. Es obvio que esta operacin modifica el ABB perdiendo la versin anterior del mismo.A continuacin se muestran las dos versiones del algoritmo enpseudolenguaje, iterativa y recursiva, respectivamente.PROC InsertarABB(rbol:TABB; dato:TElemento)VARIABLES nuevonodo,pav,pret:TABB clavenueva:Tclave ele:TElementoINICIO nuevonodo hIzquierdo, &aux); free(aux); }} void reemplazar(tArbol **a, tArbol **aux){ if ((*a)->hDerecho == NULL) { (*aux)->clave = (*a)->clave; *aux = *a; *a = (*a)->hIzquierdo; } else reemplazar(&(*a)->hDerecho, & aux);}Otro ejemplo enPascal.Procedure Borrar(var T:ABR, x:ABR)var aBorrar:ABR; anterior:ABR; actual:ABR; hijo:ABR;begin if (^x.izq=nil) or (^x.dch=nil) then aBorrar:=x; else aBorrar:=sucesor(T,x); actual:=T; anterior:=nil; while (actualaBorrar) do begin anterior:=actual; if (^actual.raiz X$Elt . eq min(arbolBin(R, crear, D)) = R . eq max(arbolBin(R, I, crear)) = R . eq min(arbolBin(R, INV, D)) = min(INV) . eq max(arbolBin(R, I, DNV )) = max(DNV) . eq eliminar(M, crear) = crear . ceq eliminar(M, arbolBin(R, crear, D)) = D if M == clave(R) . ceq eliminar(M, arbolBin(R, I, crear)) = I if M == clave(R) . ceq eliminar(M, arbolBin(R, INV, DNV)) = arbolBin(max(INV), eliminar(clave(max(INV)), INV), DNV) if M == clave(R) . ceq eliminar(M, arbolBin(R, I, D)) = arbolBin(R, eliminar(M, I), D) if M < clave(R) . ceq eliminar(M, arbolBin(R, I, D)) = arbolBin(R, I, eliminar(M, D)) if clave(R) < M .Otras Operaciones[editar]Otra operacin sera por ejemplo comprobar que un rbol binario es un rbol binario de bsqueda. Su implementacin en maude es la siguiente: op esABB? : ABB{X} -> Bool . var R : X$Elt . vars I D : ABB{X} . eq esABB?(crear) = true . eq esABB?(arbolbBin(R, I, D)) = (Max(I) < R) and (Min(D) > R) and (esABB?(I)) and (esABB?(D)) .Recorridos[editar]Se puede hacer un recorrido de un rbol en profundidad o en anchura.Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raz a todos los hijos antes de pasar a la descendencia de alguno de los hijos.El coste de recorrer el ABB es O(n), ya que se necesitan visitar todos los vrtices.El recorrido en profundidad lleva al camino desde la raz hacia el descendiente ms lejano del primer hijo y luego contina con el siguiente hijo. Como recorridos en profundidad tenemosinorden,preordenypostorden.Una propiedad de los ABB es que al hacer un recorrido en profundidad inorden obtenemos los elementos ordenados de forma ascendente.

Ejemplo rbol binario de bsquedaResultado de hacer el recorrido en:Inorden= [6, 9, 13, 14, 15, 17, 20, 26, 64, 72].Preorden= [15, 9, 6, 14, 13, 20, 17, 64, 26, 72].Postorden=[6, 13, 14, 9, 17, 26, 72, 64, 20, 15].

Recorridos en Visual Basic .Net'funcin de recorrido en PREORDEN Public Function preorden() As String cadenasalida = "" rePreorden(raz) Return cadenasalida End Function Private Sub rePreorden(ByVal padre As Nodo) If IsNothing(padre) Then Return End If cadenasalida = cadenasalida & "-" & padre.dato rePreorden(padre.ant) rePreorden(padre.sig) End Sub 'funcin de recorrido en POSTORDEN Public Function postorden() As String cadenasalida = "" reposorden(raz) Return cadenasalida End Function Private Sub repostorden(ByVal padre As Nodo) If IsNothing(padre) Then Return End If repostorden(padre.ant) repostorden(padre.sig) cadenasalida = cadenasalida & "-" & padre.dato End Sub 'funcin de recorrido en ENORDEN Public Function inorden() As String cadenasalida = "" reinorden(raz) Return cadenasalida End Function Private Sub reinorden(ByVal padre As Nodo) If IsNothing(padre) Then Return End If reinorden(padre.ant) cadenasalida = cadenasalida & "-" & padre.dato reinorden(padre.sig) End Sub

Recorridos enCcon funciones recursivasstruct Nodo{ char nombre[30]; struct Nodo *izq; struct Nodo *der;}; typedef struct Nodo Nodo;typedef Nodo *Arbol; void preOrden(Arbol abb){ if(abb) { printf("%s\n", abb->nombre); preOrden(abb->izq); preOrden(abb->der); }} void postOrden(Arbol abb){ if(abb) { postOrden(abb->izq); postOrden(abb->der); printf("%s\n", abb->nombre); }} void inOrden(Arbol abb){ if(abb) { inOrden(abb->izq); printf("%s\n", abb->nombre); inOrden(abb->der); }}Tipos de rboles binarios de bsqueda[editar]Hay varios tipos de rboles binarios de bsqueda. Losrboles AVL,rbol rojo-negro, son rboles autobalanceables . Losrbol biseladoson rboles tambin autobalanceables con la propiedad de que los elementos accedidos recientemente se acceder ms rpido en posteriores accesos. En elmontculocomo en todos los rboles binarios de bsqueda cada nodo padre tiene un valor mayor que sus hijos y adems es completo, esto es cuando todos los niveles estn llenos con excepcin del ltimo que puede no estarlo, por ltimo, en lo montculos, cada nodo mantiene una prioridad y siempre, un nodo padre tendr una prioridad mayor a la de su hijo.Otras dos maneras de configurar un rbol binario de bsqueda podra ser como un rbol completo o degenerado.Un rbol completo es un rbol con "n" niveles, donde cada nivel d sig;aux->sig=nuevo;

}}void mostrar(){nodo *aux; //Aux es un apuntadoraux=cab; //En esta line aux toma la direccion de cabwhile(aux!=NULL){printf("%d, ",aux->valor);aux=aux->sig;}}void BorrarTodo(void){nodo *aux;aux=cab;while(aux!=NULL){cab=aux->sig;delete aux;aux=cab;}}

void Eliminar(int num) {nodo *aux,*aux2, *prev;int c=0;aux=cab;

while(c!=1){if(aux->valor==num){c=1;}else{prev=aux;aux=aux->sig;}}

if(c==1){if(prev->sig==NULL){cab=cab->sig;delete aux;}else{aux2 = aux->sig;prev->sig = aux2;delete aux;}}

}

void insertord(int num) {nodo *aux,*nuevo,*aux2,*prev;int c=0;aux2=cab;nuevo=new nodo;// nuevo->valor=num;while(aux2!=NULL){if(aux2->valor>=num){

prev->sig=nuevo;nuevo->valor=num;nuevo->sig=aux2;cab=prev;aux2=NULL;c=1;}prev=aux2;aux2=aux2->sig;}if(aux2==NULL)if(c==0){insertar(num);}else{delete aux2;}}Eliminacin[editar]Se busca el nodo hoja correspondiente y se elimina la clave. Si al eliminar una clave, n queda menor a (M/2 -1), entonces debe realizarse una redistribucin de claves, tanto en el ndice como en las pginas hojas.1. include2. include3. include4. include5. includestruct nodo {int valor;struct nodo*sig;}*cab; void insertar(int num); void mostrar(void); void BorrarTodo(void); void Eliminar(int num); void insertord(int num);

void main (void) { int op, num; cab=NULL;while(1){clrscr();printf("1.-Insertar un nodo.\n2.-Eliminar un nodo.\n3.-Mostrar\n4.-Insettar nodos en orden\n0.-Salir\n");printf("\nElige una opcion: ");scanf("%d",&op);switch(op){case 1:printf("Valor del nodo que deseas insertar: ");scanf("%d",&num);insertar(num);break;case 2:printf("Dame el valor del nodo a eliminar: ");scanf("%d",&num);Eliminar(num);break;case 3:mostrar();break;case 4:printf("Valor del nodo que deseas insertar: ");scanf("%d",&num);insertord(num);break;case 0:BorrarTodo();exit(0);//para usar exit debes declarar stdlib.hbreak;default:printf("ERROR Opcion incorrecta");getch();

}getch();}} void insertar(int num) {nodo *aux,*nuevo;aux=cab;nuevo=new nodo;nuevo->valor=num;nuevo->sig=NULL;if(cab==NULL)cab=nuevo;

else{while(aux->sig!=NULL)aux=aux->sig;aux->sig=nuevo;

}}void mostrar(){nodo *aux; //Aux es un apuntadoraux=cab; //En esta line aux toma la direccion de cabwhile(aux!=NULL){printf("%d, ",aux->valor);aux=aux->sig;}}void BorrarTodo(void){nodo *aux;aux=cab;while(aux!=NULL){cab=aux->sig;delete aux;aux=cab;}}

void Eliminar(int num) {nodo *aux,*aux2, *prev;int c=0;aux=cab;

while(c!=1){if(aux->valor==num){c=1;}else{prev=aux;aux=aux->sig;}}

if(c==1){if(prev->sig==NULL){cab=cab->sig;delete aux;}else{aux2 = aux->sig;prev->sig = aux2;delete aux;}}

}

void insertord(int num) {nodo *aux,*nuevo,*aux2,*prev;int c=0;aux2=cab;nuevo=new nodo;// nuevo->valor=num;while(aux2!=NULL){if(aux2->valor>=num){

prev->sig=nuevo;nuevo->valor=num;nuevo->sig=aux2;cab=prev;aux2=NULL;c=1;}prev=aux2;aux2=aux2->sig;}if(aux2==NULL)if(c==0){insertar(num);}else{delete aux2;}}Categ