BINAR QIDIRUV DARAXTLARI
Abstract
Bu maqolada ikkilik qidiruv daraxtlarining o‘z-o‘zini moslashtiruvchi turi bo‘lgan "splay daraxt" ishlab chiqilib, tahlil qilingan. Ikkilik qidiruv daraxtlari ma’lumotlar ro‘yxatini tuzishda foydalaniladi va unda ma’lumotlarga kirish, ularni kiritish va o‘chirish jarayonlari qulay amalga oshiriladi. n tugundan iborat splay daraxtida har bir operatsiya amortizatsiya qilingan vaqtda O(log n) murakkablikka ega. Bunda "amortizatsiya qilingan vaqt" deganda eng yomon holatdagi operatsiyalar ketma-ketligi uchun o‘rtacha vaqt tushuniladi. Shunday qilib, splay daraxtlar umumiy ishlash vaqti nuqtai nazaridan balanslangan daraxtlar kabi samarali hisoblanadi. Bundan tashqari, splay daraxtlar uzoq vaqt davomida ishlaganda statik optimal qidiruv daraxtlar kabi samarali bo‘lib, ular oddiy qayta tuzish usuli orqali ishlaydi. Bu usul har safar daraxtdan foydalanilganda qo‘llaniladigan "splaying" deb nomlangan oddiy qayta tuzish mexanizmini o‘z ichiga oladi.
References
1. GUIBAS, L.G., MCCREIC;HT, E.M., PLASS, M.F., AND ROBERTS, J.R. A new representation for linear lists. In Proceedings ofthe 9th Symposium on Theory of Computing (Boulder Colo., May 2-4). ACM, New York, 1977, pp. 49-60.
2.GOTING, H., AND KRIEGEL, H.P. Multidimensional B-tree: An efficient dynamic file structure for exact match queries. In Proceedings of the 10th Gesellschaft fir Informatik Annual Conference. Informatik-Fachberichte, vol. 33. Springer-Verlag, New York, 1980, pp. 375-388.
3.Hu, T.C., AND TUCKER, A.C. Optimal computer-search trees and variable-length alphabetic codes. SIAM J. Appl. Math. 37 (1979), 246-256.
4. HUDDLESTON, S. An improved bound on the performance of self-adjusting search trees. Unpub lished research note, Computer Science Dept., Univ. of California, Irvine, Calif., 1983.
5. HUDDLESTON, S., AND MEHLHORN, K. Robust balancing in B-trees. In Theoretical Computer
Science: 5th G&Conference (Karlseuhe, West Germany, March 23-25). Lecture Notes in Computer
Science, vol. 104. Springer-Verlag, Berlin, 1981, pp. 234-244.
6. HUDDLESTON, S., AND MEHLHORN, K. A new data structure for representing sorted lists. Acta Zn?
17(1982), 157-184.
7. KNUTH, D.E. Optimum binary search trees. Acta Inf 1 (197 I), 14-25.
8 . KNUTH, D.E. The Art of Computer Programming. Vol. 1, Fundamental Algorithms, 2nd ed.
Addison-Wesley, Reading, Mass., 1973.
9. KNUTH, D.E. The Art of Computer Programming. Vol. 3, Sorting and Searching. Addison-Wesley,
Reading, Mass., 1973.
10. KOSARAJU, S.R. Localized search in sorted lists. In Proceedings of the 13th Annual ACM Sympo
sium on Theory of Computing (Milwaukee, Wis., May I l-l 3). ACM, New York, I98 1, pp. 62-69.
11. MAIER, D., AND SALVETER, S. Hysterical B-trees. Inf: Proc. Lett. 12 (198 I), 199-202.
