Java中Binary Search树介绍

Binary Search Tree（二叉搜索树）是一种常见的数据结构，它是一种二叉树，其中每个节点最多只有两个子节点，并且满足以下性质：

1. 左子树中的所有节点的值都小于当前节点的值。
2. 右子树中的所有节点的值都大于当前节点的值。
3. 左右子树也都是二叉搜索树。

由于满足上述性质，二叉搜索树可以支持高效的搜索、插入和删除操作。搜索操作的时间复杂度为O(log n)，其中n为树中节点的数量。

Java中可以通过自定义节点类和二叉搜索树类来实现Binary Search Tree。下面是一个简单的实现示例：

class Node {
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST {
    private Node root;

    public BST() {
        this.root = null;
    }

    public void insert(int val) {
        this.root = insertNode(root, val);
    }

    private Node insertNode(Node root, int val) {
        if (root == null) {
            return new Node(val);
        }

        if (val < root.val) {
            root.left = insertNode(root.left, val);
        } else {
            root.right = insertNode(root.right, val);
        }

        return root;
    }

    public boolean search(int val) {
        return searchNode(root, val);
    }

    private boolean searchNode(Node root, int val) {
        if (root == null) {
            return false;
        }

        if (val == root.val) {
            return true;
        } else if (val < root.val) {
            return searchNode(root.left, val);
        } else {
            return searchNode(root.right, val);
        }
    }

    public void delete(int val) {
        this.root = deleteNode(root, val);
    }

    private Node deleteNode(Node root, int val) {
        if (root == null) {
            return null;
        }

        if (val < root.val) {
            root.left = deleteNode(root.left, val);
        } else if (val > root.val) {
            root.right = deleteNode(root.right, val);
        } else {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            root.val = findMin(root.right);
            root.right = deleteNode(root.right, root.val);
        }

        return root;
    }

    private int findMin(Node root) {
        int min = root.val;
        while (root.left != null) {
            min = root.left.val;
            root = root.left;
        }
        return min;
    }
}

在上面的代码中，我们定义了Node类表示二叉搜索树的节点，以及BST类表示二叉搜索树。我们实现了插入、搜索和删除操作，可以通过这些操作来操作二叉搜索树。