11 Solving problems with advanced trees

 

In this chapter

    • Avoiding stack overflow with self-balancing trees
    • Implementing the red-black tree
    • Implementing maps
    • Implementing priority queues

    In the previous chapter, you learned about the binary tree structure and basic tree operations. But you saw that to fully benefit from trees, you must either have specific use cases, such as handling randomly ordered data, or a limited data set in order to avoid any risk of stack overflows. Making trees stack-safe is much more difficult than it was for lists because each computing step involves two recursive calls. That makes it impossible to create tail-recursive versions. In this chapter, you’ll learn about two specific trees:

    • The red-black tree is a self-balancing, general-purpose tree with high performance. It’s suitable for general use and data sets of any size.
    • The leftist heap is a specific tree suitable for implementing priority queues.

    You’ll also learn how to implement maps using trees storing key/values tuples. And you’ll see how to create priority queues for noncomparable elements.

    11.1 Better performance and stack safety with self-balancing trees

    The Day-Stout-Warren balancing algorithm that you used in the previous chapter isn’t ideally suited for balancing immutable trees because it’s designed for in-place modifications. In order to write safer programs, in-place modifications must be avoided as often as possible.

    11.1.1 Understanding the basic red-black tree structure

    11.1.2 Adding an element to the red-black tree

    11.1.3 Removing elements from the red-black tree

    11.2 A use case for the red-black tree: Maps

    11.2.1 Implementing Map

    11.2.2 Extending maps

    11.2.3 Using Map with noncomparable keys

    11.3 Implementing a functional priority queue

    11.3.1 Looking at the priority queue access protocol

    11.3.2 Exploring priority queue use cases

    11.3.3 Looking at implementation requirements

    11.3.4 The leftist heap data structure

    11.3.5 Implementing the leftist heap

    11.3.6 Implementing the queue-like interface

    11.4 Elements and sorted lists

    11.5 A priority queue for noncomparable elements

    Summary