AVL Red Black Every node is either red or black Root is black The leaves which are NULL are black Red must have two black children Every path from a node to its leave must have the same number of black children B Trees A*