Chapter 14

Red–Black Trees and Splay Trees

This chapter introduces the data structures, red-black trees and splay trees. It describes how red-black trees exist with the reason behind them along with its definition and representation. Most popular operations on red-black trees are exemplified. Splay trees, splay rotations and amortized analysis with respect to splay trees are also explained in the chapter. This chapter also includes the applications of red-black trees and splay trees.


B trees of order m discussed in the earlier chapter have a number of applications as they minimize disk accesses. To implement its node, sequential data structures like arrays may be invoked. So, in a B-tree of order m every node requires two ...

Get Data Structures and Algorithms Using C++ now with O’Reilly online learning.

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