17
$\begingroup$

I have a little history question, namely, as the title says, I am looking for early uses of trees (as a data structure, search tree, whatever) in computer science.

$\endgroup$
  • 2
    $\begingroup$ There is likely an earlier use of the term in the context of graph theory. $\endgroup$ – Juho Dec 18 '15 at 13:50
  • $\begingroup$ Probably since the beginning. Oh, you mean that kind of trees. $\endgroup$ – 200_success Dec 18 '15 at 22:18
13
$\begingroup$

Wikipedia says that the first use of tree in mathematics was by Cayley in 1857.

Since the use in computer science is taken directly from mathematics, it seems more fundamental to ask when they originated there. Unless computer scientists originally called trees something else, the first computer scientist to use "tree" doesn't seem any more significant than, say, the first Australian to use "tree".

$\endgroup$
  • $\begingroup$ Cayley probably coined the word "tree", but trees have been used before (e.g., by Kirchhoff). In the 19th century mathematicians did not really care about algorithms (some exceptions here). Trees were definitely not used as a data structure like a search tree in these works. $\endgroup$ – A.Schulz Dec 18 '15 at 18:12
11
$\begingroup$

According to Donald Knuth's TAOCP, Vol. 1, pg. 459 the following papers might be considered as one of the first appearances of trees in CS.

  • H. G. Kahrimanian, Analytical Differentiation by a Digital Computer, Symposium on Automatic Programming, 6–14, 1952
  • K.E. Iverson and L.R. Johnson, IBM Corp. research reports RC-390, RC-603, 1961
  • A.J. Perils and C. Thornton, Threaded trees, CACM 3, 195–204, 1960

Check out TAOCP for more information and more references.

$\endgroup$
  • $\begingroup$ Thanks, that looks very promising. Does the second reference have a title? I don't have TAOCP at hand, I'll go to the library later. $\endgroup$ – john_leo Dec 18 '15 at 14:20
  • 4
    $\begingroup$ This is an argument by authority that may actually work, given that Knuth is known to be a very diligent collector of references. $\endgroup$ – Raphael Dec 18 '15 at 16:25
  • $\begingroup$ INVERSON, K. E. A programming notation for trees. Research Report R--390, II3M Research Center (Jan. 1961). That's from here: dl.acm.org/citation.cfm?id=366828 which also might be a good reference. $\endgroup$ – KWillets Dec 18 '15 at 21:15
  • $\begingroup$ @Raphael He literally wrote the book on computer science, didn't he... $\endgroup$ – corsiKa Dec 18 '15 at 23:22
6
$\begingroup$

Isaiah: ""And there shall come forth a rod out of the stem of Jesse, and a Branch shall grow out of his roots"

The tree as a data model for genealogical information is very ancient indeed.

$\endgroup$
  • 2
    $\begingroup$ "... in computer science." $\endgroup$ – Raphael Dec 19 '15 at 11:26
  • $\begingroup$ @Raphael Fair point, though it is arguably a data structure, which is tenuously computer-science-by-another-name. $\endgroup$ – David Richerby Dec 19 '15 at 20:33
  • 3
    $\begingroup$ I tend to Dijkstra's view that computer science is all about data structures and algorithms, and has very little to do with computers. $\endgroup$ – Michael Kay Dec 20 '15 at 16:52
4
$\begingroup$

I found this paper in the (BCS) Computer Journal for 1960:

P. F. Windley: Trees, forests, and rearranging.

He introduces the concept of "trees", "described briefly by Douglas (1959)" [Sandy Douglas] "and attributed to Berners-Lee" [Conway Berners-Lee, father of Tim].

Interestingly his trees are botanically more accurate than modern CS trees, in that they have the root at the bottom rather than the top!

http://comjnl.oxfordjournals.org/content/3/2/84.full.pdf+html?sid=a1c02733-1497-49e9-b308-a05c1dcca1df

Coincidentally, the last citation in the paper is to a paper which Windley co-authored with Tony Rowland Jones and "L. F. Kay", which is a misprint for L. R. Kay, my father, who went on to run UCCA, the central University Admissions system in the UK.

A letter from Conway B-L to the Computer Journal commenting on this paper, and a response from Windley, is split between pages 174 and 184 of the following issue:

http://comjnl.oxfordjournals.org/content/3/3/174.full.pdf+html http://comjnl.oxfordjournals.org/content/3/3/175.full.pdf+html

$\endgroup$
3
$\begingroup$

Lambda calculus dates back to the 1930's. Its grammar is an early application of trees, specifically abstract syntax trees. Every LC term is a tree. Variables are the leaf nodes. Both abstraction and application terms consist of other terms, so they are non-leaf nodes.

I don't know when LC terms were first thought of as trees. However, the early proofs involving LC required case analysis, much like what programmers writing programs to walk ASTs do now.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.