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 are used as powerful tool empowering us to with advanced string manipulation capabilities. In this chapter, we'll cover the following recipes:
Building self-balancing, search-efficient splay trees: This data structure is an enhancement to the binary search trees, providing for a mechanism to keep a good balance among the trees elements, while permitting a more efficient access to its most accessed elements.
B-trees: B-trees are commonly used in databases and filesystems, thus we will design a B-tree in order to implement a minimalistic key-value store. A B-tree...