Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 12 and Chapter 13

Chapter 12
The authors discuss properties of a binary search tree. The authors first define binary-search-tree-property. The authors define in-order, pre-order and post-order tree traversal. The authors prove that the walks take time where is the number of nodes in the tree.

The authors provide implementation of SEARCH, MAXIMUM, MINIMUM, INSERT, DELETE, PREDECESSOR and SUCCESSOR methods for a binary search tree and prove that each of it takes time where is the height of the tree.

The authors show that the worst-case height of binary search tree can be when the input keys are in increasing order. If the input is randomized then the expected height of the tree is .

Chapter 13
The authors, in this chapter, provide the concept of RED-BLACK TREE, describe its properties and prove them.