Binar qidiruv daraxtlari
Ikkilik qidiruv daraxti - bu ikkilik daraxt bo‘lib, unda har bir tugunning chap bolasi pastroq qiymatga ega va har bir tugunning o‘ng qismi yuqoriroq qiymatga ega.
Ikkilik qidiruv daraxtlarining aniq afzalligi shundaki, qidirish, o‘chirish va kiritish kabi operatsiyalar tezkor va xotiradagi qiymatlarni o‘zgartirmasdan amalga oshiriladi.
Ikkilik qidiruv daraxtlari
Ikkilik qidiruv daraxti (BST) — bu ikkilik daraxt ma’lumotlar tuzilmasining bir turi bo‘lib, unda daraxtdagi istalgan "X" tugun uchun quyidagi shartlar bajarilishi shart:
- X tugunining chap bolasi va uning barcha avlodlari (bolalar, bolalar bolalari va boshqalar) X qiymatidan pastroq qiymatlarga ega.
- To‘g‘ri bola va uning barcha avlodlari X qiymatidan yuqori qiymatlarga ega.
- Chap va o‘ng pastki daraxtlar ham Ikkilik qidiruv daraxtlari bo‘lishi kerak.
Bu xususiyatlar oddiy ikkilik daraxtga qaraganda qiymatlarni qidirish, qo‘shish va o‘chirishni tezroq qiladi.
Buni iloji boricha tushunish va amalga oshirishni osonlashtirish uchun, keling, ikkilik qidiruv daraxtidagi barcha qiymatlar noyob deb faraz qilaylik.
Daraxtning o‘lchami - undagi tugunlar soni (n).
Pastki daraxt mahalliy ildiz sifatida daraxtdagi tugunlardan biri bilan boshlanadi va shu tugun va uning barcha avlodlaridan iborat.
Tugunning avlodlari bu tugunning barcha asosiy tugunlari va ularning barcha tugunlari va boshqalar. Shunchaki tugun bilan boshlang va avlodlar ushbu tugun ostida bog‘langan barcha tugunlar bo‘ladi.
Tugunning balandligi - bu tugun va barg tugunlari orasidagi maksimal qirralarning soni.
Tugunning tartibli vorisi, agar biz tartibli o‘tishni amalga oshirsak, undan keyin keladigan tugundir. Yuqoridagi BST ning tartibli o‘tishi 13-tugun 14-tugundan oldin kelishiga olib keladi va shuning uchun 13-tugunning vorisi 14-tugun bo‘ladi.
Ikkilik qidiruv daraxtining o‘tishi
Bizning oldimizda ikkilik qidiruv daraxti ma’lumotlar strukturasi mavjudligini tasdiqlash uchun biz ushbu sahifaning yuqori qismidagi xususiyatlar to‘g‘ri yoki yo‘qligini tekshirishimiz mumkin. Shunday qilib, yuqoridagi rasmdagi har bir tugun uchun tugunning chap tomonidagi barcha qiymatlar pastroq yoki o‘ngdagi barcha qiymatlar yuqoriroq ekanligini tekshiring.
Ikkilik daraxtning BST ekanligini tekshirishning yana bir usuli - bu tartib bo‘yicha o‘tish (oldingi sahifada qilganimiz kabi) va natijada olingan qiymatlar ro‘yxati ortib borayotgan tartibda yoki yo‘qligini tekshirish.
Quyidagi kod yuqoridagi rasmdagi Ikkilik qidiruv daraxtining o‘tish bilan amalga oshirilishidir.
Misol
Pythonda ikkilik qidiruv daraxtining o‘tishi
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
root = TreeNode(13)
node7 = TreeNode(7)
node15 = TreeNode(15)
node3 = TreeNode(3)
node8 = TreeNode(8)
node14 = TreeNode(14)
node19 = TreeNode(19)
node18 = TreeNode(18)
root.left = node7
root.right = node15
node7.left = node3
node7.right = node8
node15.left = node14
node15.right = node19
node19.left = node18
# Traverse
inOrderTraversal(root)
Misolni ishga tushirish »
Yuqoridagi kod misolini ishga tushirish orqali ko‘rib turganimizdek, tartib bo‘yicha o‘tish o‘sish (o‘sish) tartibida raqamlar ro‘yxatini hosil qiladi, bu ikkilik daraxt ikkilik qidiruv daraxti ekanligini anglatadi.
BSTda qiymatni qidiring
BSTda qiymatni izlash massivda Ikkilik qidiruv yordamida qiymatni qanday topishimizga juda o‘xshaydi.
Ikkilik qidiruv ishlashi uchun massiv allaqachon tartiblangan bo‘lishi kerak va massivdagi qiymatni qidirish juda tez bajarilishi mumkin.
Xuddi shunday, BSTda qiymatni qidirish ham tugunlar qanday joylashtirilganligi sababli juda tez bajarilishi mumkin.
Qanday ishlaydi:
- Ildiz tugunidan boshlang.
- Agar bu biz izlayotgan qiymat bo‘lsa, qaytaring.
- Agar biz izlayotgan qiymat yuqoriroq bo‘lsa, o‘ng pastki daraxtda qidirishni davom eting.
- Agar biz izlayotgan qiymat pastroq bo‘lsa, chap pastki daraxtda qidirishni davom eting.
- Agar biz qidirmoqchi bo‘lgan pastki daraxt mavjud bo‘lmasa, dasturlash tiliga qarab, qiymat BST ichida emasligini ko‘rsatish uchun
NoneyokiNULLyoki shunga o‘xshash narsani qaytaring.
Algoritmni quyidagicha amalga oshirish mumkin:
Misol
Daraxtdan "13" qiymatini qidiring
def search(node, target):
if node is None:
return None
elif node.data == target:
return node
elif target < node.data:
return search(node.left, target)
else:
return search(node.right, target)
# Search for a value
result = search(root, 13)
if result:
print(f"Found the node with value: {result.data}")
else:
print("Value not found in the BST.")
Misolni ishga tushirish »
Qiymat uchun BST ni qidirishning vaqt murakkabligi O(h), bu yerda h - daraxt balandligi.
Masalan, o‘ng tomonda tugunlari ko‘p bo‘lgan BST uchun daraxtning balandligi kerak bo‘lganidan kattaroq bo‘ladi va eng yomon holatni qidirish uzoq davom etadi. Bunday daraxtlar muvozanatsiz deb ataladi.
Yuqoridagi ikkala Ikkilik qidiruv daraxtlari ham bir xil tugunlarga ega va ikkala daraxtning ketma-ket o‘tishi bizga bir xil natijani beradi, lekin balandligi juda farq qiladi. Yuqoridagi muvozanatsiz daraxtni qidirish ko‘proq vaqt talab etadi, chunki u balandroq.
Keyingi sahifadan AVL Trees deb nomlangan Ikkilik daraxt turini tasvirlash uchun foydalanamiz. AVL daraxtlari o‘z-o‘zini muvozanatlashtiradi, ya’ni qidiruv, kiritish va o‘chirish kabi operatsiyalar kamroq vaqt talab qilishi uchun daraxtning balandligi minimal bo‘ladi.
BST ga tugunni kiriting
BST ga tugunni kiritish qiymatni qidirishga o‘xshaydi.
Qanday ishlaydi:
- Ildiz tugunidan boshlang.
- Compare each node:
- Qiymat pastroqmi? Chapga boring.
- Qiymat yuqoriroqmi? O‘ngga boring.
- Taqqoslash uchun o‘ng yoki chap bo‘lmaguncha tugunlarni yangi qiymat bilan solishtirishda davom eting. Aynan shu erda yangi tugun kiritilgan.
Yuqorida aytib o‘tilganidek, tugunlarni kiritish kiritilgan tugun har doim yangi barg tuguniga aylanishini anglatadi.
BSTdagi barcha tugunlar noyobdir, shuning uchun biz kiritmoqchi bo‘lgan qiymat bilan bir xil qiymatni topsak, biz hech narsa qilmaymiz.
BST-ga tugunni kiritish shu tarzda amalga oshirilishi mumkin:
Misol
BST ga tugunni kiritish:
def insert(node, data):
if node is None:
return TreeNode(data)
else:
if data < node.data:
node.left = insert(node.left, data)
elif data > node.data:
node.right = insert(node.right, data)
return node
# Inserting new value into the BST
insert(root, 10)
Misolni ishga tushirish »
BST pastki daraxtidagi eng past qiymatni toping
Keyingi bo‘limda BSTdagi tugunni qanday o‘chirishimiz mumkinligi tushuntiriladi, ammo buning uchun bizga tugunning pastki daraxtida eng past qiymatni topadigan funksiya kerak bo‘ladi.
Qanday ishlaydi:
- Pastki daraxtning ildiz tugunidan boshlang.
- Iloji boricha chapga boring.
- Siz yakunlagan tugun bu BST pastki daraxtidagi eng past qiymatga ega tugundir.
BST tugunining pastki daraxtidagi eng past qiymatni topish funksiyasi quyidagicha ko‘rinadi:
Misol
BST pastki daraxtidagi eng past qiymatni toping
def minValueNode(node):
current = node
while current.left is not None:
current = current.left
return current
# Find Lowest
print("\nLowest value:",minValueNode(root).data)
Misolni ishga tushirish »
Quyidagi bo‘limda biz ushbu minValueNode() funksiyasidan tugunning o‘rinbosarini topish va tugunni o‘chirish uchun foydalanamiz.
BSTdagi tugunni o‘chirish
Tugunni o‘chirish uchun bizning funksiyamiz avval uni topish uchun BSTni qidirishi kerak.
Tugun topilgandan so‘ng, tugunni o‘chirish boshqacha bajarilishi kerak bo‘lgan uch xil holat mavjud.
Qanday ishlaydi:
- Agar tugun barg tugun bo‘lsa, unga havolani olib tashlash orqali uni olib tashlang.
- Agar tugun faqat bitta tugunga ega bo‘lsa, o‘chirmoqchi bo‘lgan tugunning ota-ona tugunini shu tugunga ulang.
- Agar tugun o‘ng va chap tugunlarga ega bo‘lsa: Tugunning navbatdagi vorisini toping, ushbu tugun bilan qiymatlarni o‘zgartiring, keyin uni o‘chiring.
Yuqoridagi 3-bosqichda biz topadigan voris har doim barg tugun bo‘ladi va u biz o‘chirmoqchi bo‘lgan tugundan so‘ng keladigan tugun bo‘lgani uchun biz u bilan qiymatlarni almashtirishimiz va uni o‘chirishimiz mumkin.
BST tugunni o‘chirish funksiyasi bilan shunday amalga oshirilishi mumkin:
Misol
BSTdagi tugunni o‘chirish
def delete(node, data):
if not node:
return None
if data < node.data:
node.left = delete(node.left, data)
elif data > node.data:
node.right = delete(node.right, data)
else:
# Node with only one child or no child
if not node.left:
temp = node.right
node = None
return temp
elif not node.right:
temp = node.left
node = None
return temp
# Node with two children, get the in-order successor
node.data = minValueNode(node.right).data
node.right = delete(node.right, node.data)
return node
# Delete node 15
delete(root,15)
Misolni ishga tushirish »
1-qator: Bu yerdagi node argumenti biz o‘chirmoqchi bo‘lgan data bilan nodeni qidirishda kichikroq va kichikroq pastki daraxtlarda funksiya o‘zini rekursiv chaqirishiga imkon beradi.
2-8 qator: Bu biz o‘chirmoqchi bo‘lgan to‘g‘ri data tugunni qidirmoqda.
9-22-qator: Biz o‘chirmoqchi bo‘lgan tugun topildi. Bunday uchta holat mavjud:
- 1-holat: Tugun tugunlari bo‘lmagan tugun (barg tugun).
Noneqaytariladi va bu rekursiya orqali ota-tugunning yangi chap yoki o‘ng qiymatiga aylanadi (6 yoki 8-qator). - 2-holat: Chap yoki o‘ng tugunli tugun. Ushbu chap yoki o‘ng tugun rekursiya orqali ota-onaning yangi chap yoki o‘ng bolasiga aylanadi (7 yoki 9-qator).
- 3-holat: Tugun chap va o‘ng tugunlarga ega. Tartibdagi voris
minValueNode()funksiyasi yordamida topiladi. Biz merosxo‘rning qiymatini o‘chirmoqchi bo‘lgan tugunning qiymati sifatida o‘rnatib, ushlab turamiz va keyin biz merosxo‘r tugunni o‘chirib tashlashimiz mumkin.
24-qator:noderekursiv funksiyani saqlab qolish uchun qaytariladi.
Boshqa ma’lumotlar tuzilmalari bilan solishtirganda BST
Ikkilik qidiruv daraxtlari ikkita boshqa ma’lumotlar tuzilmasidan eng yaxshisini oladi: massivlar va bog‘langan listlar.
| Data Structure | Qiymatni qidirish | O‘chirish / qo‘shish xotirada siljishga olib keladi |
|---|---|---|
| Sorted Array | O(\log n) |
Ha |
| Linked List | O(n) |
No |
| Binary Search Tree | O(\log n) |
No |
BSTni qidirish massivdagi Ikkilik qidiruv kabi tez va bir xil vaqt murakkabligi O(log n).
Va yangi qiymatlarni o‘chirish va kiritish, xuddi bog‘langan listlar kabi xotiradagi elementlarni o‘zgartirmasdan amalga oshirilishi mumkin.
BST balansi va vaqt murakkabligi
Ikkilik qidiruv daraxtida yangi tugun qo‘shish, tugunni o‘chirish yoki tugunni qidirish kabi operatsiyalar aslida O(h)hisoblanadi. Bu shuni anglatadiki, daraxt (h) qanchalik baland bo‘lsa, operatsiya shunchalik uzoq davom etadi.
Yuqoridagi jadvalda qiymatni qidirish O(log n) deb yozganimizning sababi, agar daraxt quyidagi rasmdagi kabi "muvozanatlangan" bo‘lsa, bu to‘g‘ri bo‘ladi.
Biz bu daraxtni muvozanatli deb ataymiz, chunki daraxtning chap va o‘ng tomonida taxminan bir xil miqdordagi tugunlar mavjud.
Ikkilik daraxtning muvozanatli ekanligini aniqlashning aniq usuli shundaki, har qanday tugunning chap va o‘ng pastki daraxtlarining balandligi faqat bitta bilan farqlanadi. Yuqoridagi rasmda ildiz tugunining chap pastki daraxtining balandligi h=2 va o‘ng pastki daraxtning balandligi h=3ga ega.
Ko‘p sonli tugunlarga (katta n) ega bo‘lgan muvozanatli BST uchun biz h ≈ \log_2 n balandligini olamiz va shuning uchun tugunni qidirish, o‘chirish yoki kiritish uchun vaqt murakkabligi O(h) = O(\log n) sifatida yozilishi mumkin.
Ammo, agar BST butunlay muvozanatsiz bo‘lsa, quyidagi rasmda bo‘lgani kabi, daraxtning balandligi taxminan tugunlar soni bilan bir xil bo‘ladi,h ≈ n va biz tugunni qidirish, o‘chirish yoki kiritish uchun O(h) = O(n) vaqt murakkabligini olamiz.
Shunday qilib, BSTda operatsiyalarni optimallashtirish uchun balandlikni minimallashtirish kerak va buning uchun daraxt muvozanatli bo‘lishi kerak.
Ikkilik qidiruv daraxtini muvozanatli saqlash AVL daraxtlari aynan shunday qiladi, bu keyingi sahifada tushuntirilgan ma’lumotlar tuzilishi.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!