Topic: trees

topics > computer science > data > Group: data structures

hierarchical structures
sparse arrays
structured programming
suffix trie and suffix array
syntax analysis


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 up

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 up

QuoteRef: morrJH8_1972 ;;760 treewalk special-range with node: @@ and leaf: expr2 specific, not understood treewalking

Subtopic: subtree up

Quote: with hierarchical organization; users want to operate on subtrees [»akscRM5_1984]

Subtopic: trees for data communication up

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 up

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 up

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 up

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 up

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 up

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 up

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 up

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
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.