English subtitles

← 03-07 Splay Tree Issues

03-07 Splay Tree Issues

Get Embed Code
1 Language

Showing Revision 2 created 07/16/2014 by Udacity Robot.

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