1 00:00:00,000 --> 00:00:04,000 Looking at that, there's a few extra things you need to know about splay trees, and the first is that 2 00:00:04,000 --> 00:00:09,000 it's a self-balancing tree which means that if you insert nodes in sort of order, remember we 3 00:00:09,000 --> 00:00:12,000 have a binary search tree but we call this stability tree that looks something like this. 4 00:00:12,000 --> 00:00:17,000 And so as you can see, this is a very bad kind of a binary search tree because here to do a lookup, 5 00:00:17,000 --> 00:00:21,000 we're going to have to walk all of the nodes in a tree and we'd lost this nice logarithmic property 6 00:00:21,000 --> 00:00:24,000 that made lookups and search and deletes extremely fast. 7 00:00:24,000 --> 00:00:28,000 The way a self-balancing binary search tree works is as you add elements to the tree 8 00:00:28,000 --> 00:00:32,000 that has some sort of a balancing procedure that keeps the thing approximately balanced 9 00:00:32,000 --> 00:00:34,000 so that tree operations remain very fast. 10 00:00:34,000 --> 00:00:38,000 And if you look at the literature, it turns out there are tons and tons of different data structures 11 00:00:38,000 --> 00:00:43,000 that offer self-balancing binary search trees and the fast ones of these end up being somewhat 12 00:00:43,000 --> 00:00:46,000 complicated and the splay tree is really one of the simplest examples of a self-balancing 13 00:00:46,000 --> 00:00:48,000 binary search tree and the implementation that we're going to look at 14 00:00:48,000 --> 00:00:50,000 in the minute contains something like a 100 lines of code. 15 00:00:50,000 --> 00:00:53,000 So the other thing you need to know about splay tree before you get into the code 16 00:00:53,000 --> 00:00:57,000 is that it has a really cool property that when we access the nodes, let's say we do a lookup 17 00:00:57,000 --> 00:01:02,000 of this node here which contains 7, what's going to happen is as a side-effect of the lookup 18 00:01:02,000 --> 00:01:08,000 that node is going to get migrated up to the root and then whatever was previously at the root 19 00:01:08,000 --> 00:01:11,000 is going to be pushed down and possibly some sort of a balancing operation is going to happen. 20 00:01:11,000 --> 00:01:16,000 But the point is, is that frequently accessed elements end up being pushed towards the root 21 00:01:16,000 --> 00:01:20,000 of a tree and therefore, future accesses to these elements become even faster. 22 00:01:20,000 --> 00:01:23,000 So this is sort of a really nifty feature of the splay tree. 23 00:01:23,000 --> 00:01:26,000 So what we're going to do now is look at an open source of Pythons splay tree, specifically a 24 00:01:26,000 --> 00:01:29,000 random-based structure that I found on the web and that happens to implement a 25 00:01:29,000 --> 00:01:33,000 splay tree--it comes with its own test suite and we're going to look at what kind of code 26 00:01:33,000 --> 99:59:59,999 coverage that this test suite gets on the splay tree.