Data Structures & Algorithms in Python

10. AVL and Red-Black Trees

In This Chapter

• Our Approach to the Discussion

• Balanced and Unbalanced Trees

• AVL Trees

• The Efficiency of AVL Trees

• Red-Black Trees

• Using the Red-Black Tree Visualization Tool

• Experimenting with the Visualization Tool

• Rotations in Red-Black Trees

• Inserting a New Node

• Deletion

• The Efficiency of Red-Black Trees

• 2-3-4 Trees and Red-Black Trees

• Red-Black Tree Implementation

As you learned in Chapter 8, “Binary Trees,” ordinary binary search trees offer important advantages as data storage structures. They enable quick search for an item with a given key, and quick insertion or deletion of an item. Other data storage structures, such as arrays, sorted arrays, linked lists, and sorted linked lists, ...