Java中Binary Search樹介紹

Binary Search Tree（二叉搜索樹）是一種常見的數(shù)據(jù)結(jié)構(gòu)，它是一種二叉樹，其中每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)，并且滿足以下性質(zhì)：

1. 左子樹中的所有節(jié)點(diǎn)的值都小于當(dāng)前節(jié)點(diǎn)的值。
2. 右子樹中的所有節(jié)點(diǎn)的值都大于當(dāng)前節(jié)點(diǎn)的值。
3. 左右子樹也都是二叉搜索樹。

由于滿足上述性質(zhì)，二叉搜索樹可以支持高效的搜索、插入和刪除操作。搜索操作的時(shí)間復(fù)雜度為O(log n)，其中n為樹中節(jié)點(diǎn)的數(shù)量。

Java中可以通過自定義節(jié)點(diǎn)類和二叉搜索樹類來實(shí)現(xiàn)Binary Search Tree。下面是一個(gè)簡(jiǎn)單的實(shí)現(xiàn)示例：

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類表示二叉搜索樹的節(jié)點(diǎn)，以及BST類表示二叉搜索樹。我們實(shí)現(xiàn)了插入、搜索和刪除操作，可以通過這些操作來操作二叉搜索樹。