ឧបករណ៍បង្ហាញ Binary Search Tree

insert(node, key):  if node = null: return new Node(key)  if key < node.key: node.left = insert(node.left, key)  else if key > node.key: node.right = insert(node.right, key)  return node            // equal keys are ignoredsearch(node, key):  if node = null: return not found  if key = node.key: return node  if key < node.key: return search(node.left, key)  return search(node.right, key)delete(key):  find the node, like search  no children: remove it  one child: replace the node with its child  two children: copy the in-order successor into it, delete the successortraversals:  in-order:    left, node, right   (sorted order)  pre-order:   node, left, right  post-order:  left, right, node  level order: queue = [root]; visit front, enqueue its children

struct Node { int key; Node *left = nullptr, *right = nullptr; Node(int k) : key(k) {} };

Node* insert(Node* n, int key) {
    if (!n) return new Node(key);
    if (key < n->key) n->left = insert(n->left, key);
    else if (key > n->key) n->right = insert(n->right, key);
    return n;
}
Node* search(Node* n, int key) {
    while (n && n->key != key) n = key < n->key ? n->left : n->right;
    return n;
}
Node* remove(Node* n, int key) {
    if (!n) return nullptr;
    if (key < n->key) n->left = remove(n->left, key);
    else if (key > n->key) n->right = remove(n->right, key);
    else {
        if (!n->left) { Node* r = n->right; delete n; return r; }
        if (!n->right) { Node* l = n->left; delete n; return l; }
        Node* s = n->right;
        while (s->left) s = s->left;           // in-order successor
        n->key = s->key;
        n->right = remove(n->right, s->key);
    }
    return n;
}
void inorder(Node* n) { if (!n) return; inorder(n->left); std::cout << n->key << ' '; inorder(n->right); }

class BST {
    static class Node { int key; Node left, right; Node(int k) { key = k; } }
    Node root;

    void insert(int key) { root = insert(root, key); }
    private Node insert(Node n, int key) {
        if (n == null) return new Node(key);
        if (key < n.key) n.left = insert(n.left, key);
        else if (key > n.key) n.right = insert(n.right, key);
        return n;
    }
    boolean contains(int key) {
        Node n = root;
        while (n != null && n.key != key) n = key < n.key ? n.left : n.right;
        return n != null;
    }
    void delete(int key) { root = delete(root, key); }
    private Node delete(Node n, int key) {
        if (n == null) return null;
        if (key < n.key) n.left = delete(n.left, key);
        else if (key > n.key) n.right = delete(n.right, key);
        else {
            if (n.left == null) return n.right;
            if (n.right == null) return n.left;
            Node s = n.right;
            while (s.left != null) s = s.left;
            n.key = s.key;
            n.right = delete(n.right, s.key);
        }
        return n;
    }
    void inorder(Node n, java.util.List<Integer> out) {
        if (n == null) return;
        inorder(n.left, out); out.add(n.key); inorder(n.right, out);
    }
}

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

def insert(n, key):
    if n is None:
        return Node(key)
    if key < n.key:
        n.left = insert(n.left, key)
    elif key > n.key:
        n.right = insert(n.right, key)
    return n

def search(n, key):
    while n and n.key != key:
        n = n.left if key < n.key else n.right
    return n

def delete(n, key):
    if n is None:
        return None
    if key < n.key:
        n.left = delete(n.left, key)
    elif key > n.key:
        n.right = delete(n.right, key)
    else:
        if n.left is None:
            return n.right
        if n.right is None:
            return n.left
        s = n.right
        while s.left:
            s = s.left
        n.key = s.key
        n.right = delete(n.right, s.key)
    return n

def inorder(n):
    return inorder(n.left) + [n.key] + inorder(n.right) if n else []

class Node {
  constructor(key) { this.key = key; this.left = null; this.right = null; }
}
function insert(n, key) {
  if (!n) return new Node(key);
  if (key < n.key) n.left = insert(n.left, key);
  else if (key > n.key) n.right = insert(n.right, key);
  return n;
}
function search(n, key) {
  while (n && n.key !== key) n = key < n.key ? n.left : n.right;
  return n;
}
function remove(n, key) {
  if (!n) return null;
  if (key < n.key) n.left = remove(n.left, key);
  else if (key > n.key) n.right = remove(n.right, key);
  else {
    if (!n.left) return n.right;
    if (!n.right) return n.left;
    let s = n.right;
    while (s.left) s = s.left;
    n.key = s.key;
    n.right = remove(n.right, s.key);
  }
  return n;
}
const inorder = (n) => (n ? [...inorder(n.left), n.key, ...inorder(n.right)] : []);