Deletion in one-sided height balanced search trees

Abstract

We give an deletion algorithm for one-sided height balanced search trees of n nodes. Thus deletion appears to be simpler than insertion, since Hirschberg's insertion algorithm is .

Keywords:

• balanced
• binary
• search
• trees
• one-sided

C.R. Categories:

• 3.73
• 3.74
• 4.34
• 5.25
• 5.31

†Work carried out partially under a National Research Council of Canada Grant No. A-7700 and partially under the auspices of the Universities of Karlsruhe and Antwerpen.

†Work carried out partially under a National Research Council of Canada Grant No. A-7700 and partially under the auspices of the Universities of Karlsruhe and Antwerpen.

Notes

†Work carried out partially under a National Research Council of Canada Grant No. A-7700 and partially under the auspices of the Universities of Karlsruhe and Antwerpen.