PPT Slide

Necessary and Sufficient Conditions for BST’s given

as red-black trees to be generated by the breadth-first

method using the insert and elete algorithms of Cormen,

Leiserson & Rivest:

For every subtree of the given BST, compute the height

of the left subtree, HL, and of the right subtree, HR.

Then for every subtree, either

1) | HL - HR | <= 1, or

2) Max (HL, HR) = k (even) and

Min (HL, HR) = (k - 2).

Previous slide

Next slide

Back to first slide

View graphic version