Methods for storing AND/OR tree structures and their variants in RAM and ROM

Abstract: Tree structures are widely used to represent information objects containing hierarchical relations between their parts. An exam-ple of such tree structures are AND/OR trees, that have found their application in the development of combinatorial generation algorithms and related tasks. This paper explores possible ways to store tree structures in the random access memory (RAM) and read only memory (ROM) of devices that process these structures. The adaptation of these methods to the problem of storing AND/OR tree structures and their variants is also con-sidered. In addition, to organize operational work with stored variants of the AND/OR tree, the authors propose the bijective mapping of an AND/OR tree structure to a relational database schema.

Keywords: relational database, linked list, data structure, read only memory, random access memory, and/or tree variant, tree structure