用java代碼實現(xiàn)二進制搜索樹

　　Java中的二進制搜索樹(Binary Search Tree，簡稱BST)是一種基于二分查找的數(shù)據(jù)結構，其中每個節(jié)點都包含一個鍵值和對應的值，同時滿足以下性質(zhì)：

　　1.左子樹上所有節(jié)點的鍵值都小于它的根節(jié)點的鍵值。

　　2.右子樹上所有節(jié)點的鍵值都大于它的根節(jié)點的鍵值。

　　3.每個子樹都是BST。

　　以下是Java代碼實現(xiàn)二進制搜索樹的基本操作(kotlin)：

public class BinarySearchTree {
    private Node root;

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

        public Node(int key) {
            this.key = key;
        }
    }

    public BinarySearchTree() {
        root = null;
    }

    // 插入操作
    public void insert(int key) {
        root = insert(root, key);
    }

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

    // 查找操作
    public boolean contains(int key) {
        return contains(root, key);
    }

    private boolean contains(Node x, int key) {
        if (x == null) return false;
        if (key == x.key) return true;
        else if (key < x.key) return contains(x.left, key);
        else return contains(x.right, key);
    }

    // 刪除操作
    public void delete(int key) {
        root = delete(root, key);
    }

    private Node delete(Node x, int key) {
        if (x == null) return null;
        if (key < x.key) x.left = delete(x.left, key);
        else if (key > x.key) x.right = delete(x.right, key);
        else {
            if (x.right == null) return x.left;
            if (x.left == null) return x.right;
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        return x;
    }

    private Node deleteMin(Node x) {
        if (x.left == null) return x.right;
        x.left = deleteMin(x.left);
        return x;
    }

    private Node min(Node x) {
        if (x.left == null) return x;
        return min(x.left);
    }
}

　　以上是基本的二進制搜索樹操作，包括插入、查找、刪除等。需要注意的是，這里實現(xiàn)的二進制搜索樹并不是平衡樹，因此在最壞情況下，樹的高度可能會達到 $N$，其中 $N$ 是樹中節(jié)點的數(shù)量，導致時間復雜度退化為 $O(N)$。為了解決這個問題，可以使用平衡二叉樹(如紅黑樹、AVL樹等)來代替二進制搜索樹。