Abstract
We introduce a self-stabilizing data structure, which we call either a min-max search tree or a max-min search tree (both abbreviated M2ST), depending on whether the root has the minimum or the maximum value in the tree. Our structure is a refinement of the standard min-max heap (or max-min heap), with additional property that every value in the left subtree of a node is less than or equal to every value in the right subtree of that node. The M 2 ST has all the power of a binary search tree and all the power of a min-max heap, combined; with the additional feature that maintaining balance is easy. We give a self-stabilizing algorithm for reorganizing the values of an asynchronous network with a binary tree topology into an M2ST in O(n) rounds. We then give an algorithm for reorganizing an asynchronous network with a binary tree topology, which is already in M 2 ST order, into binary search tree order in O(h) rounds. This result answers an open problem posed in [3].
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arvind, A., Rangan, C.P.: Symmetric min-max heap: a simpler data structure for double-ended priority queue. Information Processing Letters 69, 197–199 (1999)
Atkinson, M.D., Sack, J.R., Santoro, B., Strothotte, T.: Min-max heaps and generalized priority queues. Communications of the ACM 29(10), 996–1000 (1986)
Bein, D., Datta, A.K., Villain, V.: Snap-stabilizing optimal binary search tree. In: Tixeuil, S., Herman, T. (eds.) SSS 2005. LNCS, vol. 3764, pp. 1–17. Springer, Heidelberg (2005)
Carlsson, S.: The deap: - a double-ended heap to implement double-ended priority queues. Information Processing Letters 26, 33–36 (1987)
Dijkstra, E.W.: Self stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery 17, 643–644 (1974)
Ding, Y., Weiss, M.A.: The relaxed min-max heap. Acta Informatica 30, 215–231 (1993)
Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)
Dolev, S., Israeli, A., Moran, S.: Uniform dynamic self-stabilizing leader election. IEEE Transactions on Parallel and Distributed Systems 8(4), 424–440 (1997)
Herman, T., Masuzawa, T.: Available stabilizing heaps. Information Processing Letters 77, 115–121 (2001)
Herman, T., Masuzawa, T.: A stabilizing search tree with availability properties. In: Fifth International Symposium on Autonomous Decentralized Systems (ISADS 2001), pp. 398–405 (2001)
Herman, T., Pirwani, I.: A composite stabilizing data structure. In: Datta, A.K., Herman, T. (eds.) WSS 2001. LNCS, vol. 2194, pp. 167–182. Springer, Heidelberg (2001)
Koong, C.M., Leong, H.W.: Double-ended binomial queues. In: Proceedings of ISAAC, pp. 128–137 (1993)
Makris, C., Tsakalidis, A., Tsichlas, K.: Reflected min-max heaps. Information Processing Letters 86(4), 209–214 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bein, D., Datta, A.K., Larmore, L.L. (2006). On Self-stabilizing Search Trees. In: Dolev, S. (eds) Distributed Computing. DISC 2006. Lecture Notes in Computer Science, vol 4167. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11864219_6
Download citation
DOI: https://doi.org/10.1007/11864219_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44624-8
Online ISBN: 978-3-540-44627-9
eBook Packages: Computer ScienceComputer Science (R0)