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]

↑ 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.

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	Ball 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 6/15/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.