REPRESENTACIÓN EN ARREGLOS NUMÉRICOS DE ÁRBOLES BINARIOS COMPLETOS

Resumen

Los árboles binarios completos (PBT, por sus siglas en inglés planar binary trees) es una subclase de grafos simples en la cual, cada vértice tiene al menos uno y a lo más tres lados incidentes, con un único vértice con dos lados incidentes. Cada vértice con tres lados incidentes se llama padre. El padre principal o raíz es aquel que posee dos lados incidentes. Finalmente, los vértices con un sólo lado incidente se denominan hojas y a todos los lados se les llama rama. Expuesto lo anterior, conviene, en la representación gráfica de los PBT, no tomar en cuenta el isomorfismo entre ellos cuando su única diferencia es la rotación de 180° con respecto a la raíz. Así, se demuestra que existe una equivalencia entre el conjunto de los PBT de n padres y el conjunto de Catalan Y_n. Los PBT, aparte de su representación gráfica, también poseen una representación en arreglos numéricos, basada en la notación Permutation-like de PBT, en la cual la cantidad de padre es importante para determinar el arreglo; i.e., la permutación de un PBT. Para precisar dicha representación, en el presente trabajo se desarrollaron algoritmos para la conversión de los PBT en arreglos numéricos, aportando mayor fiabilidad al uso de la mencionada representación. Por último, se desarrolló un algoritmo para obtener el PBT de un arreglo dado.

PALABRAS CLAVE: Árbol binario completo, arreglo, algoritmo, conjunto de Catalan.

ABSTRACT

Planar binary trees are a subclass of simple graphs in which each vertex has at least one and at most three incident edges, with one vertex having two incident edges. Each vertex with three incident edges is called a father. The main father or root is the vertex with two incident edges. Finally, the vertices with only one incident edge are called leaves and all edges are branches. It is thus convenient, when graphically representing PBTs, not to take into account the isomorphisms between them when their only difference is a rotation of 180° with regard to the root. The PBT sets of n parents and the Catalan set Y_n can then be shown to be equivalent. PBTs can also be represented by numeric arrays, based on the Permutation-like notation of trees, in which the number of fathers is important to determine the array; i.e., the permutation of a PBT. In this study we developed algorithms for the conversion of PBTs in numeric arrays, thus providing improved reliability when using the above mentioned representation. Lastly, we developed an algorithm to obtain the PBT of a given array of numbers.

KEY WORDS: Planar binary tree, array, algorithm, Catalan set.