Here are the slides from today’s lecture:
Here are some lecture notes from today’s lecture:
Note that the above lecture notes cover Red-Black trees, which we did not. Here you can find some treap code in python. To add augmentation, simply add a recalculate function to the TreapNode class with the data you’d like to augment and what the data should be on a None value. When I run this with 100,000 insertions, this (not super optimized) implementation takes around 0.72 seconds. I think that’s pretty impressive 🙂