Binary Tree Diagram - With Boolean Expressions
The evolvement of binary tree diagram began in 1990's, when CEA, Dassault Aviation, EDF, ELF-EP, Renault, Schneider Electric, SGN, Technicatome formed a group to develop a software that would explore the use of binary decision diagrams in the field of Operating Dependability and Safety. In a few years, the group came up with a software tool that processed probabilistic formulae, and since that time the software has been meeting different areas of applications, catering for varied demands in qualitative and quantitative calculus of the members of the group.
The binary tree diagram produces a tree shaped diagram, which is also known as a dendrogram or phenogram. It is created by a data set derived from a cluster or Varclus procedure. The data produced by the Cluster and the Varclus, contains the results of hierarchical clustering as a tree structure. The output data set is used to produce the tree diagram in a style, where the root is at the top. The diagram may also be oriented horizontally, with the root at the left. Any of the numeric variables in the output data set could be used to specify the heights of the Clusters. A variable to indicate the disjoint clusters can also be created by PROC TREE from an output data set at a specified level in the tree.
Binary tree diagrams have been extensively discussed in the context of Cluster analysis by experts like Duran and Odell, Hartigan, and others, who provide a general outlook on tree diagrams in computer programming. The terminologies of the tree diagram are generally a mixture of botanical and genealogical terms. The objects that are clustered are leaves, and the Cluster containing the other objects is the root. If a Cluster contains at least two objects but not all forms the branch of the tree. The general term for leaves, branches, and roots is node. If a Cluster A is the union of Clusters B and C, then A is called the parent of B and C, while B and C are the children of A. Therefore, a leaf becomes a node with no children and a root is a node with no parent. If every cluster has a maximum of two children, the tree diagram is a binary tree. The CLUSTER procedure always outputs binary trees. The Varclus procedure can output tree diagrams with clusters that have many children.
Like a negation normal form (NNF), or a propositional directed acyclic graph (PDAG), binary tree diagram is a data structure which is used to represent a Boolean function. A Boolean function can be represented as a rooted, directed, acyclic graph, which consists of decision nodes and two terminal node called 0-terminal and 1-terminal. The decision nodes, which are labeled by a Boolean variable, have two child nodes called low child and high child. If you move from the edge of a node to a low child, it is represented by "0". On the other hand if it is a high child, it becomes "1". The edge from a node to a low or high child represents an assignment of the variable to 0 or 1respectively. Such binary tree diagrams are called "ordered" if it is found that the different variables appear in the same order on all paths. The diagram is called "reduced" if it follows to the two rules as below: Merge any isomorphic sub-graphs.
Eliminate any node whose two children are isomorphic. In general usages, binary tree diagram usually refers to Reduced Ordered Binary Decision Diagram (ROBDD). The advantage of an ROBDD is that it is unique for a particular functionality. This property makes it useful in functional equivalence checking and other operations like functional technology mapping. When binary decision diagram was first introduced it lacked a sophisticated, graphical interface for the fault tree diagram construction. With introduction of sophisticated graphical interface, highly complex fault tree facilities have been made available as an integrated part of binary tree diagram tool engine, which forms a complete, state of the art analysis tool, offering some of the most powerful and flexible safety analysis tools available anywhere today.
Privacy Policy
|
