二叉搜索树是一种二叉树,其中每个节点的左子树中的值都小于该节点的值,右子树中的值都大于该节点的值。这种特性使得二叉搜索树在查找、插入和删除操作上具有较高的效率。
二叉搜索树(Binary Search Tree,简称BST)是一种特殊的二叉树数据结构,它具有以下特点:对于树中的每个节点,其左子树中所有节点的值都小于该节点的值,右子树中所有节点的值都大于该节点的值。
删除操作较为复杂,需要考虑三种情况:
▼Java复制代码public class BinarySearchTree { // 定义节点类 class Node { int value; // 节点值 Node left; // 左子节点 Node right; // 右子节点 public Node(int value) { this.value = value; this.left = null; this.right = null; } } private Node root; // 根节点 public BinarySearchTree() { root = null; } // 插入操作 public void insert(int value) { root = insertRecursive(root, value); } private Node insertRecursive(Node current, int value) { // 如果当前节点为空,创建新节点 if (current == null) { return new Node(value); } // 递归插入到合适位置 if (value < current.value) { current.left = insertRecursive(current.left, value); } else if (value > current.value) { current.right = insertRecursive(current.right, value); } // 值已存在,不做任何操作 return current; } // 查找操作 public boolean search(int value) { return searchRecursive(root, value); } private boolean searchRecursive(Node current, int value) { // 空树或到达叶节点 if (current == null) { return false; } // 找到目标值 if (value == current.value) { return true; } // 在左子树或右子树中查找 if (value < current.value) { return searchRecursive(current.left, value); } else { return searchRecursive(current.right, value); } } // 删除操作 public void delete(int value) { root = deleteRecursive(root, value); } private Node deleteRecursive(Node current, int value) { // 树为空或未找到要删除的值 if (current == null) { return null; } // 找到要删除的节点 if (value == current.value) { // 情况1:叶节点 if (current.left == null && current.right == null) { return null; } // 情况2:只有一个子节点 if (current.left == null) { return current.right; } if (current.right == null) { return current.left; } // 情况3:有两个子节点 // 查找右子树中的最小值 int smallestValue = findSmallestValue(current.right); current.value = smallestValue; // 删除右子树中的最小值节点 current.right = deleteRecursive(current.right, smallestValue); return current; } // 继续在左子树或右子树中查找 if (value < current.value) { current.left = deleteRecursive(current.left, value); } else { current.right = deleteRecursive(current.right, value); } return current; } // 查找子树中的最小值(最左侧节点) private int findSmallestValue(Node root) { if (root.left == null) { return root.value; } return findSmallestValue(root.left); } }
▼Javascript复制代码class Node { constructor(value) { this.value = value; // 节点值 this.left = null; // 左子节点 this.right = null; // 右子节点 } } class BinarySearchTree { constructor() { this.root = null; // 根节点 } // 插入操作 insert(value) { this.root = this.insertRecursive(this.root, value); } insertRecursive(current, value) { // 如果当前节点为空,创建新节点 if (current === null) { return new Node(value); } // 递归插入到合适位置 if (value < current.value) { current.left = this.insertRecursive(current.left, value); } else if (value > current.value) { current.right = this.insertRecursive(current.right, value); } // 值已存在,不做任何操作 return current; } // 查找操作 search(value) { return this.searchRecursive(this.root, value); } searchRecursive(current, value) { // 空树或到达叶节点 if (current === null) { return false; } // 找到目标值 if (value === current.value) { return true; } // 在左子树或右子树中查找 if (value < current.value) { return this.searchRecursive(current.left, value); } else { return this.searchRecursive(current.right, value); } } // 删除操作 delete(value) { this.root = this.deleteRecursive(this.root, value); } deleteRecursive(current, value) { // 树为空或未找到要删除的值 if (current === null) { return null; } // 找到要删除的节点 if (value === current.value) { // 情况1:叶节点 if (current.left === null && current.right === null) { return null; } // 情况2:只有一个子节点 if (current.left === null) { return current.right; } if (current.right === null) { return current.left; } // 情况3:有两个子节点 // 查找右子树中的最小值 const smallestValue = this.findSmallestValue(current.right); current.value = smallestValue; // 删除右子树中的最小值节点 current.right = this.deleteRecursive(current.right, smallestValue); return current; } // 继续在左子树或右子树中查找 if (value < current.value) { current.left = this.deleteRecursive(current.left, value); } else { current.right = this.deleteRecursive(current.right, value); } return current; } // 查找子树中的最小值(最左侧节点) findSmallestValue(root) { if (root.left === null) { return root.value; } return this.findSmallestValue(root.left); } // 中序遍历(得到排序结果) inorderTraversal() { const result = []; this.inorderRecursive(this.root, result); return result; } inorderRecursive(current, result) { if (current !== null) { this.inorderRecursive(current.left, result); result.push(current.value); this.inorderRecursive(current.right, result); } } }
▼Python复制代码class Node: def __init__(self, value): self.value = value # 节点值 self.left = None # 左子节点 self.right = None # 右子节点 class BinarySearchTree: def __init__(self): self.root = None # 根节点 # 插入操作 def insert(self, value): self.root = self._insert_recursive(self.root, value) def _insert_recursive(self, current, value): # 如果当前节点为空,创建新节点 if current is None: return Node(value) # 递归插入到合适位置 if value < current.value: current.left = self._insert_recursive(current.left, value) elif value > current.value: current.right = self._insert_recursive(current.right, value) # 值已存在,不做任何操作 return current # 查找操作 def search(self, value): return self._search_recursive(self.root, value) def _search_recursive(self, current, value): # 空树或到达叶节点 if current is None: return False # 找到目标值 if value == current.value: return True # 在左子树或右子树中查找 if value < current.value: return self._search_recursive(current.left, value) else: return self._search_recursive(current.right, value) # 删除操作 def delete(self, value): self.root = self._delete_recursive(self.root, value) def _delete_recursive(self, current, value): # 树为空或未找到要删除的值 if current is None: return None # 找到要删除的节点 if value == current.value: # 情况1:叶节点 if current.left is None and current.right is None: return None # 情况2:只有一个子节点 if current.left is None: return current.right if current.right is None: return current.left // 情况3:有两个子节点 # 查找右子树中的最小值 smallest_value = self._find_smallest_value(current.right) current.value = smallest_value # 删除右子树中的最小值节点 current.right = self._delete_recursive(current.right, smallest_value) return current // 继续在左子树或右子树中查找 if value < current.value: current.left = self._delete_recursive(current.left, value) else: current.right = self._delete_recursive(current.right, value) return current # 查找子树中的最小值(最左侧节点) def _find_smallest_value(self, root): if root.left is None: return root.value return self._find_smallest_value(root.left) # 中序遍历(得到排序结果) def inorder_traversal(self): result = [] self._inorder_recursive(self.root, result) return result def _inorder_recursive(self, current, result): if current is not None: self._inorder_recursive(current.left, result) result.append(current.value) self._inorder_recursive(current.right, result)
▼Go复制代码package main import "fmt" // Node 定义二叉搜索树节点 type Node struct { value int // 节点值 left *Node // 左子节点 right *Node // 右子节点 } // BinarySearchTree 定义二叉搜索树 type BinarySearchTree struct { root *Node // 根节点 } // NewBinarySearchTree 创建新的二叉搜索树 func NewBinarySearchTree() *BinarySearchTree { return &BinarySearchTree{root: nil} } // Insert 插入操作 func (bst *BinarySearchTree) Insert(value int) { bst.root = bst.insertRecursive(bst.root, value) } // insertRecursive 递归插入节点 func (bst *BinarySearchTree) insertRecursive(current *Node, value int) *Node { // 如果当前节点为空,创建新节点 if current == nil { return &Node{value: value, left: nil, right: nil} } // 递归插入到合适位置 if value < current.value { current.left = bst.insertRecursive(current.left, value) } else if value > current.value { current.right = bst.insertRecursive(current.right, value) } // 值已存在,不做任何操作 return current } // Search 查找操作 func (bst *BinarySearchTree) Search(value int) bool { return bst.searchRecursive(bst.root, value) } // searchRecursive 递归查找节点 func (bst *BinarySearchTree) searchRecursive(current *Node, value int) bool { // 空树或到达叶节点 if current == nil { return false } // 找到目标值 if value == current.value { return true } // 在左子树或右子树中查找 if value < current.value { return bst.searchRecursive(current.left, value) } else { return bst.searchRecursive(current.right, value) } } // Delete 删除操作 func (bst *BinarySearchTree) Delete(value int) { bst.root = bst.deleteRecursive(bst.root, value) } // deleteRecursive 递归删除节点 func (bst *BinarySearchTree) deleteRecursive(current *Node, value int) *Node { // 树为空或未找到要删除的值 if current == nil { return nil } // 找到要删除的节点 if value == current.value { // 情况1:叶节点 if current.left == nil && current.right == nil { return nil } // 情况2:只有一个子节点 if current.left == nil { return current.right } if current.right == nil { return current.left } // 情况3:有两个子节点 // 查找右子树中的最小值 smallestValue := bst.findSmallestValue(current.right) current.value = smallestValue // 删除右子树中的最小值节点 current.right = bst.deleteRecursive(current.right, smallestValue) return current } // 继续在左子树或右子树中查找 if value < current.value { current.left = bst.deleteRecursive(current.left, value) } else { current.right = bst.deleteRecursive(current.right, value) } return current } // findSmallestValue 查找子树中的最小值(最左侧节点) func (bst *BinarySearchTree) findSmallestValue(root *Node) int { if root.left == nil { return root.value } return bst.findSmallestValue(root.left) } // InorderTraversal 中序遍历(得到排序结果) func (bst *BinarySearchTree) InorderTraversal() []int { result := make([]int, 0) bst.inorderRecursive(bst.root, &result) return result } // inorderRecursive 递归中序遍历 func (bst *BinarySearchTree) inorderRecursive(current *Node, result *[]int) { if current != nil { bst.inorderRecursive(current.left, result) *result = append(*result, current.value) bst.inorderRecursive(current.right, result) } } // 主函数示例 func main() { // 创建二叉搜索树 bst := NewBinarySearchTree() // 插入节点 bst.Insert(8) bst.Insert(3) bst.Insert(10) bst.Insert(1) bst.Insert(6) bst.Insert(14) bst.Insert(4) bst.Insert(7) bst.Insert(13) // 查找节点 fmt.Println(bst.Search(6)) // 输出: true fmt.Println(bst.Search(9)) // 输出: false // 中序遍历 fmt.Println(bst.InorderTraversal()) // 输出: [1 3 4 6 7 8 10 13 14] // 删除节点 bst.Delete(6) fmt.Println(bst.InorderTraversal()) // 输出: [1 3 4 7 8 10 13 14] }
▼C++复制代码#include <iostream> #include <vector> // 定义节点类 class Node { public: int value; // 节点值 Node* left; // 左子节点 Node* right; // 右子节点 Node(int value) : value(value), left(nullptr), right(nullptr) {} }; // 定义二叉搜索树类 class BinarySearchTree { private: Node* root; // 根节点 // 递归插入节点 Node* insertRecursive(Node* current, int value) { // 如果当前节点为空,创建新节点 if (current == nullptr) { return new Node(value); } // 递归插入到合适位置 if (value < current->value) { current->left = insertRecursive(current->left, value); } else if (value > current->value) { current->right = insertRecursive(current->right, value); } // 值已存在,不做任何操作 return current; } // 递归查找节点 bool searchRecursive(Node* current, int value) { // 空树或到达叶节点 if (current == nullptr) { return false; } // 找到目标值 if (value == current->value) { return true; } // 在左子树或右子树中查找 if (value < current->value) { return searchRecursive(current->left, value); } else { return searchRecursive(current->right, value); } } // 递归删除节点 Node* deleteRecursive(Node* current, int value) { // 树为空或未找到要删除的值 if (current == nullptr) { return nullptr; } // 找到要删除的节点 if (value == current->value) { // 情况1:叶节点 if (current->left == nullptr && current->right == nullptr) { delete current; return nullptr; } // 情况2:只有一个子节点 if (current->left == nullptr) { return current->right; } if (current->right == nullptr) { return current->left; } // 情况3:有两个子节点 // 查找右子树中的最小值 int smallestValue = findSmallestValue(current->right); current->value = smallestValue; // 删除右子树中的最小值节点 current->right = deleteRecursive(current->right, smallestValue); return current; } // 继续在左子树或右子树中查找 if (value < current->value) { current->left = deleteRecursive(current->left, value); } else { current->right = deleteRecursive(current->right, value); } return current; } // 查找子树中的最小值(最左侧节点) int findSmallestValue(Node* root) { if (root->left == nullptr) { return root->value; } return findSmallestValue(root->left); } // 递归中序遍历 void inorderRecursive(Node* current, std::vector<int>& result) { if (current != nullptr) { inorderRecursive(current->left, result); result.push_back(current->value); inorderRecursive(current->right, result); } } // 递归释放内存 void clearRecursive(Node* node) { if (node != nullptr) { clearRecursive(node->left); clearRecursive(node->right); delete node; } } public: // 构造函数 BinarySearchTree() : root(nullptr) {} // 析构函数 ~BinarySearchTree() { clearRecursive(root); } // 插入操作 void insert(int value) { root = insertRecursive(root, value); } // 查找操作 bool search(int value) { return searchRecursive(root, value); } // 删除操作 void remove(int value) { root = deleteRecursive(root, value); } // 中序遍历(得到排序结果) std::vector<int> inorderTraversal() { std::vector<int> result; inorderRecursive(root, result); return result; } }; // 主函数示例 int main() { // 创建二叉搜索树 BinarySearchTree bst; // 插入节点 bst.insert(8); bst.insert(3); bst.insert(10); bst.insert(1); bst.insert(6); bst.insert(14); bst.insert(4); bst.insert(7); bst.insert(13); // 查找节点 std::cout << (bst.search(6) ? "true" : "false") << std::endl; // 输出: true std::cout << (bst.search(9) ? "true" : "false") << std::endl; // 输出: false // 中序遍历 std::vector<int> inorder = bst.inorderTraversal(); std::cout << "中序遍历: "; for (int value : inorder) { std::cout << value << " "; } std::cout << std::endl; // 输出: 中序遍历: 1 3 4 6 7 8 10 13 14 // 删除节点 bst.remove(6); inorder = bst.inorderTraversal(); std::cout << "删除6后中序遍历: "; for (int value : inorder) { std::cout << value << " "; } std::cout << std::endl; // 输出: 删除6后中序遍历: 1 3 4 7 8 10 13 14 return 0; }
为了解决普通二叉搜索树可能失衡的问题,人们实现了多种自平衡二叉搜索树:
测验答案
- 最多需要约log₂1000 ≈ 10次比较就能找到目标值。在最坏情况下(如果树完全失衡成为链表),需要1000次比较。
- 按照升序插入元素会形成一个右斜树(实际上是一个链表),这种结构失去了二叉搜索树的查找效率优势,所有操作的时间复杂度都退化为O(n)。
- 使用后继节点替换是为了保持二叉搜索树的性质。后继节点是大于当前节点的最小节点,它保证比当前节点的左子树中的所有节点大,同时比右子树中其他节点小。前驱节点(左子树中的最大值)也可以用来替换,因为它比当前节点的左子树中其他节点大,同时比当前节点的右子树中所有节点小。两种方法都能维持二叉搜索树的特性。选择使用哪一种通常取决于实现偏好或特定应用需求。