Left-child right-sibling binary tree

Last updated
6-ary tree represented as a binary tree N-ary to binary.svg
6-ary tree represented as a binary tree

Every multi-way or k-ary tree structure studied in computer science admits a representation as a binary tree, which goes by various names including child-sibling representation, [1] left-child, right-sibling binary tree, [2] doubly chained tree or filial-heir chain. [3]

In a binary tree that represents a multi-way tree T, each node corresponds to a node in T and has two pointers: one to the node's first child, and one to its next sibling in T. The children of a node thus form a singly-linked list. To find a node n's k'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
A trie implemented as a doubly chained tree: vertical arrows are .mw-parser-output .monospaced{font-family:monospace,monospace} child pointers, dashed horizontal arrows are next-sibling pointers. Tries are edge-labeled, and in this representation the edge labels become node labels on the binary nodes. Pointer implementation of a trie.svg
A trie implemented as a doubly chained tree: vertical arrows are child pointers, dashed horizontal arrows are next-sibling pointers. Tries are edge-labeled, and in this representation the edge labels become node labels on the binary nodes.

The process of converting from a k-ary tree to an LC-RS binary tree is sometimes called the Knuth transform. [4] 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 in 1963. [5]

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. [6] 

                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

  1. Memory efficiency is a concern, and/or
  2. 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, 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 heaps, pairing heaps and weak heaps.) The main reason for this is that in heap data structures, the most common operations tend to be

  1. Remove the root of a tree and process each of its children, or
  2. 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. [7]

Related Research Articles

<span class="mw-page-title-main">Binary search tree</span> Rooted binary tree data structure

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree.

<span class="mw-page-title-main">Binary tree</span> Limited form of tree data structure

In computer science, a binary tree is a k-ary tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root. Some authors allow the binary tree to be the empty set as well.

<span class="mw-page-title-main">Heap (data structure)</span> Computer science data structure

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap is called the root node.

In computer science, a red–black tree is a specialised binary search tree data structure noted for fast storage and retrieval of ordered information, and a guarantee that operations will complete within a known time. Compared to other self-balancing binary search trees, the nodes in a red-black tree hold an extra bit called "color" representing "red" and "black" which is used when re-organising the tree to ensure that it is always approximately balanced.

<span class="mw-page-title-main">Tree (data structure)</span> Abstract data type simulating a hierarchical tree structure and represented as a set of linked nodes

In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children, but must be connected to exactly one parent, except for the root node, which has no parent. These constraints mean there are no cycles or "loops", and also that each child can be treated like the root node of its own subtree, making recursion a useful technique for tree traversal. In contrast to linear data structures, many trees cannot be represented by relationships between neighboring nodes in a single straight line.

<span class="mw-page-title-main">Binary heap</span> Variant of heap data structure

A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.

<span class="mw-page-title-main">Smoothsort</span> Comparison-based sorting algorithm

In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of O(n log n), but it is not a stable sort. The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree, whereas heapsort averages O(n log n) regardless of the initial sorted state.

In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged. It is important as an implementation of the mergeable heap abstract data type, which is a priority queue supporting merge operation. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.

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 binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis.

In computer science, tree traversal is a form of graph traversal and refers to the process of visiting each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well.

A B+ tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.

<i>m</i>-ary tree Tree data structure in which each node has at most m children.

In graph theory, an m-ary tree is an arborescence 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 case with m = 3 that limits its children to three.

The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan and Jensen et al., d-ary heaps were invented by Donald B. Johnson in 1975.

In computer science, a pagoda is a priority queue implemented with a variant of a binary tree. The root points to its children, as in a binary tree. Every other node points back to its parent and down to its leftmost or rightmost descendant leaf. The basic operation is merge or meld, which maintains the heap property. An element is inserted by merging it as a singleton. The root is removed by merging its right and left children. Merging is bottom-up, merging the leftmost edge of one with the rightmost edge of the other.

<span class="mw-page-title-main">Cartesian tree</span> Binary tree derived from a sequence of numbers

In computer science, a Cartesian tree is a binary tree derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be the minimum number in the sequence, and recursively construct its left and right subtrees from the subsequences before and after this number. It is uniquely defined as a min-heap whose symmetric (in-order) traversal returns the original sequence.

<span class="mw-page-title-main">Ternary tree</span>

In computer science, a ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as "left", “mid” and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node, if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left, mid or right child.

A B-heap is a binary heap implemented to keep subtrees in a single page. This reduces the number of pages accessed by up to a factor of ten for big heaps when using virtual memory, compared with the traditional implementation. The traditional mapping of elements to locations in an array puts almost every level in a different page.

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 binomial heaps.

References

  1. ↑ Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). "The pairing heap: a new form of self-adjusting heap" (PDF). Algorithmica. 1 (1): 111–129. doi:10.1007/BF01840439.
  2. ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 214–217. ISBN   0-262-03293-7.
  3. ↑ PD-icon.svg This article incorporates public domain material from Paul E. Black. "Binary tree representation of trees". Dictionary of Algorithms and Data Structures . NIST.
  4. ↑ Computer Data Structures. John L. Pfaltz.
  5. ↑ Sussenguth, Edward H. (May 1963). "Use of tree structures for processing files". Communications of the ACM . 6 (5): 272–279. doi: 10.1145/366552.366600 .
  6. ↑ "binary tree representation of trees". xlinux.nist.gov. Retrieved 2015-11-24.
  7. ↑ "What is the left-child, right-sibling representation of a tree? Why would you use it?". stackoverflow.com. Retrieved 2016-12-12.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.