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.