Learn

You have now completed the necessary steps to represent a BTree in Python and can now move on to implementing the fundamental operations needed to leverage BTrees. We start first with an insert method. Insert has multiple steps in the general implementation, but we will first start with inserting values into nodes. First, we fill a BTree. We will only need to fill in the keys of the root element until it’s full. More specifically:

  • When we insert a new value, we first check if the root has space.
  • If so, and the root is a leaf, we can insert the value into the root.
  • To insert a value into a node, we need to make sure the keys stay in order, and thus we insert in order (don’t append and then sort).

For testing, we will set a high branching factor in this exercise, so all values are inserted into the root node. Here and in the coming exercises, we will split our implementation between the BTreeNode and BTree classes, so be aware of what is going where when implementing.

Instructions

1.

Start by implementing the add_key() method in BTreeNode, which takes in a value argument. Here, we need to make sure that when adding keys, they stay in ascending order.

To do this, our code will be as follows:

  • Iterate over the length of self.keys.
  • Check if value is less than the element in self.keys we are at.
  • If value is less than the element, insert value at the index of the element.
  • If this condition isn’t hit during the iteration, append value at the end of self.keys.
2.

Next, implement the initial insert() method in BTree. This function will be added too later, but for now, take in a value and add it to the root node using the root node’s add_key() method.

Click the hint if you feel stuck.

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?