On Self-stabilizing Search Trees | SpringerLink
Skip to main content

On Self-stabilizing Search Trees

  • Conference paper
Distributed Computing (DISC 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4167))

Included in the following conference series:

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.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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)

    Article  MATH  MathSciNet  Google Scholar 

  2. 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)

    Article  MATH  Google Scholar 

  3. 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)

    Chapter  Google Scholar 

  4. Carlsson, S.: The deap: - a double-ended heap to implement double-ended priority queues. Information Processing Letters 26, 33–36 (1987)

    Article  MathSciNet  Google Scholar 

  5. Dijkstra, E.W.: Self stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery 17, 643–644 (1974)

    MATH  Google Scholar 

  6. Ding, Y., Weiss, M.A.: The relaxed min-max heap. Acta Informatica 30, 215–231 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  7. Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)

    MATH  Google Scholar 

  8. Dolev, S., Israeli, A., Moran, S.: Uniform dynamic self-stabilizing leader election. IEEE Transactions on Parallel and Distributed Systems 8(4), 424–440 (1997)

    Article  Google Scholar 

  9. Herman, T., Masuzawa, T.: Available stabilizing heaps. Information Processing Letters 77, 115–121 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  10. 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)

    Google Scholar 

  11. 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)

    Chapter  Google Scholar 

  12. Koong, C.M., Leong, H.W.: Double-ended binomial queues. In: Proceedings of ISAAC, pp. 128–137 (1993)

    Google Scholar 

  13. Makris, C., Tsakalidis, A., Tsichlas, K.: Reflected min-max heaps. Information Processing Letters 86(4), 209–214 (2003)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics