Binary search tree ustida amallar. API yozish

Binary search tree

BSTga element qo’shish, o’chirish, qidirish, maksimum/minimum elementni chiqarish uchun API yozamiz. APIning tuzilishi quyidagicha bo’ladi.

Mavzu: Binary search tree

Qo’shish (Insert)

Ma’lumot qo’shishdan oldin uni BST’da qidiramiz. Agar mavjud bo’lsa, shunchaki uning qiymatini o’zgartiramiz. Yo’q bo’lsa, yangi child sifatida qo’shamiz.

Element qidirish (Find)

Elementlarni qidirish binary search prinsipi asosida bo’ladi: tree’dan elementni qidirishda tree’ni root’idan leaf’gacha tushib keladi. Bunda har bir node’ga kelganda uni qidirilayotgan element bilan solishtirib, element katta bo’lsa, qidiruvni node’ning o’ng child’idan; element kichik bo’lsa qidiruvni node’ning chap child’idan davom ettiradi. 

O’chirish (Delete)

O’chirish haqida avvalgi maqolada tushuntirib o’tilgani uchun, bu yerda faqat funksiya bilan cheklanamiz.

Tree’dan minimum qiymatni topish (Min)

Tree’ning minimum qiymati uning eng uzoqdagi chap node’ida bo’lgani uchun biz faqat chap tarafdagi child’larni tekshiramiz. Faqat o’ng child’larida node bo’lgan degenerate tree uchun root element qaytariladi.

Tree’dan maksimum qiymatni topish (Max)

Tree’ning maksimum qiymati uning eng uzoqdagi o’ng node’ida bo’lgani uchun biz faqat o’ng tarafdagi child’larni tekshiramiz.

Tree’dan berilgan qiymatga teng yoki undan kichik elementni topish (Floor)

Misol uchun, tree’da 30 50, 70 elementlari bo’lsayu, biz 35 ni qidirsak, funksiya 30 ni qaytaradi. Funksiya katta ma’lumotlar bilan ishlashda yoki statistikada foydali.

Tree’dan berilgan qiymatga teng yoki undan kichik elementni topish (Ceiling)

Floor’ning teskarisi.

Tree’ni array’ga o’zgartirib tartiblash (Sort)

Tree’ni array’ga o’zgartirishda root’dan leafgacha tushib kelib, ma’lumotlar array’ga yig’iladi.

* * *

To’liq API kod Githubdahttps://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/trees/binary-search-trees.js

* * *

Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.