Robert Manson Sawko, Malgorzata Zimon
SIAM/ASA JUQ
iR trees are parameterized binary search trees which rebalance themselves locally. In our previous work the cases for i=1, 2 were studied. This note extends the result to arbitrary i. In particular, we derive a formula for the average number of rotations/reorganizations involved in an insertion and consequently a formula for the average number of comparisons for a successful search in iR trees. © 1984 BIT Foundations.
Robert Manson Sawko, Malgorzata Zimon
SIAM/ASA JUQ
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
Heng Cao, Haifeng Xi, et al.
WSC 2003
Tong Zhang, G.H. Golub, et al.
Linear Algebra and Its Applications