Hello everyone
This lecture for the data structure and algorithm is Splay tree in 12th chapter advanced data structure.
Splay tree is a self-organized data structure.
This so-called self-organized data structure is that
We can do some adjustment according to its using frequency during the use of this data structure.
For instance, if we use a word a lot of times in input method, this word might show up more frequent.
And it's convenient to retrieve. That's self-organized linear structure.
For BST it is important to keep order in in-order transversal.
So some adjustments will be made. It doesn't matter who the root is.
If we retrieve a key code lots of times.
And if there exists a method which can move this key code to the position near the root.
We might get better efficiency performance.
Tarjan develop a BST called splay tree.
This tree doesn't modify much about BST. It doesn't need balanced factor.
What does splay tree do? We just need to splay every time we operate.
Splay the current node to the root. That's splay tree mainly about.
So splay tree has a good efficiency performance.
Splay tree is very practical.
The adjustments have several situations.
If the current node is the direct child of the root. Then rotate the current node to the root.
All we need is a single rotation.
This single rotation contains zig and zag. Zig and zag are symmetric.
What about the nodes near the leaves (far from the root)?
We want it to rotate to the root as fast as possible.
Combine three nodes together. These nodes are the current node, the father and the grandfather of the current node.
The first situation is that
the current node is the left child of its father and its father is the left child of its grandfather.
The symmetric situation is changing left to right.
Let's say the current node is X. It's at the bottom.
We want to rotate X to the root of these three nodes.
Rotate like this. Then X became the root.
Another situation is symmetric.
If the current node is left child of its father and its father is the right child of its grandfather.
In this situation, we need to rotate the current node to the root.
After rotation, its father and grandfather became the current node's children.
The double rotation also has the same symmetric situation.
After rotation it has to be a balanced structure.
And it is ordered in in-order transversal after rotation.
The process of splay is actually a visit from the current node to the root.
Both inserting, deleting and retrieving work like this.
Combine three nodes together. Rotate the current node to the root of these three nodes.
Then start from the new root.
Combine three nodes together again.
Rotation
till the root.
But if the father of the current node is the root.
Then do a single rotation.
Everytime after inserting, deleting of retrieving, rotate the current node to the root.
The current node in inserting is the new node we just inserted.
The current node in retrieving is the node we need to retrieve.
What about deleting? The current node is the father of the deleted node.
During deleting, We need to find the biggest node in the left subtree or the smallest node in the right subtree.
Use the node, we just found, to replace the node we need to delete.
And rotate the current node to the root.
Let's take a close look at the adjustment of splay tree.
Let's take a look at single rotation. The current node x is the left child of node y.
The node y is the root of the subtree y.
After rotation, x became the new root and y became the right child of node x.
The double rotation contains zig-zig and zig-zag.
The current node, its father and its grandfather are involved in double rotation.
Actually double rotation is constituted by two single rotations.
That is zig and zag.
Review red-black tree and AVL tree, they are like this too.
If the current node is the left child of its father and its father is the left child of its grandfather.
Zig the father y and its grandfather, rotate y to the root.
Then zig the current node and its father. Zig the father first, then zig the current node.
If the current node is the right child of its father and its father is the left child of its grandfather.
This double rotation started from the current node, rotate with its father.
After rotate the current node, rotate the current node with its grandfather.
For structure like this, rotate the current node twice.
That's zag x the zig x.
Keep doing double rotation till the root.
If double rotation is not allowed, do a single rotation.
Then splay was done.
It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.
The tree is balanced and won't degenerated.
Let's take a look at this example. Retrieve node A first.
Start frome A, double rotation with three nodes.
The father of a is b, and its grandfather is c.
Single rotation with father and grandfather.
After b and c was done, rotate with a and b.
Rotate a to the new root of the subtree.
Then keep doing this.
double rotation.
a became new root again.
Now a is the child of the root. We can only do a single rotation.
The job was done after rotate a to the root of the whole tree.
Splay is easy to implement. Use a father point to record these ancesters.
Splay the current node to the root is very common.
The more common operation is rotate the node x to the child of some node f, which is the ancester of x.
This operation is similar to the operation we talked about before.
We just need to stop before met node f.
Inserting, retrieving and deleting is similar to the operations of BST.
The only difference is that we need to do a splay after operations.
Splay the current node. Then splay tree would have a good efficiency performance.
How to implement splay?
Splay is rotating the current node x to the child of some node f which is the ancester of x.
Denote that the current node's father is y, and its grandfather is z.
If node f is the father of node y. We can't double rotate with x, y and z.
If we did that, the x would be the root and f would be under x.
So we just need to single rotate with x and y.
x is grandson of z.
After single rotation, x will be the child of z.
Then our job is done.
If the node y isn't f. It's ok to double rotate.
Denote that z's left child is y.
If x is the left child of y
Rotate y first then rotate x.
Remember this order.
If x is the right child of y.
Zag x
Then zig x.
Rotate x twice.
Another symmetric situation, y is the right child of z. Then the father of y is f.
Single rotate with x and y. Rotate x to the child of node f.
If x is the left child of y, then zig x.
If not, Zag.
The father of the current node x would be empty after operation.
What's that?
Node x is the root of the whole tree.
Modify the global variable root to x.
Of course we can pass root as the parameter in the function.
There are lots of applications for splay tree.
Let's look at this example.
We want to delete the nodes whose values range from u to v.
u is smaller than v.
First rotate u to the root.
Then splay.
Splay v to the child of u.
v is the right child of u cause v is bigger than u.
All the nodes, whose values range bigger than u and smaller than v, are the left subtree of v.
Delete that left subtree.
Let's take a look at this example. u is 35 and v is 60.
Rotate u to the root then splay v to the right child of u.
Finally delete the left subtree of v.
Call the function splay with parameters u and null to splay u to the root.
The second the parameter is null means that we want u to be root.
Then call the function splay with parameters v and u.
This call will splay v to the right child of u. Then delete the left subtree of v.
Splay tree performs operations in O(log n) amortized time.
If the splay tree has n nodes and there are m operations.
We can prove that it costs O(m * log n) amortized time.
a single operation costs average log n.
To achieve this performance, splay must be done after inserting, deleting and retrieving.
Splay tree is widely used cause its easy implementation.
Let's take a look at a variety of splay tree.
The mainly difference is that
If the current node is the left child of its father and its father is the left child of its grandfather.
We rotate the current node to the root, its father became its son and its grandfather became its grandson before.
Now it's ok that the current node wasn't rotated to the new root.
Rotate the current node to the father of node x.
Find the other two nodes upon, do it with three nodes.
If the current node is the left child of its father and its father is the right child of its grandfather.
The process of rotation is very similar. And we don't take the current node x.
We just use its father node as the current node and continue operating.
It's like input method.
We don't put the word, we just retrieved, to the first of the vocabulary.
Instead we pass it slowly.
Let's think about the difference of applications between splay tree and the tree we talked about just now.
What else can splay tree's variety like? And what's the applications of splay tree?
Besides we can check some open source code like STL and Linux.
Look about how the splay tree, red-black tree and AVL tree was implemented.
We could find out that AVL tree was widely used during the beginning of some open source projects.
But now it's replaced by red-black tree and splay tree
Because they are faster and easy to implement.
Thank you