Reja qidiruv binar daraxti tushunchasi

11- MAVZU Qidiruv binar daraxti. Qidiruv binar daraxtini qurish. Tugunlar qo‘shish va o‘chirish .

REJA

Qidiruv binar daraxti tushunchasi

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