Overview / Logistics

As we discussed, it's possible for BSTs to be unbalanced depending on the order that we insert the nodes. By contract, a balanced tree has height at most ceil(log₂(N)) for N nodes. We can perform an operation called a tree rotation to rebalance an unbalanced tree without changing the order that inorder traverses the nodes. A picture is shown below

Let's work on implementing tree rotations in code, and we'll see if we can balance a tree manually. Click here to download the starter code. A method to do a left rotation has been filled in for you. You should fill in the method to to a right rotation. Then, you can experiment with different rotations in the tree_rotation_example method to balance the tree. This method has a dictionary filled in so you can quickly jump to nodes with a particular key. For example, we start with this tree:

And then we run this code, which saves the rotated tree as an image

We get this

Notice how there's some code to verify that this is still in order after the rotation.

Next, run this code

And get the following result

You should keep going until your tree has a maximum height of 5, since there are 25 nodes, and ceil(log₂(25)) = 5

---

Edge Flip

A binary tree corresponds to a triangulation of a convex polygon. In this context, a tree rotation is an edge flip