Engineering, 25.10.2019 22:43, arias333
The insertions in red-black trees cost upto 2 rotations (if uncle is black) and upto o(log n) color changes (if uncle is red). show that amortized color updates per insertion is o(1). (hint: to develop an appropriate potential function try to see what is decreasing in the structure when we push the red-conflict upwards in case 1.)
Answers: 3