Notes From Wednesday

SPLAY TREES Remember Binary Search Trees from CS 17? If not, the notes are still online.
A problem we would get with BSTs is that a lot of insert operations would unbalance the tree, which would therefore have effects on our runtime. There are various solutions to this problem that have each led to own specific data structures: treaps, red-black trees, and so forth. We look at splay trees because theyre EASY. Rotate Everything depends on the following operation: rotate. Rotate is basically summarised by:
In class we referred to them as clockwise and anticlockwise. The forward arrow shows P rotating clockwise; the back arrow shows Q rotating anticlockwise. Note that A, B, and C can each also be BSTs. The way to figure out this operation is to place P at the top; then refigure out the tree from there. Really, not much changes; all that you should pay attention to is how B moves. B is greater than P but smaller than Q, so that explains why in the rotated tree it becomes Qs left node. The way we are thinking of this is that each of these nodes has three pointers: leftChild, rightChild and parent.(This is a little different from CS 17 where we didnt bother having the parent referred to, but it makes our life much easier here). Rotate can then be seen as just reassigning pointer values, so rotate is a constant time operation. Note that its also a local operation. What well do in splay trees is that were going to use rotate to get the lowestaccessed node to the top of the tree. More about that later. Rotation in practice: Lets try out to see whether rotating a tree could help us some. Say we have the following tree: (X here denotes a leaf. Im sorry if Im being confusing, but Im just grasping at straws here in
terms of how to make this clear without just pencil and paper.) So the idea that were going to do is perform a sequence of rotations in order to try to get 1 to the top. So we get: (try this yourself)
And so forth. Now Im gonna skip a lot of steps to get to the final, but you should do the whole thing just to get a feel for rotate and how it works.
So this isnt much better than our original tree. In fact its just as bad. So whats the point of rotation if it doesnt seem to help? Well, splay trees are a little smarter than just rotating forever. So lets talk about them.
Splay Trees Splay trees are self-balancing BSTs with just a basic operation: rotate above the usual BST operations (insert, lookup, delete, search, etc.) ADVANTAGES: -simple: only extra operation is rotation - state-efficient, meaning: no extra information needs to be stored to balance the tree (this is not true of other solutions) - operations are (log n) amortized - working set: recently accessed items are closer to the root: near the root access time is almost constant. Remember how in Huffman coding more popular nodes were higher up in the Huffman tree? Splay trees take this to the extreme, as the popularity of nodes can shift and the tree will adapt. DISADVANTAGE: - The runtime has to be amortized log n KEY IDEA You want to move the DEEPEST accessed node to the root using a sequence of rotations, called splay steps Splay Steps Say we want to splay a node X, ie, aid in its moving up towards the root. There are three possible cases for X. 1. Zig Zag: X is the left child of a right child, or the right child of the left child: 1. Rotate X up 2. Rotate X up again.
Note: youll want to try these operations out by hand, just to get a feel for them.
2. Zig-zig: X is the left child of a left child, or X is the right child of a right child. 1. Rotate Parent of X up (here parent pointers come in handy) 2. Rotate X up This one youll certainly want to do by hand, just to understand it. Youll notice how at a certain point the tree seems perfectly balanced, and then the next step unbalances it again. This is no issue: these operations will be repeated several times, so in the end the tree will be somewhat more balanced.
So in this diagram, we would first rotate up P, and then we would rotate X up. 3. Zig: X is a child of the root of the tree 1. Counterclockwise or clockwise rotation of X up to the root => whatever is appropriate
Now try these steps on the original tree (that 7 1 chain. ) you should eventually get:
As you can see, the last tree isnt perfectly balanced. But it is a lot better than what we started with. On average, the tree will somehow balance itself out in action. In action So BSTs have three operations. Which node should you move up in every operation? Remember, we want to splay the LOWEST ACCESSED NODE. So: Lookup: You splay the node you looked up (as this will be the lowest node you accessed) Insert: Splay the inserted node (as this will be lowest down in the tree) Delete: There are two possible cases: CASE 1: Youve deleted a node with no children, so at the bottom of the tree. In this case you should splay the nodes parent. CASE 2: Youve deleted a node with children. Remember from CS17 how when you deleted a node in the tree, youd dig up its predecessor and replace the deleted node by the predecessor. Ie. Youd either go to the left child and then find the rightmost node, or go to the right child and find the leftmost node. In this case, as the predecessors PARENT is the lowestmost node you accessed, you want to splay the predecessors parent. So now all that is our homework assignment! Fridays lecture was a long analysis of splay trees. Im not even gonna try to explain it cos it was kind of weird and hard.

Notes From Wednesday

Uploaded by

Copyright:

Available Formats

Notes From Wednesday

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Notes From Wednesday

Uploaded by

Copyright:

Available Formats

SPLAY TREES Remember Binary Search Trees from CS 17? If not, the notes are still online.

You might also like