Learn

Now that we have implemented all of the individual operations for performing a splay of a target node, we need to implement the logic behind an entire splay operation. More specifically, how do we ensure that a target node five layers deep can be splayed up to the root, even if our core splaying operations are only built for two layers of rotations?

We can apply the six core operations again and again, as each operation will move a target node higher up the tree if applied correctly. When the target node is two or more layers deep, we will use a combination of zig-zig, zig-zag, zag-zig, and zag-zag operations. Finally, if our target node is the child of the root node, we can call a single zig or a zag operation.

Let’s look to now implement the necessary logic.

### Instructions

1.

We have given you the following starter code for `splay()` in script.py:

``````if node == self.root or node.parent == None:
return

while node != self.root:
parent = node.parent

if parent == self.root:
pass # Checkpoint 1

else:
grandparent = parent.parent
if parent.left == node:
pass # Checkpoint 2

else:
pass # Checkpoint 3

if node.parent == None:
self.root = node``````

Within the conditional statement `if parent == self.root:`, create the following logic:

• If `node` is to the left of the parent, use a `self._zig()` operation calling `node`.
• Otherwise, use a `self._zag()` operation calling `node`.

Make sure to set up this logic before `self.root = node`.

2.

Within the conditional statement:

``````grandparent = parent.parent
if parent.left == node:``````

create the following logic:

• If `parent` is to the left of the grandparent, use a `self._zig_zig()` operation calling `node`.
• Otherwise, use a `self._zag_zig()` operation calling `node`.

Note: if you press run before implementing your code, you will hit an infinite loop. If you hit an infinite loop and your code is not getting tested, hit the refresh button.

3.

Within the last `else` statement, implement the following logic:

• If `parent` is to the left of the grandparent, use a `self._zig_zag()` operation calling `node`.
• Otherwise, use a `self._zag_zag()` operation calling `node`.

Note: if you press run before implementing your code, you will hit an infinite loop. If you hit an infinite loop and your code is not getting tested, hit the refresh button.