Binary search tree

Binary search tree (BST) - çap çild'ining qiymati özidan kiçik bölgan, öng çild'ining qiymati özidan katta bölgan node'lardan iborat binary tree.
Binary search tree. Image credit: https://medium.com/swlh/exploring-binary-search-trees-8f63aa0d5dd7
Mavzu:* Tree ma'lumotlar tuzilmasi va binary tree*
Binary search tree'ning binary heap'dan farqi - binary heap'da parent özining çild'laridan katta böladi, binary search'da esa parent çap çild'dan katta va öng çild'dan kiçik böladi.
BST ma'lumotlarni tezkor qidiriş, qöşiş va öçiriş imkonini beradi. Elementlarni qidiriş binary search prinsipi asosida böladi: tree'dan elementni qidirişda (yoki yangi element qöşişda), tree'ni root'idan leaf'gaça tuşib keladi. Bunda har bir node'ga kelganda uni qidirilayotgan element bilan soliştirib, element katta bölsa, qidiruvni node'ning öng tarafidan; element kiçik bölsa qidiruvni node'ning çap tarafidan davom ettiradi. Şu tariqa tree'dagi node'larning yarmidan köpi tekşirilmay taşlab ketiladi.
Agar tree - perfect binary tree bölsa, işlaş vaqti O(log N) gaça tuşadi. N - tree'dagi node'lar soni.
Binary search tree da qidiriş (search)
Quyidagi rasmda qidiriş jarayonini tuşunib olamiz:
BST'da qidiruv
7 sonini BST dan qidiramiz.
- Qidiruvni root (10) dan boşlaymiz.
- 7 < 10, root'ning çap tarafiga ötamiz.
- 7 > 5, node'ning öng tarafida davom ettiramiz.
- 7 = 7, kerakli sonni topdik.
BST'ga ma'lumot qöşiş (insert)
BST'ga ma'lumot qöşiş. Image credit: https://link.medium.com/oXl7cHounab
Ma'lumot qöşişdan oldin uni BST'da qidiramiz. Agar mavjud bölsa, şunçaki uning qiymatini özgartiramiz. Yöq bölsa, yangi child sifatida qöşamiz.
BTS'ga 16 sonini qöşamiz.
- Qidiruvni root (10) dan boşlaymiz.
- 16 > 10, öng tarafga ötamiz
- 16 > 15, lekin 15 ning çild'i yöq. Şu sababli 16ni 15 ning çild'i sifatida qöşamiz. 16 > 15 bölgani uçun, 16 öng tarafdagi child sifatida qöşiladi.
BST'dan ma'lumot öçiriş (delete)
Öçiriş jarayoni biroz murakkab, çunki biz tree'dan node'ni öçirganimizdan keyin tree'ning butunligini saqlab qolişimiz ham kerak. Ya'ni node öçirilgaç, biz node'ning çild'larini tekşirib, ularni kerakli parent'ga beramiz.
Öçiriş 3 xil holatda bölişi mumkin
Öçirilayotgan node - leaf. Uni şunçaki öçiriş bilan qutilamiz.
Çild'i yöq node'ni öçiriş. Image credit: https://levelup.gitconnected.com/deletion-in-binary-search-tree-with-javascript-fded82e1791c
Öçirilayotgan node'ning bitta çild'i bor. Bunisi ham oson, node'ning çild'ini uning parent'iga beramiz.
*Bitta çild'i bor node'ni öçiriş: *Image credit: https://levelup.gitconnected.com/deletion-in-binary-search-tree-with-javascript-fded82e1791c
Öçirilayotgan node'ning ikki çild'i bor. Murakkab qismi. Dastlab, öçirilayotgan node'ning çild'lari içidan keyingi qiymatdagi node'ni topamiz. Keyin uning qiymatini öçirilayotgan node'ga beramiz va keyin qiymatdagi node'ni tree'dan öçiramiz.
*Ikki çild'i bor node'ni öçiriş. *Image credit: https://levelup.gitconnected.com/deletion-in-binary-search-tree-with-javascript-fded82e1791c
Öçiriş yakunlangaç
*Tree ikki çild'i bor node öçirilganidan söng. *Image credit: https://levelup.gitconnected.com/deletion-in-binary-search-tree-with-javascript-fded82e1791c
Binary search'ning vizualizatsiyasini özingiz bu yerda sinab körişingiz mumkin: https://www.cs.usfca.edu/~galles/visualization/BST.html
Binary search tree'ni array'da ifodalaş
Binary search tree'ni array'da ifodalaş mumkin. Muammo - agar binary tree perfect bölmasa, array'dagi ba'zi indekslar böş qolib ketadi. Masalan quyidagi binary tree'ni array'da ifodalaymiz.
Perfect binary search tree
Hisoblaşda oson bölişi uçun array[0] ni böş qoldiramiz. array[1] - root; array[2] va array[3] root'ning ikki çild'i böladi.
[null, 50, 30, 70, 23, 35, 80, 11, 25, 31, 42, 73, 85]
Binary heap'dagi kabi parent'ning çild'ini 2i va 2i + 1 topiş mumkin. Bunda i - parent'ning indeksi.
Ok, hayot har doim ham bir tekis davom etmaydi. Tree kamdan-kam holatda perfect böladi.
**Binary search tree. Image credit: https://medium.com/swlh/exploring-binary-search-trees-8f63aa0d5dd7
Yuqoridagi tree perfect emas, şu sabab uni array'da ifodalaşda array'ning ba'zi indekslarida null qiymat paydo böladi:
[null, 56, 30, 70, 22, 40, 60, 95, 11, null, null, null, null, 65, null, null, 3, 16, null, null, null, null, null, null, null, null, 63, 67, null, null, null, null]
Eng yomon holatdagi tree - degenerate search tree'ni körib çiqamiz.

[null, 50, null, 70, null, null, null, 75, null, null, null, null, null, null, null, 80, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, 85]
5 ta elementdagi degenerate tree'ni ifodalaş uçun array'da 31 da indeks band qilinyapti. Juda ham samarasiz.
Xulosa. Binary search tree faqat perfect bölgandagina, uni array'da ifodalaşdan ma'no bor.
Linked list'da ifodalaş
Linked list ma'lumot tuzilmasi tree'larni ifodalaş uçun mos keladi. Tree turiga qarab linked list'dagi node'larning pointerlari bitta yoki undan köp bölişi mumkin. Biz binary search tree'ni linked list'da ifodalaşni körib çiqamiz.
Binary search tree'dagi har bir node'ning maksimum ikki çild'i bölişi ehtimoli borligi uçun, Linked list'dagi node'ning ham ikki pointeri böladi.
Mavzuning davomi va kod bu yerda: Binary search tree ustida amallar. API yoziş