Ar galite paaiškinti, kas yra duomenų struktūra dvejetainis paieškos medis ir kaip ji veikia?

Dvinaris paieškos medis (Binary Search Tree, BST) yra duomenų struktūra, vaizduojama kaip medis, kur kiekvienas mazgas turi raktą, ir kiekvienam mazgui galioja šios sąlygos:

• Visų kairėje esančių mazgų raktai yra mažesni už mazgo raktą.
• Visų dešinėje esančių mazgų raktai yra didesni už mazgo raktą.

Tai leidžia efektyviai atlikti paieškos, įterpimo ir ištrynimo operacijas su vidutine sudėtingumu O(log n), jei medis yra subalansuotas.

Pavyzdys, kaip įterpti ir ieškoti 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