The Joy of Kotlin

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, ...