10 More data handling with trees

 

In this chapter

  • Understanding size, height, and depth in a tree structure
  • Understanding insertion order in the binary search tree
  • 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 immutable data structure. Although the list is an efficient data structure for many operations, it has some limitations. The main shortcoming is 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. For example, 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 new data structure that solves these problems: the binary tree.

10.1 The binary tree

10.2 Understanding balanced and unbalanced trees

10.3 Looking at size, height, and depth in trees

10.4 Empty trees and the recursive definition

10.5 Leafy trees

10.6 Ordered binary trees or binary search trees

10.7 Insertion order and the structure of trees

10.8 Recursive and non-recursive tree traversal order

10.8.1 Traversing recursive trees

10.8.2 Non-recursive traversal orders

10.9 Binary search tree implementation

10.9.1 Understanding variance and trees

10.9.2 What about an abstract function in the Tree class?

10.9.3 Overloading operators

10.9.4 Recursion in trees

10.9.5 Removing elements from trees

10.9.6 Merging arbitrary trees

About folding trees

10.10.1 Folding with two functions

10.10.2 Folding with a single function

10.10.3 Choosing a fold implementation

About mapping trees