Looking at that, there's a few extra things you need to know about splay trees, and the first is that
it's a self-balancing tree which means that if you insert nodes in sort of order, remember we
have a binary search tree but we call this stability tree that looks something like this.
And so as you can see, this is a very bad kind of a binary search tree because here to do a lookup,
we're going to have to walk all of the nodes in a tree and we'd lost this nice logarithmic property
that made lookups and search and deletes extremely fast.
The way a self-balancing binary search tree works is as you add elements to the tree
that has some sort of a balancing procedure that keeps the thing approximately balanced
so that tree operations remain very fast.
And if you look at the literature, it turns out there are tons and tons of different data structures
that offer self-balancing binary search trees and the fast ones of these end up being somewhat
complicated and the splay tree is really one of the simplest examples of a self-balancing
binary search tree and the implementation that we're going to look at
in the minute contains something like a 100 lines of code.
So the other thing you need to know about splay tree before you get into the code
is that it has a really cool property that when we access the nodes, let's say we do a lookup
of this node here which contains 7, what's going to happen is as a side-effect of the lookup
that node is going to get migrated up to the root and then whatever was previously at the root
is going to be pushed down and possibly some sort of a balancing operation is going to happen.
But the point is, is that frequently accessed elements end up being pushed towards the root
of a tree and therefore, future accesses to these elements become even faster.
So this is sort of a really nifty feature of the splay tree.
So what we're going to do now is look at an open source of Pythons splay tree, specifically a
random-based structure that I found on the web and that happens to implement a
splay tree--it comes with its own test suite and we're going to look at what kind of code
coverage that this test suite gets on the splay tree.