EL PRESENTE TRABAJO ESTA DEDICADO AL ANALISIS DE ALGORITMOS ASUMIENDO QUE SUS ENTRADAS ESTAN DISTRIBUIDAS
SEGUN EL MODELO PROBALISTICO BST O SEGUN EL MODELO EQUILIBRADO, QUE GENERALIZA AL ANTERIOR. EL CONJUNTO DE ENTRADAS DE TALES ALGORITMOS ES SIEMPRE ALGUNA FAMILIA DE ARBOLES SIMPLEMENTE GENERADOS. EN AMBOS MODELOS, DOS ARBOLES DEL MISMO TAMAÑO NO SON
NECESARIAMENTE EQUIPROBABLES; BIEN AL CONTRARIO, LOS ARBOLES MEJOR EQUILIBRADOS SON MAS PROBABLES QUE LOS POCO EQUILIBRADOS.
EL MODELO BST CORRESPONDE A LOS ARBOLES BINARIOS DE BUSQUEDA, Y TAMBIEN, A LOS ARBOLES K-D Y "HEAP ORDERED".
EL ANALISIS DEL COMPORTAMIENTO MEDIO DE ALGORITMOS PARA LOS MODELOS BST Y EQUILIBRADO CONDUCE EN MUCHOS CASOS, A ECUACIONES DIFERENCIALES ORDINARIAS Y EN DERIVADAS PARCIALES, MIENTRAS LOS CORRESPONDIENTES ANALISIS PARA ARBOLES UNIFORMEMENTE
DISTRIBUIDOS REQUIEREN LA RESOLUCION DE PROBLEMAS ALGEBRAICOS Y DE ENUMERACION COMBINATORIA. LA TESIS CONSTA DE CUATRO PARTES. LAS DOS PRIMERAS SE DEDICAN AL MATERIAL INTRODUCTORIO: CONCEPTOS BASICOS, DEFINICIONES Y LAS TECNICAS MATEMATICAS
(ALGEBRAICAS Y ANALITICAS) QUE SE USAN, TAMBIEN SE PRESENTA EN LA PARTE II UNA COLECCION DE MODELOS PROBABILISTICOS SOBRE ARBOLES, AMEN DEL MODELO BST Y DEL MODELO EQUILIBRADO. LA PARTE III CONSTITUYE LA PRINCIPAL CONTRIBUCION DE LA TESIS COMIENZA
CON UN CAPITULO EN EL QUE SE ANALIZA LA OCUPACION, UNA CARACTERISTICA RELACIONADA CON EL GRADO DE EQUILIBRIO DE LOS ARBOLES. SE ANALIZA DICHA CARACTERISTICA PARA DIVERSOS MODELOS DE PROBABILIDAD. EN EL SIGUIENTE CAPITULO, SE ABORDA LA DEFINICION DE
UN SISTEMA DE REGLAS ALGEBRAICAS QUE PERMITE LA TRADUCCION DE VARIAS ESPECIFICACIONES RECURSIVAS ALGORITMICAS A ECUACIONES MATEMATICAS QUE DESCRIBEN EL COMPORTAMIENTO MEDIO DE LOS ALGORITMOS QUE INVOLUCRAN DICHO TIPO DE CONSTRUCCIONES. EN EL
CAPITULO POSTERIOR SE EXAMINA UN ESQUEMA DE RECURSION SIMPLE, ASOCIADO A LO QUE DENOMINAMOS PROPIEDADES HEREDITARIAS.
DICHAS PROPIEDADES APARECEN EN DIVERSOS CONTEXTOS, Y DAN ORIGEN A PROBLEMAS MATEMATICOS ESTRUCTURALMENTE IDENTICOS. LOS CAPITULOS 7 Y 8 SE DEDICAN AL ANALISIS DEL TAMAÑO MEDIO DE LA INTERSECCION DE UN PAR DE ARBOLES Y AL ANALISIS DE LA
COMPLEJIDAD MEDIA DEL TEST DE IGUALDAD. EN AMBOS CASOS, EL PROBLEMA ORIGINAL SE REDUCE A UNO DE RESOLUCION DE UNA ECUACION EN DERIVADAS PARCIALES. EL USO DEL METODO DE RIEMANN Y LA APLICACION DE TECNICAS DEL ANALISIS ASINTOTICO PROPORCIONAN LOS
RESULTADOS DESEADOS.
EL TAMAÑO MEDIO DE LA INTERSECCION DE UN PAR DE ARBOLES DE TAMAÑO ES O(NO.8/RAIZ CUADRADA DE LOGN); LA COMPLEJIDAD DEL TEST DE IGUALDAD ES O(LOG N).