Axtarış ağacı məlumatlar strukturu nədir və necə işləyir?

İkili Axtarış Ağacı (Binary Search Tree, BST) — bu, hər bir düyünündə açar olan və hər bir düyün üçün aşağıdakı şərtin təmin olunduğu ağac şəklində məlumat quruluşudur:

• Sol alt ağacdakı bütün açarlar düyünün açarından kiçikdir.
• Sağ alt ağacdakı bütün açarlar düyünün açarından böyüktür.

Bu, ağac balanslı olduqda, axtarış, əlavə və silmə əməliyyatlarını effektiv şəkildə həyata keçirməyə imkan verir və orta hesabla O(log n) mürəkkəbliyə malikdir.

JavaScript-də BST-də əlavə və axtarış nümunəsi:

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