A Linear Time Algorithm for Coding and Decoding Neville Codes

摘要

This paper studies the algorithms for coding and decoding second Neville's codes of a labeled tree. The algorithms for coding and decoding second Neville's codes of a labeled tree in the literatures require O(n log n) time usually. As stated in the literatures, no linear time algorithms for the second Neville's codes. In this paper we consider the second Neville's code problem in a different angle and a more direct manner. We start from a naive algorithm, then improved it gradually and finally we obtain a very practical linear time algorithm. The techniques we used in this paper are interesting themselves.