Оё шумо метавонед шарҳ диҳед, ки структураи додаҳои дарахти ҷустуҷӯӣ чӣ гуна аст ва чӣ гуна кор мекунад?

Дарахти дуалӣ (Binary Search Tree, BST) — структураи маълумот дар шакли дарахт, ки дар он ҳар як нод дорои калид аст, ва барои ҳар як нод шарти зерин риоя мешавад:

• Ҳамаи калидҳо дар зердарахти чап хурдтар аз калиди нод мебошанд.
• Ҳамаи калидҳо дар зердарахти рост калонтар аз калиди нод мебошанд.

Ин имкон медиҳад, ки амалиётҳои ҷустуҷӯ, ворид кардан ва хориҷ кардани элементҳо бо мураккабии миёнаи O(log n) ба таври самаранок иҷро шаванд, агар дарахт мувозинат дошта бошад.

Масалан, намунаи ворид кардан ва ҷустуҷӯ дар BST дар JavaScript:

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(key) {
    const newNode = new Node(key);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (key < current.key) {
        if (!current.left) {
          current.left = newNode;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }
    }
  }

  search(key) {
    let current = this.root;
    while (current) {
      if (key === current.key) return true;
      current = key < current.key ? current.left : current.right;
    }
    return false;
  }
}

const tree = new BST();
tree.insert(10);
tree.insert(5);
tree.insert(15);
console.log(tree.search(5)); // true
console.log(tree.search(20)); // false