Fault tolerance and storage reduction in binary search trees

We introduce a method of representing a broad class of binary search trees in an environment in which pointers and other structural information may be “lost” or “maliciously altered.” The fault tolerant representation permits any 2 field changes to be detected and any 1 to be corrected without significantly increasing storage requirements of the binary tree. The detection and correction procedures applied to the entire tree require O(n) time. This discipline is also used to represent binary search trees with a single pointer per datum without altering the cost of searching or updating, if applied in conjunction with any underlying tree balancing scheme (bounded balance, etc.). If no balancing scheme is employed, the trees we form will have significantly shorter search paths than those formed using the straightforward algorithm