Generic Data Structures and Algorithms in Go: An Applied Approach Using Concurrency, Genericity and Heuristics

© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022

R. WienerGeneric Data Structures and Algorithms in Gohttps://doi.org/10.1007/978-1-4842-8191-8_12

12. Red-Black Trees

Richard Wiener¹  

(1)

Colorado Springs, CO, USA

 

In the previous chapter, we presented heap trees. These are close to fully balanced trees in which the largest item is always found in the root node and each node has a value greater than its children.

In this chapter, we present another balanced tree structure, the red-black tree. Like the AVL tree presented in Chapter 10, the red-black tree data structure is aimed at efficient insertion, deletion, and searching of items stored in the tree.

In the next section, we introduce red-black trees.

12.1 ...