An Analysis of the AVL Balanced Tree Insertion Algorithm
スポンサーリンク
概要
- 論文の詳細を見る
Mathematical analysis of the average behavior of the AVL balanced tree insertion algorithm has not ever been done completely. As the first step toward this analysis, we have proposed an approximate analysis based on the assumption that all AVL balanced trees with a given number of nodes and height are constructed with equal probability. In this paper, we propose a new analysis of the AVL balanced tree insertion algorithm in conformity with that all n! permutations of n keys occur with equal probability. First we derive the formulae to enumerate the number of permutations constructing the AVL balanced trees with a given number of nodes and height. Then, we propose the formulae to evaluate the average behavior of the AVL balanced tree insertion algorithm and show some results from the proposed formulae.
- 社団法人電子情報通信学会の論文
- 2003-05-01
著者
-
ITOKAWA Tsuyoshi
Graduate School of Science and Technology, Kumamoto University
-
Tada Akio
Graduate School Of Science And Technology Kumamoto University
-
NAKAMURA Ryozo
Department of ComputerScience, Faculty of Engineering, Kumamoto University
-
Nakamura Ryozo
Department Of Computer Science Faculty Of Engineering Kumamoto University
-
Nakamura Ryozo
Department Of Computerscience Faculty Of Engineering Kumamoto University
-
Itokawa Tsuyoshi
Graduate School Of Science And Technology Kumamoto University
関連論文
- Redundant TC Message Senders in OLSR
- An Analysis of the AVL Balanced Tree Insertion Algorithm
- Severity of Neurological Disorders in Elderly Residents of a Farming Town in Kyushu, Japan; Prevalence of Disability in Activities of Daily Living
- Redundant TC Message Senders in OLSR
- An Approximate Analysis of the AVL Balanced Tree Insertion Algorithm(Special Issue on Generation Database Technology for Internet, Multimedia and Mobile computing)
- A New Analysis of Hashing Algorithm for External Searching
- An Alternative Analysis of Linear Probing Hashing with Buckets
- An Alternative Analysis of Dynamic Hashing Algorithms
- An Alternative Analysis of the Algorithm for Separate Chaining Technique of the Hashing Method
- A New Analysis of Tree Hashing Algorithm
- BS-4-18 A Comparison of Mesh and Tree-Based Multicast Routing Protocols for VANETs(BS-4. Network Design, Management and Control for Future Networked Systems)
- An Alternative Analysis of Linear Dynamic Hashing Algorithm
- An Alternative Analysis of the Algorithm for Separate Chaining Technique of the Hashing Method