|
Reja qidiruv binar daraxti tushunchasi
|
səhifə | 1/4 | tarix | 30.12.2023 | ölçüsü | 11,58 Kb. | | #167120 |
| 4gY1tIJRbr61EFKVy52ED6yB5b74D6XlEA6kx92R 11- MAVZU Qidiruv binar daraxti. Qidiruv binar daraxtini qurish. Tugunlar qo‘shish va o‘chirish . REJA Qidiruv binar daraxtini qurish. Binar daraxtda qidiruv, tugunlar qo‘shish va o‘chirish Asosiy adabiyotlar ro‘yxati - Alfred V. Axo., Djon E. Xopkroft, Djefri D. Ulman. Struktura dannыx i algoritmы//Ucheb.pos., M. : Izd.dom: "Vilyams", 2000, — 384 s.
- Baknell Djulian M. Fundamentalnыe algoritmы i strukturы dannыx v Delphi//SPb: OOO «DiaSoftYUP», 2003. 560s.
- Robert Sedjvik. Fundamentalnыe algoritmы na C++. Analiz, Strukturы dannыx, Sortirovka, Poisk//K.: Izd. «DiaSoft», 2001.- 688 s.
- Dinman M.I. S++. Osvoy na primerax//SPB.:BXV-Peterburg, 2006, 384.
- SHildt, Gerbert. Polnыy spravochnik po S#//M. : Izd. dom "Vilyamc", 2004, 752 s.
- Virt N. Algoritmы i strukturы programmы//M., Mir, 1985.
Agar ajratib olingan elementlar qandaydir o’zgarmas to’plamni tashkil qilishsa, kelgusi qidiruvlar samaraliroq bo’lishi uchun ularni binar daraxt ko’rinishida ifodalash maqsadga muvofiq bo’lishi mumkin. - Quyida keltirilgan daraxtlarda binar qidiruvni ko’rib chiqaylik ( a)va b) chizma). Ikkala daraxt xam uchtadan elementga ega - k1, k2, k3 bo’lib, bu yerda k1. k3 elementni qidirish a) chizmada ikkita taqqoslashni talab qilsa, b) chizmada esa bitta ( bunda u ildizning kaliti).
Mantiqiy bosqich
Faraz qilaylik:
qidiruv argumenti key = k1 bo’lishi extimolligi - p1,
qidiruv argumenti key = k2 bo’lishi extimolligi – p3,
qidiruv argumenti key = k3 bo’lishi extimolligi – p3,
key < k1 bo’lishi extimolligi – q0,
k2 > key > k1 bo’lishi extimolligi – q1,
k3 > key > k2 bo’lishi extimolligi – q2,
key > k3 bo’lishi extimolligi – q3,
C1 - a) chizmadagi taqqoslashlar soni,
C2 - b) chizmadagi taqqoslashlar soni.
U holda p1+p2+p3+q0+q1+q2+q3 = 1
Dostları ilə paylaş: |
|
|