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.

Sign up to start coding

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?