Splaying in the Implementation of the Link/cut Tree Operations Used in Solving the Maximum Flow Problem

Abstract

This study is concerned with the analysis of the splaying operation, which moves a certain node in a tree all the way up the tree to become the new root. Splaying is an operation on a self-adjusting data structure called the Splay tree. New methods are suggested to perform top-down restructuring of splay trees when moving a given node to the root providing faster and simpler algorithms. The splaying operation is used in implementing the link/cut tree operations thus solving the linking and cutting trees problem in an amortized time bound of O<log2n> per tree operation. Finally, the use of the link/cut tree in solving the maximum flow problem giving an algorithm of O(n*m*log2n) is illustrated to give a precise idea of how this powerful data structure can be applied.