Μπορείτε να εξηγήσετε τι είναι μια δομή δεδομένων δυαδικό δέντρο αναζήτησης και πώς λειτουργεί;

Το δυαδικό δέντρο αναζήτησης (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