@inproceedings{DBLP:conf/pods/MunroP83, author = {J. Ian Munro and Patricio V. Poblete}, title = {A Discipline for Robustness or Storage Reduction in Binary Search Trees}, booktitle = {Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983, Colony Square Hotel, Atlanta, Georgia}, publisher = {ACM}, year = {1983}, isbn = {0-89791-097-4}, pages = {70-75}, ee = {http://doi.acm.org/10.1145/588058.588069, db/conf/pods/MunroP83.html}, crossref = {DBLP:conf/pods/83}, bibsource = {DBLP, http://dblp.uni-trier.de} }BibTeX
We develop a method of representing binary search trees in an environment in which pointers and other structural information may be "lost" or "maliciously altered". Our fault tolerant representation permits any 2 field changes to be detected and any 1 to be corrected without significantly increasing to storage requirements of the binary tree. The detection and correction procedures applied to the entire tree require O(n) time.
Our discipline is also used to represent binary search trees with a single pointer per datum without altering the cost of searching or updating. While our scheme can be applied in conjunction with any underlying tree balancing scheme ([AVL], bounded balance [Nievergelt et al.] etc.), if no balancing scheme is employed, the trees we form will have significantly shorter search paths than those formed using the straightforward algorithm.
Copyright © 1983 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.