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


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, ...

Get Data Structures & Algorithms in Python now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.