[+] Link-Cut trees and Euler Tour trees |
| We show that the amortized cost per operation of Link-Cut trees is logarithmic. We also discuss how to implement decorations that allow updates and queries along a root-to-node path in logarithmic time. On the last part of the lesson we present Euler Tour trees. |
|
Download Video: 720p |
[No lecture notes for this lecture.] |
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email me.