Map Index Random Help Topics

## Topic: trees

topics > computer science > data > Group: data structures

Group:
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 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 special-range 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 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: 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: on-line 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 sub-tree in each node Quote: enhancements to ropes/cords: rebalance tree, user-defined functions at leaf nodes, substring nodes

Subtopic: B-tree

 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 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 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]

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: 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)

Updated barberCB 3/05