ENUMERATION, RANKING AND GENERATION OF BINARY TREES BASED ON LEVEL-ORDER TRAVERSAL USING CATALAN CIPHER VECTORS
Journal Title: Journal of Information Technology and Application (JITA) - Year 2013, Vol 3, Issue 2
Abstract
In this paper, a new representation of a binary tree is introduced, called the Catalan Cipher Vector, which is a vector of elements with certain properties. It can be ranked using a special form of the Catalan Triangle designed for this purpose. It is shown that the vector coincides with the level-order traversal of the binary tree and how it can be used to generate a binary tree from it. Streamlined algorithms for directly obtaining the rank from a binary tree and vice versa, using the Catalan Cipher Vector during the processes, are given. The algorithms are analyzed for time and space complexity and shown to be linear for both. The Catalan Cipher Vector enables a straightforward determination of the position and linking for every node of the binary tree, since it contains information for both every node’s ancestor and the direction of linking from the ancestor to that node. Thus, it is especially well suited for binary tree generation. Using another structure, called a canonical state-space tableau, the relationship between the Catalan Cipher Vector and the level-order traversal of the binary tree is explained.
Authors and Affiliations
Adrijan Božinovski, Biljana Stojčevska, Veno Pačovski
Keywords
Related Articles
- EP ID EP244506
- DOI 10.7251/JIT1302078B
- Views 100
- Downloads 0
E-COMMERCE IN DINACARD SYSTEM
This paper presents the status of e-commerce in Serbia with the focus on the domestic DinaCard system, its architecture and participants in the system. We reported results on Internet transaction in DinaCard system in 20...
SOCIAL MEDIA IN MARKETING AND PR
Social media as a new communication channel has managed to radicalize the way companies communicate with consumers and other stakeholders. Companies that are not on time engaged in social media weaken its ability for com...
TRENDS IN EDUCATIONAL GAMES DEVELOPMENT
In this paper we will give a literature review related to game-based education, in the fi rst place at university, as well as the analysis of existing solutions which should enable this type of eLearning. The main topic...
DATA VISUALIZATION ON INFORMATION TABLES - DASHBOARDS
Today’s level of the information technology development allows gathering of large amount of data relevant for a company. The issue of way and method of data gathering has been solved, however, at the same time the need a...
T he Use of Energy Storage Devices of Uncontrolled Type on the Mosc ow Metro (Theory and Practice)
The problem of increasing energy saving and energy efficiency in the system of traction power supply of the Moscow Metro is considered due to the use of energy storage devices of uncontrolled type. The results of simulat...