An Optimal Algorithm for Neville Codes of a Tree Network

This paper studies the algorithms for coding and decoding second Neville's codes of a tree network. 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, 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 used in this paper are interesting themselves.