Pouvez-vous expliquer ce qu'est une structure de données arbre binaire de recherche et comment elle fonctionne?

Un arbre de recherche binaire (Binary Search Tree, BST) est une structure de données sous forme d'arbre, où chaque nœud contient une clé, et la condition suivante est satisfaite pour chaque nœud :

• Toutes les clés dans le sous-arbre gauche sont inférieures à la clé du nœud.
• Toutes les clés dans le sous-arbre droit sont supérieures à la clé du nœud.

Cela permet d'effectuer efficacement des opérations de recherche, d'insertion et de suppression d'éléments avec une complexité moyenne de O(log n), si l'arbre est équilibré.

Exemple d'insertion et de recherche dans un BST en 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