Chapter 10. More data handling with trees
This chapter covers
- Understanding the relationships between size, height, and depth in a tree structure
- Understanding the relationship between insertion order and the binary search tree structure
- Traversing trees in various orders
- Implementing the binary search tree
- Merging, folding, and balancing trees
In chapter 5, you learned about the singly linked list, which is probably the most widely used data structure in functional programming. Although the list is a very efficient data structure for many operations, it has some limitations, the main one being that the complexity of accessing elements grows proportionally with the number of elements. For example, searching for a particular element may necessitate examining all elements if it happens that the searched-for element is the last in the list. Among other less efficient operations are sorting, accessing elements by their index, and finding the maximal or minimal element. Obviously, to find the maximal (or minimal) element in a list, one has to traverse the whole list. In this chapter, you’ll learn about a data structure that solves these problems: binary trees.