Können Sie erklären, was eine Datenstruktur binärer Suchbaum ist und wie sie funktioniert?

Binärer Suchbaum (Binary Search Tree, BST) ist eine Datenstruktur in Form eines Baumes, bei der jeder Knoten einen Schlüssel enthält, und für jeden Knoten gilt folgende Bedingung:

• Alle Schlüssel im linken Teilbaum sind kleiner als der Schlüssel des Knotens.
• Alle Schlüssel im rechten Teilbaum sind größer als der Schlüssel des Knotens.

Dies ermöglicht effiziente Operationen wie Suche, Einfügen und Löschen mit einer durchschnittlichen Komplexität von O(log n), wenn der Baum ausgeglichen ist.

Beispiel für Einfügen und Suchen in einem 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