Learn

Inserting into a splay tree is similar to inserting into a regular binary search tree. First, we need to identify the correct location in the tree to add the new node. Once the new node is inserted, we splay that node to make it the root.

Let’s implement this logic in Python.

Instructions

1.

We have laid out the following starter code in insert():

new_node = Node(value) current_node = self.root if current_node is None: self.root = new_node return last_parent = None while current_node is not None and current_node.value != new_node.value: last_parent = current_node break # Checkpoint 1 # Checkpoint 2 new_node.parent = last_parent

Within the while loop, implement the following logic:

  • If the value of the new node is less than or equal to the value of the current node, set the current node to the next node on the left (traverse to the left).
  • Otherwise, set the current node to the next node on the right (traverse to the right).

Make sure to delete the break statement.

2.

Below new_node.parent = last_parent, implement the following logic:

  • If the value of the new node is less than the value of the last parent, set last_parent.left equal to new_node.
  • If the value of the new node is greater than the value of the last parent, set last_parent.right equal to new_node.

After this, splay the new node to make it the root.

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?