Group: sequences
Topic: btrees
Topic: graphs
Topic: hierarchical structures
Topic: sparse arrays
Topic: structured programming
Topic: suffix trie and suffix array
Topic: syntax analysis
 
Summary
In computer science, a tree is a hierarchical data structure of nodes and leaves. There is one root node. A node may have one or more children. Leaves are nodes without children. There may be a fixed or variable number of children per node.
Trees are useful data structures. Types of trees include binary tree, Btree, syntax tree, suffix trie, heightbalanced tree, and concatenation tree. (cbb 6/06)
Subtopic: tree transformation
Quote: transform tree structures by transforming a linear representation of the tree; use string transformations [»chriC8_1966, OK]
 QuoteRef: chriC8_1966 ;;570 Ambit for manipulating trees follow up
 Subtopic: tree traversal
QuoteRef: morrJH8_1972 ;;760 treewalk specialrange with node: @@ and leaf: expr2 specific, not understood treewalking
 Subtopic: subtree
Quote: with hierarchical organization; users want to operate on subtrees [»akscRM5_1984]
 Subtopic: trees for data communication
Quote: the Connection Machine uses trees and butterflies for collecting, combining, and spreading information, e.g., sets; need twoway pointers [»hillWD_1985]
 Quote: a butterfly structure avoids the exponential behavior of trees by keeping the levels constant sized; omega network, perfect shuffle, FFT [»hillWD_1985]
 Subtopic: suffix tree or trie
Quote: compress assembly code by identifying common substrings via suffix trees; 7% compression on average [»frasCW6_1984]
 Quote: Bonsai trees compress large trie structures to 1/3; encodes indices with 32 by 32 bit multiplication [»darrJJ3_1993]
 Quote: online construction of suffix tree in O(N) [»nelsMR8_1996]
 Subtopic: concatenation tree
Quote: represent rope/cord as an ordered concatenation tree with flat strings for leaves and shared nodes with other ropes [»boehHJ12_1995]
 Quote: efficient operations on ropes/cords by storing the length of the subtree in each node
 Quote: enhancements to ropes/cords: rebalance tree, userdefined functions at leaf nodes, substring nodes
 Subtopic: Btree
Quote: each Btree level increases size by 400x; at most two physical I/O per operation due to caching highest levels [»bayeR_2002]
 Subtopic: tree access
Quote: access a tree structure by specifying a path or a matching pattern [»elsoM3_1970, OK]
 QuoteRef: kiebRB9_1973 ;;4.3 p(n) father of p(n) has composite type of p(n)>p(n) where p(n) is a pointer to a note (this forms a function returning type p(n))
 QuoteRef: kiebRB9_1973 ;;%Earley: pointer in a data structure is an access path
 Subtopic: tree representation
Quote: stores data as multilevel strings from character, to symbol, ..., to library [»mullAP_1964, OK]
 QuoteRef: mullAP_1964 ;;452 definition by n A n(3)(3)H(1)B(2)C(1)D(3) then can "insert the value string into another, or "join" two named strings together(retainnames)
 Quote: threaded binary tree for detection and correction of errors: link nullpointers in a special way [»taylDJ11_1980, OK]
 Subtopic: implicit representation
Quote: can implicitly represent regularly structured trees and butterflies by address [»hillWD_1985]
 QuoteRef: sammJE_1969 ;;456 matched parens to show tree structure %!!

Related Topics
Group: sequences (7 topics, 97 quotes)
Topic: btrees (16 items)
Topic: graphs (18 items)
Topic: hierarchical structures (46 items)
Topic: sparse arrays (6 items)
Topic: structured programming (27 items)
Topic: suffix trie and suffix array (20 items)
Topic: syntax analysis (29 items)
