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