Trees and the Structure of Data

One of the basic tools that computers use to organize data is trees. Trees are at the heart of how computers understand the programs that we write down, trees for the basis of many basic algorithms, and trees are the foundation for almost every piece of data that a web page or web-based application communicates over the internet.

Prerequisites

You should know how to write a recursive function and a loop in some programming language. Computation and Change is the right starting point otherwise.

The exercises in this course can be done in essentially any programming language. I would recommend Haskell, OCaml, or Typescript. I'd be comfortable teaching this topic in C, Java, Python, Scheme/Racket/LISP, Standard ML, or Prolog/logic programming. Feel free to ask about other languages.

Topics

The core of the course is a discussion of how basic tree structures are written down and communicated by humans, stored and transmitted by computers, and manipulated by programs, especially:

  • Binary search trees that implement sets or dictionaries.
  • Syntax trees that represent the structure of programs.
  • XML or JSON trees that flexibly represent data.

Beyond that, the course is designed to be flexible. In guided instruction, this topic could encompass the following:

  • Functional data structures like balanced binary search trees, tries, ropes, and discrimination trees.
  • A closer look at algorithms and tools for parsing code to create syntax trees.
  • Every type system, tool, or language that facilitates programming with tree-structured data has advantages and shortcomings. We can look into one or two tools in depth and see where they work best and fail hardest.
  • Comparing the nuts and bolts of how different languages actually represent trees.

Learn this topic at your own pace with expert help

tree-tiny