首頁常見問題正文

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

更新時(shí)間:2023-03-06 來源:黑馬程序員 瀏覽量:

IT培訓(xùn)班

  Java中的二進(jìn)制搜索樹(Binary Search Tree,簡(jiǎn)稱BST)是一種基于二分查找的數(shù)據(jù)結(jié)構(gòu),其中每個(gè)節(jié)點(diǎn)都包含一個(gè)鍵值和對(duì)應(yīng)的值,同時(shí)滿足以下性質(zhì):

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

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

  3.每個(gè)子樹都是BST。

  以下是Java代碼實(shí)現(xiàn)二進(jì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);
    }
}

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

分享到:
在線咨詢 我要報(bào)名
和我們?cè)诰€交談!