| 
|
Topic: trees
topics >
computer science >
data >
sequences
Topic:
b-trees
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, B-tree, syntax tree, suffix trie, height-balanced tree, and concatenation tree. (cbb 6/06)
Subtopic: tree traversal
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: subtree
QuoteRef: morrJH8_1972 ;;760 treewalk special-range with node: @@ and leaf: expr2 specific, not understood treewalking
Subtopic: trees for data communication
Quote: with hierarchical organization; users want to operate on subtrees [»akscRM5_1984]
Subtopic: suffix tree or trie
Quote: the Connection Machine uses trees and butterflies for collecting, combining, and spreading information, e.g., sets; need two-way 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: concatenation tree
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: on-line construction of suffix tree in O(N) [»nelsMR8_1996]
Subtopic: B-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 sub-tree in each node Quote: enhancements to ropes/cords: rebalance tree, user-defined functions at leaf nodes, substring nodes
Subtopic: tree access
Quote: each B-tree level increases size by 400x; at most two physical I/O per operation due to caching highest levels [»bayeR_2002]
Subtopic: tree representation
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: implicit representation
Quote: stores data as multi-level 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 null-pointers in a special way [»taylDJ11_1980, OK]
Quote: can implicitly represent regularly structured trees and butterflies by address [»hillWD_1985] QuoteRef: sammJE_1969 ;;456 matched parens to show tree structure %!!
Group: sequences (7 topics, 97 quotes)
Topic: b-trees (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)