Rose tree

For the species of rhododendron, see Rhododendron maximum.

In computing, a multi-way tree or rose tree is a tree data structure with a variable and unbounded number of branches per node.^[1] The name rose tree for this structure is prevalent in the functional programming community, e.g., in the context of the Bird–Meertens formalism.^[2] It was coined by Lambert Meertens to evoke the similarly-named, and similarly-structured, common rhododendron.^[3]

Definition

The following is a definition in Haskell:

data RoseTree a = RoseTree a [RoseTree a]

Sources

↑ Haskell Wiki, accessed 26 January 2012
↑ Malcolm, Grant (1990). "Data structures and program transformation". Science of Computer Programming 14 (2): 255–279.
↑ Skillicorn, David B. (1996). "Parallel implementation of tree skeletons" (PDF). J. Parallel and Distributed Computing 39 (2): 115–125.

External links

Rose tree on the Haskell wiki
Bayesian Rose Trees
Data.Tree, an implementation of basic rose tree operations in the Haskell containers package

Tree data structures

Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red-black Scapegoat Splay T Treap UB Weight-balanced

Heaps	Binary Binomial Fibonacci Leftist Pairing Skew Van Emde Boas

Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast

Spatial data partitioning trees	BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree Priority R Quad R R+ R* Segment VP X

Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

This article is issued from Wikipedia - version of the Monday, June 15, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.