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

    About balancing trees

    10.12.1 Rotating trees

    10.12.2 Using the Day-Stout-Warren algorithm

    10.12.3 Automatically balancing trees

    Summary