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 $ \Theta(n) $ time where $ n $ 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 $ O(h) $ time where $h$ is the height of the tree.

The authors show that the worst-case height of binary search tree can be $n-1$ when the input keys are in increasing order. If the input is randomized then the expected height of the tree is $ O (\lg n) $.

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