Lecture - 14 Red Black Trees

[MsDawdawdaw]

i ahve an exam soon hahah and i don't was able to follow the course this course is cool thx :)

[denebgarza]

Damn I just love the intro music. So chill.

[himanshu9408]

amazing

[chaimnatan]

What makes a node red? vs black?

[jonnism77]

@chaimnatan 1 possible situation (and probably the most frequent) is on the 2nd "Insertion" into a RB tree. Lets say you insert 5 as the first node into the RB tree. Now we have 1 node in our RB tree and (since it is the root) must be black. Then we insert 7 into the tree. Since 7 > 5, it must go on the right side. If we were to color this node black, the external nodes of 7 would have two black ancestors where as the external node of 5 (its left node) only has 1.Therefore the 7 node must be red

[FedericoLebron]

Many thanks - this helped immensely not only to implement a red-black tree, but to understand what was happening behind the deletion algorithm, and why it requires at most 3 rotations (although the particular case of 3 rotations, 2.1.1, when my red brother's right son has a red right son, isn't explicltly shown, but it's implied).

Overall, well explained and clearly shown in the slides. Thanks :)

[Rafdaganga]

better use the term "child" rather than son.. Otherwise a female marker might get pissed off...

[mzundu]

Good presentation

[kpn4321]

Thanx for this very helpful lecture. I have a problem .. In the deletion part of the lecture it is mentioned that successor can't have a right child, i think it can't have a left child but can have right child. It is predecessor that can't have a right child.

[arpit10001]

U r rite .... I haven't seen da whole lecture ... Bt wat u r saying is rite

TP

IITK