参考文献:1. Sleator, D., Tarjan, R.: Self-adjusting binary search trees. JACM聽32(3), 652鈥?86 (1985) CrossRef
作者单位:Stefan Schmid (17) Chen Avin (18) Christian Scheideler (19) Bernhard Haeupler (20) Zvi Lotker (18)
17. TU Berlin & T-Labs, Germany 18. BGU, Israel 19. U. Paderborn, Germany 20. MIT, USA
文摘
This paper initiates the study of self-adjusting distributed data structures or networks. In particular, we present SplayNets: a binary search tree based network that is self-adjusting to the routing requests. We derive entropy bounds on the amortized routing cost and show that our splaying algorithm has some interesting properties.