Clojure Data Structures and Algorithms Cookbook

Chapter 3. Walking Down Forests of Data

In this chapter, we will focus on trees. We will cover the following recipes:

• Building self-balancing and search-efficient splay trees
• Designing an efficient key-value store using B-trees
• Devising an undo-capable data structure using a rope
• Designing an autocomplete system using a trie

Introduction

In this chapter, we'll delve into some particular types of trees. As you will see through the recipes, using one or the other of these data-structures is motivated by the urge to address some very specific problematic while exposing an interesting algorithmic solution to the case being studied. For instance, we'll see some tree data structures that try to address efficiency of elements' access, along with others that ...