The most important methods for balancing search trees are periodical rebuilding of the whole tree, which takes Omega(N) time, and rebalancing the tree during each update operation, in O(log N) time. Recently, a new method called relaxed balancing has been proposed in which balancing and updates are uncoupled. Updates only leave balance information in the tree, thus enabling rebalancing later. In this paper, new algorithms for updating and rebalancing the tree, based on using the relaxed balance information, are given. It is shown that if M updates are performed in a red-black tree with N keys, the tree can be rebalanced in O(M log(N+M)) time. If the tree is originally empty, the rebalancing is performed in O(M) time.