二叉搜索树

算法

二叉搜索树是一种二叉树,其中每个节点的左子树中的值都小于该节点的值,右子树中的值都大于该节点的值。这种特性使得二叉搜索树在查找、插入和删除操作上具有较高的效率。

空间复杂度:O(n)

算法讲解

二叉搜索树

介绍

二叉搜索树(Binary Search Tree,简称BST)是一种特殊的二叉树数据结构,它具有以下特点:对于树中的每个节点,其左子树中所有节点的值都小于该节点的值,右子树中所有节点的值都大于该节点的值。

核心特性

  1. 有序性:左子树上所有节点的值都小于根节点的值,右子树上所有节点的值都大于根节点的值
  2. 唯一性:树中不存在值相同的节点(标准实现中)
  3. 平均时间复杂度:查找、插入和删除操作的平均时间复杂度为O(log n),n是节点数量
  4. 最坏时间复杂度:如果树不平衡(比如形成链表),最坏情况下时间复杂度为O(n)
  5. 递归定义:每个子树也是一个二叉搜索树

基本操作

查找操作

  1. 从根节点开始
  2. 如果目标值等于当前节点值,则找到目标
  3. 如果目标值小于当前节点值,则在左子树中继续查找
  4. 如果目标值大于当前节点值,则在右子树中继续查找
  5. 如果到达叶节点仍未找到,则目标不存在

插入操作

  1. 从根节点开始
  2. 如果树为空,创建新节点作为根节点
  3. 如果新值小于当前节点值,则在左子树中继续(如果左子树为空,则创建新节点)
  4. 如果新值大于当前节点值,则在右子树中继续(如果右子树为空,则创建新节点)
  5. 如果新值等于当前节点值,根据实现可以选择忽略或更新节点

删除操作

删除操作较为复杂,需要考虑三种情况:

  1. 删除叶节点:直接移除
  2. 删除有一个子节点的节点:用子节点替换被删除的节点
  3. 删除有两个子节点的节点:
    • 找到右子树中的最小值节点(中序后继)
    • 用该节点的值替换要删除的节点值
    • 删除中序后继节点

基础实现

代码实现

Java

▼
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

▼
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

▼
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 实现

▼
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++ 实现

▼
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; }

优缺点

优点

  1. 查找效率高:在平衡状态下,查找、插入和删除的时间复杂度为O(log n)
  2. 有序性:中序遍历可以得到有序序列
  3. 范围查询:支持高效的范围查询操作
  4. 实现简单:相比其他高级树结构,实现较为简单直观
  5. 动态性:支持动态添加和删除元素

缺点

  1. 不自平衡:在最坏情况下(如顺序插入),可能退化为链表,性能下降到O(n)
  2. 空间开销:每个节点需要额外的指针空间
  3. 实际应用受限:在需要保证最坏情况性能的场景下,需要使用自平衡树变种(如AVL树、红黑树)
  4. 不适合频繁修改:频繁增删节点可能导致树失去平衡

扩展:自平衡二叉搜索树

为了解决普通二叉搜索树可能失衡的问题,人们实现了多种自平衡二叉搜索树:

  1. AVL树:通过旋转操作保持树的平衡,每个节点的左右子树高度差不超过1
  2. 红黑树:通过颜色标记和旋转操作保持近似平衡,广泛应用于许多编程语言的标准库中
  3. 伸展树(Splay Tree):在访问节点后通过旋转将其移至根部,适合有访问局部性的应用
  4. B树和B+树:多路搜索树,主要用于数据库和文件系统

测验

  1. 在一个包含1000个节点的平衡二叉搜索树中,最多需要多少次比较才能找到一个特定的值?在最坏情况下呢?
  2. 如果按照升序插入元素 1, 2, 3, 4, 5, 6, 7 到一个空的二叉搜索树中,会形成什么样的树结构?这种结构有什么问题?
  3. 当删除一个有两个子节点的节点时,为什么要用后继节点(右子树中的最小值)来替换?是否可以使用前驱节点(左子树中的最大值)?

测验答案

  1. 最多需要约log₂1000 ≈ 10次比较就能找到目标值。在最坏情况下(如果树完全失衡成为链表),需要1000次比较。
  2. 按照升序插入元素会形成一个右斜树(实际上是一个链表),这种结构失去了二叉搜索树的查找效率优势,所有操作的时间复杂度都退化为O(n)。
  3. 使用后继节点替换是为了保持二叉搜索树的性质。后继节点是大于当前节点的最小节点,它保证比当前节点的左子树中的所有节点大,同时比右子树中其他节点小。前驱节点(左子树中的最大值)也可以用来替换,因为它比当前节点的左子树中其他节点大,同时比当前节点的右子树中所有节点小。两种方法都能维持二叉搜索树的特性。选择使用哪一种通常取决于实现偏好或特定应用需求。

相关的 LeetCode 热门题目

  1. 98. 验证二叉搜索树 - 要求验证一个给定的二叉树是否是有效的二叉搜索树。
  2. 700. 二叉搜索树中的搜索 - 在二叉搜索树中查找指定值的节点。
  3. 701. 二叉搜索树中的插入操作 - 在不破坏二叉搜索树性质的前提下插入新节点。
  4. 450. 删除二叉搜索树中的节点 - 实现二叉搜索树的删除操作。