rebalance(t):
|  Input  tree t with n nodes
|  Output t rebalanced
|
|  if n≥3 then
|  |  t=partition(t,n/2)         // put node with median key at root
|  |  left(t)=rebalance(left(t))  // then rebalance each subtree
|  |  right(t)=rebalance(right(t))
|  end if
|  return t