gistfile1.cpp

        // We have to rebalance (we're left heavy).
        if (node->balance() == -1) {
            // Our actual balance right now is -2, but we do not update it yet for efficiency.

            // If our left child is balanced or left-heavy then we must rotate this node right.
            if (node->left()->balance() <= 0) {
                // First we recalculate the balances after the rotation.
                //
                // Our right subtree is now two smaller than the left subtree. This means that it's
                // one smaller than left()->left() since our left child isn't right-heavy.
                // left()->right()'s height is left()->balance() bigger than left()->left(). So we
                // can subtract out left()->left()'s height to get our new balance after the
                // rotation:
                //
                //     h = height(left()->left())
                //     balance(node) = (h - 1) - (h + left()->balance)
                //     balance(node) = -left()->balance - 1 
                //
                // Since left()->balance() was -1 or 0, our new balance will be -1 or 0, which
                // satisfies the AVL invariant.
                //
                node->set_balance(-node->left()->balance() - 1);

                // Now, our left child will become our new parent. We know our new height in terms
                // of height(left()->left()):
                //
                //     height(node) = max(h - 1, h + left()->balance())
                //
                // left()->balance can be 0 or -1, so the right term is always equal or larger,
                // giving us:
                //
                //     height(node) = h + left()->balance()
                // 
                // Since left()'s new children will be the old left()->left() and node, we can
                // subtract them:
                //
                //     balance(left()) = (h + left()->balance) - h
                //     balance(left()) = left()->balance()
                //
                // So no change is necessary.