left-child right-sibling binary tree
   HOME

TheInfoList



OR:

Every multi-way or
k-ary tree In graph theory, an ''m''-ary tree (also known as ''n''-ary, ''k''-ary or ''k''-way tree) is a rooted tree in which each node has no more than ''m'' children. A binary tree is the special case where ''m'' = 2, and a ternary tree is another c ...
structure studied in
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
admits a representation as a
binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
, which goes by various names including child-sibling representation, left-child, right-sibling binary tree, doubly chained tree or filial-heir chain. In a binary tree that represents a multi-way tree , each node corresponds to a node in and has two
pointers Pointer may refer to: Places * Pointer, Kentucky * Pointers, New Jersey * Pointers Airport, Wasco County, Oregon, United States * The Pointers, a pair of rocks off Antarctica People with the name * Pointer (surname), a surname (including a l ...
: one to the node's first child, and one to its next sibling in . The children of a node thus form a
singly-linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...
. To find a node 's 'th child, one needs to traverse this list: procedure kth-child(n, k): child ← n.child while k ≠ 0 and child ≠ nil: child ← child.next-sibling k ← k − 1 return child ''// may return nil'' The process of converting from a k-ary tree to an LC-RS binary tree is sometimes called the '' Knuth transform''. To form a binary tree from an arbitrary k-ary tree by this method, the root of the original tree is made the root of the binary tree. Then, starting with the root, each node's leftmost child in the original tree is made its left child in the binary tree, and its nearest sibling to the right in the original tree is made its right child in the binary tree. Doubly chained trees were described by
Edward H. Sussenguth Edward H. (Ed) Sussenguth Jr. (October 10, 1932 – November 22, 2015) was an American engineer and former IBM employee, known best for his work on Systems Network Architecture (SNA). He was also a contributor to the architecture of IBM's Advance ...
in 1963. Processing a k-ary tree to LC-RS binary tree, every node is linked and aligned with the left child, and the next nearest is a sibling. For example, we have a ternary tree below: 1 /, \ / , \ / , \ 2 3 4 / \ , 5 6 7 / \ 8 9 We can re-write it by putting the left child node to one level below its parents and by putting the sibling next to the child at the same level it will be linear (same line). 1 / / / 2---3---4 / / 5---6 7 / 8---9 We can transform this tree to a binary tree by turning each sibling 45° clockwise. 1 / 2 / \ 5 3 \ \ 6 4 / 7 / 8 \ 9


Use cases

The LCRS representation is more space-efficient than a traditional multiway tree, but comes at the cost that looking up a node's children by index becomes slower. Therefore, the LCRS representation is preferable if # Memory efficiency is a concern, and/or # Random access of a node's children is not required. Case (1) applies when large multi-way trees are necessary, especially when the trees contains a large set of data. For example, if storing a
phylogenetic tree A phylogenetic tree (also phylogeny or evolutionary tree Felsenstein J. (2004). ''Inferring Phylogenies'' Sinauer Associates: Sunderland, MA.) is a branching diagram or a tree showing the evolutionary relationships among various biological spec ...
, the LCRS representation might be suitable. Case (2) arises in specialized data structures in which the tree structure is being used in very specific ways. For example, many types of heap data structures that use multi-way trees can be space optimized by using the LCRS representation. (Examples include
Fibonacci heap In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binar ...
s,
pairing heap A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are ...
s and
weak heap In computer science, a weak heap is a data structure for priority queues, combining features of the binary heap and binomial heap. It can be stored in an array as an implicit binary tree like a binary heap, and has the efficiency guarantees of ...
s.) The main reason for this is that in heap data structures, the most common operations tend to be # Remove the root of a tree and process each of its children, or # Join two trees together by making one tree a child of the other. Operation (1) it is very efficient. In LCRS representation, it organizes the tree to have a right child because it does not have a sibling, so it is easy to remove the root. Operation (2) it is also efficient. It is easy to join two trees together.


References

{{CS-Trees Binary trees