Efficient Algorithm for Balancing Binary Search Trees

摘要

Balancing binary search trees is a fundamental task, when efficient dictionaryoperations are implemented. However, there are situations when efficiency or concurrency requirements set up such restrictions that the rebalancing must be postponed until a more peaceful time. Currently this means that the tree has to be rebalanced globally, which takes time O(N). The author presents a new algorithm that performs this delayed rebalancing more efficiently. It traverses only the modified branches of the tree and runs in O(Mlog(N+M)) time, where N is the number of nodes in the tree and M is the number of updates performed in the tree. The algorithm is based on using chromatic search trees and requires at most one byte per node extra storage for the information about the performed updates and the needs for rebalancing.