首页 | 本学科首页   官方微博 | 高级检索  
     检索      


An analytic approach for the analysis of rotations in fringe-balanced binary search trees
Authors:Alois Panholzer  Helmut Prodinger
Institution:(1) Institut für Algebra und Diskrete Mathematik, Technical University of Vienna, Wiedner Hauptstrasse 8-10, A-1040 Vienna, Austria
Abstract:This paper presents an analytic approach to the construction cost of fringe-balanced binary search trees. In 7], Mahmoud used a bottom-up approach and an urn model of Pólya. The present method is top-down and uses differential equations and Hwang's quasi-power theorem to derive the asymptotic normality of the number of rotations needed to construct such afringe balanced search tree. We also obtain the exact expectation and variance with this method. Although Pólya's urn model is no longer needed, we also present an elegant analysis of it based on an operator calculus as in 4].This research was supported by the Austrian Research Society (FWF) under the project number P12599-MAT.
Keywords:68P05
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号