Kunning tasdiqlanishi: O'zingizga mehribon bo'lishni unutmang 🌟

Ikkilik qidiruv daraxti - bu quyidagi xususiyatlarga ega bo'lgan ma'lumotlar tuzilmasi:

A. Har bir daraxt tugunida ko‘pi bilan ikkita bola bor

B. O'ng pastki daraxtdagi barcha tugunlar ildizdan kattaroqdir

C. Chap pastki daraxtdagi barcha tugunlar ildizdan kamroq

Eslatma: Ildiz daraxtning birinchi tugunidir

Ikkilik qidiruv daraxtining eng yaxshi stsenariysi 0 (log n) dir. Buning sababi, search() ni topish yoki tugunni olib tashlash uchun biz tugunni takrorlashimiz va har bir iteratsiyada daraxtni ajratishimiz kerak. Bu bog'langan ro'yxatni ishlatishdan ko'ra ikkilik qidiruv daraxti yordamida search() va remove() ni tezroq qiladi (buning sababini quyida ko'rib chiqamiz).

Ikkilik qidiruv daraxtining eng yomon stsenariysi 0(n). Demak, ikkilik qidiruv daraxtining Katta 0 qiymati 0(n) ga teng. Ikkilik qidiruv daraxtining eng yomon stsenariysi faqat daraxtning o'ng pastki daraxtida tugunlar mavjud bo'lganda (chap pastki daraxt bo'sh) yoki daraxtning chap pastki daraxtida faqat tugunlar mavjud bo'lganda (o'ng pastki daraxt bo'sh) paydo bo'lishi mumkin. Bu erda biz to'g'ri chiziqda harakat qilganimiz uchun muammolarni yarmiga {0(log n), logarifmik vaqt} ga bo'lishning afzalliklaridan foydalana olmaymiz. Bu bog'langan ro'yxatlarga o'xshaydi.

Ikkilik qidiruv daraxtlari va bog'langan ro'yxatlar

Yuqorida aytib o'tilganidek, biz bog'langan ro'yxatda to'g'ri chiziqda ishlaymiz. Shunday qilib, agar biz tugunni qidirayotgan bo'lsak yoki tugunni olib tashlashga harakat qilsak, bog'langan ro'yxatni takrorlashimiz kerak bo'ladi. Bu 0(n) operatsiyalar.

Biroq, "bog'langan ro'yxatning oxiriga, ya'ni surish" bandini qo'shish uchun 0(1) bo'ladi. Shunday qilib, insert() bog'langan ro'yxat bilan ikkilik qidiruv daraxtiga qaraganda yaxshiroqdir, chunki 0(1) 0(log n) dan samaraliroq.

Qisqa bayoni; yakunida:

Keling, ikkilik qidiruv daraxtini (BST) amalga oshiramiz!

BST: Insert()

Ushbu usul uchun biz:

  1. Yangi tugun yarating.
  2. Agar daraxt bo'sh bo'lsa, shartli bayonotga ega bo'ling.
  3. Agar biz kiritayotgan tugun daraxtda joylashgan tugun bilan bir xil qiymatga ega bo'lsa, shartli bayonotga ega bo'ling.
  4. Biz kiritmoqchi bo'lgan tugunni 1-tugun bilan solishtiring, agar u undan kichik yoki oldingi tugundan kichik bo'lsa, u chapga, undan katta yoki oldingi tugundan katta bo'lsa, o'ngga o'tadi.
  5. Agar u null bo'lsa (bo'sh joy) biz ushbu bo'shliqqa yangi tugunni joylashtiramiz, aks holda keyingi tugunga o'tamiz va taqqoslaymiz (4-bosqichda bo'lgani kabi).
  6. Bir oz vaqt ajrating, chunki biz daraxtni necha marta aylanib o'tishimizni bilmaymiz. Ya'ni, biz 4 va 5-bosqichlarni necha marta bajarishimizni bilmaymiz.
insert(value){
const newNode = new Node(value); //we create a new Node
if(this.root === null){
this.root = newNode;
return this; //if we have an empty tree, root is set equal to the new Node and is returned
  }
let temp = this.root //we create a temp variable to point to the parent element and we will use temp to iterate through the list
while(true){
if(newNode.value === temp.value) return undefined {
 if(newNode.value < temp.value) {
    if (temp.left === null){
    temp.left = newNode;
    return this; //returns the entire tree
        }
     temp = temp.left; //if the space isn't open on the left side of the tree
      } else {
      if (temp.right === null) {
      temp.right = newNode;
       return this;
        }
  temp = temp.right;
      }
    }
  }
}

BST: tarkibida() mavjud

Bu erda biz daraxt ichida joylashgan tugunni qidiramiz.

Biz daraxtning ildizidan boshlaymiz va a) bizda takrorlash mumkin bo'lgan to'liq daraxt bor yoki b) bizda bo'sh daraxt bor, shuning uchun ildiz nullga teng bo'ladi.

contains(value) {
  if(this.root === null) return false;
    let temp = this.root //if we have items in the tree, we create a variable temp and use it to iterate through the tree
      while(temp){
      if (value < temp.value){
          temp = temp.left; //if the number we're looking for is less than the parent, temp moves to the left and down
      } else if (value > temp.value){
      temp = temp.right; //if the number is greater than the parent, temp moves to the right
      } else{
         return true; //if the values are the same return true 
      }
      return false; //if temp is equal to null it'll return false and break out of the while loop. For instance if we're looking for a number that's not in the tree
    }
  }

BST: Minimal qiymat()

Biz daraxtdagi minimal qiymatni (eng kichik raqam) o'z ichiga olgan tugunni qaytarmoqchimiz. Agar chap pastki daraxt bo'sh bo'lmasa, biz minimal qiymatga ega bo'lgunimizcha while tsiklini bajaramiz. Agar u bo'sh bo'lsa, biz while tsiklidan chiqib, minimal qiymat bo'lgan joriy tugunni qaytaramiz.

minValueNode(currentNode) {
  while (currentNode.left != null){
    currentNode = currentNode.left
  }
  return currentNode
}