Arama ağacı veri yapısının ne olduğunu ve nasıl çalıştığını açıklayabilir misiniz?

İkili Arama Ağacı (Binary Search Tree, BST), her düğümün anahtar içerdiği ve her düğüm için aşağıdaki koşulun sağlandığı ağaç biçiminde bir veri yapısıdır:

• Sol alt ağaçtaki tüm anahtarlar, düğümün anahtarından küçüktür.
• Sağ alt ağaçtaki tüm anahtarlar, düğümün anahtarından büyüktür.

Bu, ağaç dengeli ise, arama, ekleme ve silme işlemlerini ortalama O(log n) karmaşıklıkla verimli bir şekilde yapmayı sağlar.

JavaScript'te BST'de ekleme ve arama örneği:

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