Red Black Trees

This article clarifies what is taught about red black tree in the lecture.

Red Black Trees is a form of self balancing Binary Search Trees, that any given time, has height at most 2log(n+ 1).

The root is always Black.

In this data structure, the root of a Red Black Tree is always black. This is a property of the red black tree that is taught in the lecture. For red black tree that you encounter in exercises and exams, the root is must always be black to be valid.

Further to understanding Binary Search Trees, I would reccomend first looking at the following 2 videos followed by any further material u find suitable. Although some variations in the design and explanation of the trees, if you understand their properties and how they work, u will be able to understand the questions asked in the exercises and the exams.

Initial reccomended videos (combined with lecture material):