Двоичное дерево поиска (BST) – это базовое упорядоченное двоичное дерево, в котором элементы хранятся в определенном порядке, что позволяет эффективно выполнять несколько операций над элементами.

Свойства BST:

  1. Левое поддерево узла содержит узлы с ключами меньше, чем ключ узла.
  2. Правое поддерево узла содержит узлы с ключами, большими, чем ключ узла.
  3. Каждое из левого и правого поддеревьев должно быть бинарным деревом поиска.
  4. Двоичное дерево поиска не работает с повторяющимся ключом.

Пример BST:

Работа BST:

Algorithm         Average        Worst
=======================================
Space              O(n)           O(n)
Insert             O(n lg n)      O(n)
Search             O(n lg n)      O(n)
Delete             O(n lg n)      O(n)

Поиск ключа:

static class Node {
    int key;
    Node left, right;

    public Node() {}

    public Node(int key) {
        this.key = key;
    }
}
private Node searchNode(Node node, int key) {
    if(null == node || node.key == key) return node;
    if(key < node.key) return searchNode(node.left, key);
    else return searchNode(node.right, key);
}

Вставка ключа:

private Node insertNode(Node node, int key) {
    if(null == node) return new Node(key);
    if(key < node.key) node.left = insertNode(node.left, key);
    else node.right = insertNode(node.right, key);
    return node;
}

Удаление ключа:

private Node deleteNode(Node node, int key) {
    if(null == node) return node;
    if (key < node.key) node.left = deleteNode(node.left, key);
    else if(key > node.key) node.right = deleteNode(node.right, key);
    else {
        // Node with one child or no child
        if (null == node.left) return node.right;
        if (null == node.right) return node.left;

        Node temp = inorderSuccessor(node.right);
        node.key = temp.key;

        node.right = deleteNode(node.right, temp.key);
    }
    return node;
}
private Node inorderSuccessor(Node node) {
    Node current = node;
    while(null != current.left) current = current.left;
    return current;
}