Binary Search Tree(二叉搜索樹)是一種常見的數據結構,它是一種二叉樹,其中每個節點最多只有兩個子節點,并且滿足以下性質:
由于滿足上述性質,二叉搜索樹可以支持高效的搜索、插入和刪除操作。搜索操作的時間復雜度為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類表示二叉搜索樹。我們實現了插入、搜索和刪除操作,可以通過這些操作來操作二叉搜索樹。