0

The more CS I read the more I encounter trees, heaps and graphs. All languages seem to incorporate linear data types like lists and arrays and most have some compound data type like objects or structs but when it comes to hierarchical data structures like trees you've either got to roll your own each time or go hunting in the package ecosystem. It feels like in many languages trees are second class citizens even though they are seemingly fundamental to CS and lots of useful algorithms.

Why is this? Is it because there are too many variations of tree to be able to write a performant generic implementation?

1
  • 2
    The decision between "in language" and "in standard library" is not an easy one. Sep 20 '19 at 12:43
4

Most high level programming languages provide some kind of build-in container, since you cannot do much without any of them:

  • Most of them provide arrays. The principle is simple: you have an indexed set of values. It’s easy to implement and many published algorithms use indexed values.
  • Some, like LISP provide only lists.
  • Many modern languages provide more containers such lists, sets or dictionaries. These can be more tricky to implement, especially considering memory allocation issues. But the usage of these containers is straightforward and have only a limited number of options (double linked list or not ? ordered list or not ?)
  • Some specialized languages offer even more flexible containers such as tables (or in the case of prolog predicates)

Trees are generally not part of the language, because the usage of trees is much more diverse:

  • trees are often used for ordering a data structure. But if the language offers ordered containers, what would be the advantage of trees ? In C++ for example, trees are used in the standard library to implement some containers but this implementation detail is hidden. In many database oriented languages, trees are used behind the tables to implement indexing
  • trees come in many flavors: how many children per node ? binary tree or B-tree ? balanced tree or not ? unique node values or duplicates ?
  • There’s no standardized understanding of the interface a general tree should provide.

Finally trees are themselves only a special case of a more general graph structure. So people specially interested in trees for the beauty of the structure (and not only ordering), would probably often be equally well interested in graph structures.

4
  • 1
    "binary tree or B-tree ? balanced tree or not ?" - three variants all beginning with the letter 'B', including one whose name is the letter 'B', gives a nice taste of the subtlety involved!
    – Steve
    Sep 21 '19 at 8:03
  • @Steve :-) Indeed ! I used the B-tree on purpose, as many people assume that the B stands for Binary, whereas in reality B-tree can have n children and according to wikipedia, nobody knows what the B stands for ;-) (P.S: my own opinion is that B stands at the same time for Bayer, the inventor, and the following letter of A since AVL was the previously preferred algorithm)
    – Christophe
    Sep 21 '19 at 9:35
  • One nit, not that it matters post question closure: lisp builds other data structures (such as associate lists, or a-lists) on top of lists. Yes, it’s still a list. But it is really much more a dictionary. Sep 24 '19 at 3:56
  • @D.BenKnoble Interesting! Thank you for sharing. It’s never too late for expanding collective knowledge :-). Indeed, I tried to mention only the containers that are part of the core language, being understood that they can be used for building others. My lisp knowledge is somewhat outdated, but if I take C++ as example, the only build-in container is the array. But in combination with memory allocation, object model and template feature, it’s sufficient for building all the other containers provided by its standard library, that are used as if they were part of the language itself.
    – Christophe
    Sep 24 '19 at 6:37

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