Dynamic weighted binary search trees

Summary We present an algorithm which optimizes a weighted binary tree after an insertion or deletion. The resulting tree is nearly optimal. The algorithm needs O(n) space. In the case of an insertion the expected number of operations is equal to or less than the height of the tree. All results presented in this paper can also be found in [15].