更新時間:2023-03-06 來源:黑馬程序員 瀏覽量:
Java中的二進制搜索樹(Binary Search Tree,簡稱BST)是一種基于二分查找的數據結構,其中每個節點都包含一個鍵值和對應的值,同時滿足以下性質:
1.左子樹上所有節點的鍵值都小于它的根節點的鍵值。
2.右子樹上所有節點的鍵值都大于它的根節點的鍵值。
3.每個子樹都是BST。
以下是Java代碼實現二進制搜索樹的基本操作(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); } }
以上是基本的二進制搜索樹操作,包括插入、查找、刪除等。需要注意的是,這里實現的二進制搜索樹并不是平衡樹,因此在最壞情況下,樹的高度可能會達到 $N$,其中 $N$ 是樹中節點的數量,導致時間復雜度退化為 $O(N)$。為了解決這個問題,可以使用平衡二叉樹(如紅黑樹、AVL樹等)來代替二進制搜索樹。