Introduction

We have learned how to build a tree structure that can provide \(O(\log n)\) time complexity for insertion, deletion, and lookup operations on a randomly ordered set of data. However, we can’t provide any guarantees about performance because our tree can become unbalanced with certain patterns of insertions and deletions. In this chapter we explore ways to maintain balance automatically during insertions and deletions.

We will be focusing on understanding these structures conceptually. We will look at a few snippets of code but will not be building full implementations.