On deletion in threaded binary trees |
| |
| Affiliation: | 1. Department of Human Genetics, Radboud University Medical Center, P.O. Box 9100, 6500 HB, Nijmegen, the Netherlands;2. Donders Institute for Brain, Cognition and Behaviour, P.O. Box 9104, 6500 HE Nijmegen, the Netherlands;3. Department of Special Education: Cognitive and Motor Disabilities, Utrecht University, Heidelberglaan 1, 3584 CS, Utrecht, the Netherlands;4. Department of Psychology, University of Amsterdam, Nieuwe Achtergracht 129-B, 1018 WT Amsterdam, The Netherlands;5. Behavioural Science Institute, Radboud University, P.O. Box 9104, 6500 HE Nijmegen, the Netherlands;1. Centre for Microbial Ecology and Genomics, University of Pretoria, 0028, South Africa;2. Department of Genetics, University of Pretoria, 0028, South Africa;3. Department of Microbiology, University of Pretoria, 0028, South Africa;4. Bioinformatics & Systems Biology, Justus-Liebig-University Giessen, 35392 Giessen, Hesse, Germany |
| |
| Abstract: | We determine the explicit performance of deletion algorithms which have to maintain threads in a binary tree. In particular, it is shown that the cost of threads on deletion is not as high as might be expected, and is especially low for right-threaded trees. The results are obtained by using recurrences to compute the average cost of deleting a single node from both threaded and unthreaded trees. As an illustration of the technique, a new derivation of the average cost of insertion into binary search trees is presented. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
