Encoding a Binary Search Tree in Constant Time on BSR
Limin Xiang, Kai Cheng, Kazuo Ushijiam · 2005
Constant time solutions on BSR can be found in the literature to many applications, such as parenthesis matching, tree decoding, tree reconstruction, and etc. However, the problem of encoding a tree in constant time on BSR is still open. In this paper, some properties will be discussed on binary search trees and the i-p sequence, and based on the properties, a constant time algorithm on BSR is proposed for encoding a binary search tree into its i-p sequence, which is the first constant time solution to the problem on any model of computation.