Kunt u uitleggen wat een binaire zoekboom datastructuur is en hoe deze werkt?

Binaire zoekboom (Binary Search Tree, BST) is een datastructuur in de vorm van een boom, waarbij elke knoop een sleutel bevat, en voor elke knoop geldt de volgende voorwaarde:

• Alle sleutels in de linkeronderboom zijn kleiner dan de sleutel van de knoop.
• Alle sleutels in de rechteronderboom zijn groter dan de sleutel van de knoop.

Dit maakt het mogelijk om efficiënt zoek-, invoeg- en verwijderbewerkingen uit te voeren met een gemiddelde complexiteit van O(log n), als de boom gebalanceerd is.

Voorbeeld van invoegen en zoeken in BST in 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