Data Structures and Algorithms Using C++

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.

14.1 INTRODUCTION

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