Rotation Algorithms for Balancing Search Trees

Abstract

A search tree is a data structure constructed from a minimum spanning tree. This data structure is used for determining the cluster membership of a query instance clustered by a similarity-guaranteed clustering algorithm. According to the line topology of a search tree in the worst case, the time complexity of tree traversing is O(n) where n is the number of nodes of the tree. Unfortunately, the AVL tree algorithm cannot solve this problem because the algorithm is unable to maintain the hierarchical structure of a search tree. From the definition of balance factor, our proposed algorithm is designed to rotate nodes until the tree becomes balanced while maintaining the hierarchical structure. Consequently, the balanced search tree achieves the optimal time complexity of O(log n) for the searching purpose.