$2$ A balanced binary$-$search tree

The elegance of red$-$black trees and splay trees may sometimes leave us with a sense of awe. How did they come up with such a nifty scheme to keep the binary search tree balanced? It is actually not that hard to balance a binary search tree. Many simple schemes can give us $(logn)$ amortized running time. They may be lacking in elegance, but quite easy to understand.

Consider the following scheme. First, we store at every node $x$ the number of items in the subtree rooted $x.$ This allows us to determine when the binary search tree becomes unbalanced. Let's define a node $x$ to be horribly unbalanced if the left subtree of $x$ has $5$ times the number of nodes than in its right subtree, or vice versa. All we will do in this scheme is to "fix up the subtree" if we detect that $x$ is horribly unbalanced.

Suppose that none of the nodes in a binary search tree $T$ with $n$ items is horribly unbalanced. Argue that the height of $T$ is $O(logn).$ Hint: use recursion$/$induction$.$

Suppose that during an insertion, we detect that some node $x$ is horribly unbalanced. We can fix the subtree rooted at $x$ by taking apart the subtree and adding every item from this subtree into a balanced tree that is as balanced as possible. Describe how to accomplish this re$-$balancing in $O(m)$ worst case actual time, where $m$ is the number of items in the subtree rooted at $x.$

Note: Do not use pseudocode to describe your algorithm. For example, if you want to sort some numbers in an array $A,$ just say "Sort the values in $A."$

When you a insert a new key $k,$ you may encounter several nodes that are horribly unbalanced nodes on the path from the root to where $k$ gets inserted. Where should you perform a re$-$balance first? at the horribly unbalanced node closest to the root? or closest to $k?$ Justify your response.

Devise an amortized analysis for this data structure using the accounting method. Your analysis must show that the amortized running time of insert and search are $O(logn).$

Note: You must state an invariant for your accounting scheme and argue that the invariant is maintained after each insert and search operation, including operations that perform re$-$balancing operations.