二叉搜索树

**二叉搜索树**

二叉搜索树（Binary Search Tree，BST）是一种常见的数据结构，它通过在每个结点上维护一个关键字来实现快速查找、插入和删除操作。这种数据结构广泛应用于数据库管理系统、文件系统等领域。

**定义**

二叉搜索树是指一棵空树或具有以下性质的树：

1. 每个结点最多有两个子结点（左孩子和右孩子）。
2. 每个结点的值都大于其左孩子的值，小于其右孩子的值。
3. 每个结点的左、右子树都是二叉搜索树。

**性质**

二叉搜索树有以下几个重要性质：

1. **查找时间复杂度**: 二叉搜索树的查找时间复杂度为 O(h)，其中 h 是树的高度。由于每个结点最多有两个子结点，因此 h 最多为 n，n 为结点数。
2. **插入和删除时间复杂度**: 插入或删除一个结点后，可能会导致树的高度增加，但不会超过 n。
3. **平衡性**: 二叉搜索树不一定是平衡的，即每个子树的高度差不超过1。然而，在某些情况下，我们可以通过旋转操作来维持平衡性。

**实现**

以下是二叉搜索树的一些基本实现：

### Java 实现

javapublic class Node {
 int value;
 Node left;
 Node right;

 public Node(int value) {
 this.value = value;
 this.left = null;
 this.right = null;
 }
}

public class BinarySearchTree {
 private Node root;

 public void insert(int value) {
 root = insertRecursive(root, value);
 }

 private Node insertRecursive(Node node, int value) {
 if (node == null) {
 return new Node(value);
 }

 if (value < node.value) {
 node.left = insertRecursive(node.left, value);
 } else if (value > node.value) {
 node.right = insertRecursive(node.right, value);
 }

 return node;
 }

 public boolean search(int value) {
 return searchRecursive(root, value);
 }

 private boolean searchRecursive(Node node, int value) {
 if (node == null) {
 return false;
 }

 if (value < node.value) {
 return searchRecursive(node.left, value);
 } else if (value > node.value) {
 return searchRecursive(node.right, value);
 }

 return true;
 }
}

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Noneclass BinarySearchTree:
 def __init__(self):
 self.root = None def insert(self, value):
 self.root = self.insert_recursive(self.root, value)

 def insert_recursive(self, node, value):
 if node is None:
 return Node(value)
 if value < node.value:
 node.left = self.insert_recursive(node.left, value)
 elif value > node.value:
 node.right = self.insert_recursive(node.right, value)
 return node def search(self, value):
 return self.search_recursive(self.root, value)

 def search_recursive(self, node, value):
 if node is None:
 return False if value < node.value:
 return self.search_recursive(node.left, value)
 elif value > node.value:
 return self.search_recursive(node.right, value)
 return True

javapublic class Main {
 public static void main(String[] args) {
 BinarySearchTree bst = new BinarySearchTree();
 bst.insert(5);
 bst.insert(3);
 bst.insert(7);
 System.out.println(bst.search(3)); // true System.out.println(bst.search(4)); // false }
}

class Main:
 def main(self):
 bst = BinarySearchTree()
 bst.insert(5)
 bst.insert(3)
 bst.insert(7)
 print(bst.search(3)) # true print(bst.search(4)) # falseif __name__ == "__main__":
 Main().main()