Red-Black Tree
A self-balancing tree like AVL Tree
Every node has a black and red circle with the root having a black circle. Any external nodes are colored black and every red node can’t have red node as its children or else it is unbalanced.
Insertion:
Every new node is red.
If (1): parent and uncle of new node is red, change parent’s or uncle’s color to black and grandparent’s color to red.
If(2): parent of the new node is red and uncle is black, do rotation (L – L, R – R, L -R or R – L).
Deletion:
If(1): the node being deleted has a red-colored parent and a black-colored child (excuse the racism), then the child can be replaced directly.
If(2): the node being deleted has a black-colored parent (wow, again with the racism) and a red-colored child, the child could replace the node but it has to change color from red to black (my god the racism on this post is off the roof).
2-3 Tree
Tree where the node has one element of data and two children or two element of data and three children.
Insertion:
If the leaf has 2 nodes, insert the new data until the leaf has 3 nodes.
If the leaf has 3 nodes, push the middle data between A and B to the parent. Then, split the 2 data left to become 2-node. Repeat until parent is correct.
Deletion:
If the leaf has 3 nodes, then delete the data so it becomes 2 nodes.
If the leaf has 2 nodes, then:
If parents has 3 nodes, take one of the data, if the sibling has 3 nodes, then push the data to parent. If sibling has 2 nodes, make a parent to have 2 node and combine the node we have now with the sibling.
If parent has 2 nodes and sibling has 3 nodes, then take one of the data from the parent and push a data from the sibling to its parent. Then combine both of the parent and the sibling.