Would I be right in saying that the red uncle case is equivalent to splitting a 4-node in the 2-3-4 tree (but recursing bottom to top), and the black uncle case is equivalent to merging into a 3-node?
@@FrankStajanoExplains Hm, I guess I convinced myself by drawing diagrams for all the cases, but I will try. If the parent p is black, then p must be the root of a 2- or 3- node cluster, and in both cases we can add n as a red node to make a 3- or 4-node cluster. Otherwise, p is red, so must be part of a 3- or 4- node cluster. If the uncle u is red, the parent/uncle are part of a 4-node cluster [p, g, u]. When we invert the colours, p and u become black, so we get the 2-3-4 tree [p]-[g]-[u], which is the split operation. We then recursively insert the grandparent, and add n to p, to get [n, p]-[g]-[u]. If u is black, and n is a left child of p, then we go from [p, g] - [u] to [n, p, g] - [u], so n is inserted into the 3-node.
Why is it necessary that all leaves must be black with no key-value pairs it seems like this just results in an extra layer underneath everything that adds no information?
You have to stop somewhere, otherwise the tree would be infinite. Those black leaves are a bit (a bit!) like null pointers. But calling them leaves and giving them a colour lets you reason consistently about path lengths etc.
The most helpful lecture about RB tree for me
@@莊涵盛-n6u glad it helped you!
Would I be right in saying that the red uncle case is equivalent to splitting a 4-node in the 2-3-4 tree (but recursing bottom to top), and the black uncle case is equivalent to merging into a 3-node?
I like this. This sounds like a good hunch, but I’d encourage you to produce a proper justification if you wanted to convince me fully.
@@FrankStajanoExplains Hm, I guess I convinced myself by drawing diagrams for all the cases, but I will try. If the parent p is black, then p must be the root of a 2- or 3- node cluster, and in both cases we can add n as a red node to make a 3- or 4-node cluster.
Otherwise, p is red, so must be part of a 3- or 4- node cluster. If the uncle u is red, the parent/uncle are part of a 4-node cluster [p, g, u]. When we invert the colours, p and u become black, so we get the 2-3-4 tree [p]-[g]-[u], which is the split operation. We then recursively insert the grandparent, and add n to p, to get [n, p]-[g]-[u].
If u is black, and n is a left child of p, then we go from [p, g] - [u] to [n, p, g] - [u], so n is inserted into the 3-node.
@@zakbuzzard9161 Brilliant! You got this.
Why is it necessary that all leaves must be black with no key-value pairs it seems like this just results in an extra layer underneath everything that adds no information?
You have to stop somewhere, otherwise the tree would be infinite. Those black leaves are a bit (a bit!) like null pointers. But calling them leaves and giving them a colour lets you reason consistently about path lengths etc.