Vai jūs varat izskaidrot, kas ir binārais meklēšanas koka datu struktūra un kā tā darbojas?

Binaārā meklēšanas koks (Binary Search Tree, BST) ir datu struktūra koka formā, kur katrs mezgls satur atslēgu, un katram mezglam ir šādi nosacījumi:

• Visas kreisās apakškoka atslēgas ir mazākas par mezgla atslēgu.
• Visas labās apakškoka atslēgas ir lielākas par mezgla atslēgu.

Tas ļauj efektīvi veikt meklēšanas, pievienošanas un dzēšanas operācijas ar vidējo sarežģītību O(log n), ja koks ir līdzsvarots.

Piemērs, kā pievienot un meklēt 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