常用查找算法整理（顺序查找、二分查找、哈希查找、二叉排序树查找、平衡二 ...

常用的查找算法：

• 顺序查找：最简单的查找算法，实用于无序或数据量小的环境，逐个元素比较查找目标值。
  
• 二分查找：要求数据有序，通过不断比较中间元素与目标值，将查找范围缩小一半，效率较高。
  
• 哈希查找：使用哈希函数将键值映射到特定存储位置，能在较短时间内实现查找，常用于数据量较大且对查找速率要求高的场景。
  
• 二叉排序树查找：基于二叉排序树数据布局，左子树节点值小于根节点值，右子树节点值大于根节点值，通过比较和递归进行查找。
  
• 平衡二叉树查找：如AVL树、红黑树等，在二叉排序树基础上保持平衡，提高查找效率，实用于数据动态变化频仍的场景。
  
• 红黑树查找：红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。常常用于编程语言的标准库、操纵系统的内存管理、数据库索引。
  
• B树和B+树查找：常用于文件系统和数据库系统的索引布局，能高效处理大量数据的查找和范围查询。
  
• 分块查找：将数据分块，块内无序但块间有序，先确定块再在块内查找，性能介于顺序查找和二分查找之间。
  
• 斐波那契查找和插值查找在特定场景下有其独特的上风，但整体而言，它们不如顺序查找、二分查找等方法常用，
  

顺序查找

根本概念
顺序查找，也称为线性查找，是在一个数据聚会集从第一个元素开始，逐个比较元素，直到找到目标元素或遍历完备个聚集为止的查找方法。它实用于无序的线性表，也可用于有序的线性表。
算法实现

• 一般实现步骤
  
  
  
  • 从数据聚集的第一个元素开始。
    
  • 将当前元素与要查找的目标元素进行比较。
    
  • 如果当前元素等于目标元素，则查找成功，返回当前元素的位置。
    
  • 如果当前元素不等于目标元素，则继续比较下一个元素。
    
  • 重复上述步骤，直到找到目标元素或者遍历完备个数据聚集。如果遍历完备个聚集仍未找到目标元素，则查找失败，返回特定的标识（如-1）。
    
  
  
• Python代码示例
  

1. def sequential_search(lst, target):
2.     for i, element in enumerate(lst):
3.         if element == target:
4.             return i
5.     return -1
7. # 测试
8. lst = [10, 20, 30, 40, 50]
9. target = 30
10. print(sequential_search(lst, target))  

复制代码

时间复杂度

• 最好环境：目标元素在数据聚集的第一个位置，只需比较1次，时间复杂度为                                        O                            (                            1                            )                                  O(1)                     O(1)。
  
• 最坏环境：目标元素在数据聚集的末了一个位置，或者数据聚会集根本不存在目标元素，需要比较                                        n                                  n                     n次，时间复杂度为                                        O                            (                            n                            )                                  O(n)                     O(n)，此中                                        n                                  n                     n是数据聚会集元素的个数。
  
• 匀称环境：假设目标元素在数据聚会集的任何位置出现的概率相等，匀称需要比较                                                               n                                  +                                  1                                          2                                            \frac{n + 1}{2}                     2n+1​次，时间复杂度也为                                        O                            (                            n                            )                                  O(n)                     O(n)。
  

优缺点

• 优点
  
  
  
  • 算法简单，易于理解和实现。
    
  • 对数据聚集的存储布局没有特殊要求，无论是顺序存储还是链式存储都可以使用。
    
  • 对于规模较小的数据聚集，顺序查找的效率不会有显着的问题，并且在某些特定环境下（如数据聚集动态变化频仍，无法进行其他更高效的预处理时），顺序查找是一种可行的选择。
    
  
  
• 缺点
  
  
  
  • 对于规模较大的数据聚集，查找效率较低，由于匀称需要比较大量的元素。
    
  
  

实用场景

• 数据量较小：当数据聚会集的元素数目较少时，顺序查找的简单性和直接性使其成为一种合适的选择，由于在这种环境下，查找操纵的资源相对较低，不会对性能产生太大影响。
  
• 数据无序且动态变化：如果数据是无序的，并且常常需要进行插入和删除操纵，导致数据难以进行有用的组织和索引，那么顺序查找可以在不进行额外维护操纵的环境下进行查找。
  
• 一次性查找：对于只进行偶尔的、一次性的查找操纵，而不思量对整体查找性能进行优化的环境，顺序查找可以快速实现查找功能，而无需为了提高查找效率而引入复杂的算法和数据布局。
  

二分查找

根本原理
二分查找也称为折半查找，其根本思想是：每次将待查找区间缩小为原来的一半，通过不断比较中间元素与目标元素的巨细关系，来确定下一步的查找区间，直到找到目标元素或者确定目标元素不存在为止。
算法实现

• 一般实现步骤
  
  
  
  • 首先，确定待查找区间的左右边界，左边界left初始化为0，右边界right初始化为数组长度减1。
    
  • 进入循环，只要left <= right，就继续查找。
    
  • 在循环中，盘算中间位置mid，通常使用mid = left + (right - left) // 2的方式盘算，以避免整数溢出。
    
  • 将中间位置的元素与目标元素进行比较。
    
    
    
    • 如果中间元素等于目标元素，则查找成功，返回中间位置mid。
      
    • 如果中间元素大于目标元素，分析目标元素在中间元素的左侧，更新右边界right = mid - 1。
      
    • 如果中间元素小于目标元素，分析目标元素在中间元素的右侧，更新左边界left = mid + 1。
      
    
    
  • 如果循环结束后仍未找到目标元素，则查找失败，返回特定的标识（如-1）。
    
  
  

Python代码示例

1. def binary_search(lst, target):
2.     left, right = 0, len(lst) - 1
3.     while left <= right:
4.         mid = left + (right - left) // 2
5.         if lst[mid] == target:
6.             return mid
7.         elif lst[mid] > target:
8.             right = mid - 1
9.         else:
10.             left = mid + 1
11.     return -1
13. # 测试
14. lst = [10, 20, 30, 40, 50]
15. target = 30
16. print(binary_search(lst, target))  

复制代码

时间复杂度

• 最好环境：目标元素正好是中间元素，只需比较1次，时间复杂度为                                        O                            (                            1                            )                                  O(1)                     O(1)。
  
• 最坏环境：需要不断地将区间缩小一半，直到只剩下一个元素，时间复杂度为                                        O                            (                            l                            o                                       g                               2                                      n                            )                                  O(log_2n)                     O(log2​n)，此中                                        n                                  n                     n是数组中元素的个数。
  
• 匀称环境：匀称时间复杂度也为                                        O                            (                            l                            o                                       g                               2                                      n                            )                                  O(log_2n)                     O(log2​n)。
  

优缺点

• 优点
  
  
  
  • 查找速率快，相比于顺序查找，在大规模的有序数据中，二分查找的效率要高得多。
    
  • 时间复杂度低，对数级别的时间复杂度使得随着数据规模的增大，查找时间的增长相对迟钝。
    
  
  
• 缺点
  
  
  
  • 要求数据必须是有序的，因此在数据插入或删除操纵频仍的环境下，维护数据的有序性可能会带来额外的开销。
    
  • 对数据的存储布局有肯定要求，通常需要使用数组这种支持随机访问的数据布局，对于链表等不支持随机访问的数据布局，二分查找的效率会大大降低。
    
  
  

实用场景

• 数据量较大且有序：当处理大规模的有序数据集适时，二分查找可以或许充分发挥其高效的上风，快速定位目标元素。
  
• 静态数据：对于相对稳固、不常常进行插入和删除操纵的数据，二分查找是一种抱负的查找算法，由于不需要频仍地调整数据的顺序来维护有序性。
  
• 需要频仍查找：在需要多次进行查找操纵的场景下，二分查找的高效性可以或许显着提高整体的性能，减少查找的总时间。
  

哈希查找

根本原理

• 哈希函数：哈希查找的核心是哈希函数，它是一个将数据元素的键值key映射为一个固定巨细的整数（通常称为哈希值或哈希码）的函数，用hash(key)表示。抱负环境下，哈希函数应该具有精良的匀称性，即对于不同的键值，可以或许匀称地分布在哈希表的各个位置上，以减少辩说的发生。
  
• 哈希表：哈希表是用于存储数据元素的数据布局，它的巨细通常是固定的。通过哈希函数盘算出的哈希值作为索引，将数据元素存储在哈希表的相应位置上。当需要查找某个数据元素时，再次使用哈希函数盘算其键值的哈希值，然后直接访问哈希表中对应的位置，就可以快速找到该元素。
  

解决辩说的方法

• 开放定址法：当有新的数据要插入到哈希表中，发现目标位置已经被占用时，就按照肯定的规则探求下一个空闲的位置来插入。常见的探测序列有线性探测、二次探测等。线性探测就是依次探测下一个位置，即(hash(key)+i) % m，此中i = 1,2,3,...，m为哈希表的巨细。二次探测则是按照(hash(key)+i^2) % m的方式探测。
  
• 链地点法：将所有哈希值相同的数据元素存储在一个链表中。当插入一个新元素时，盘算其哈希值，然后将其插入到对应的链表头部或尾部。查找时，先盘算哈希值找到对应的链表，然后在链表中顺序查找目标元素。
  

算法实现
以下是使用链地点法实现哈希查找的Python代码示例：

1. class HashTable:
2.     def __init__(self, size):
3.         self.size = size
4.         self.table = [[] for _ in range(size)]
6.     def hash_function(self, key):
7.         return key % self.size
9.     def insert(self, key, value):
10.         hash_value = self.hash_function(key)
11.         self.table[hash_value].append((key, value))
13.     def search(self, key):
14.         hash_value = self.hash_function(key)
15.         for k, v in self.table[hash_value]:
16.             if k == key:
17.                 return v
18.         return None
20. # 测试
21. hash_table = HashTable(10)
22. hash_table.insert(1, 'apple')
23. hash_table.insert(11, 'banana')
24. print(hash_table.search(11))  

复制代码

时间复杂度

• 抱负环境：如果哈希函数计划得非常好，所有的数据元素都匀称地分布在哈希表中，那么每次查找只需要访问一次哈希表，时间复杂度为                                        O                            (                            1                            )                                  O(1)                     O(1)。
  
• 最坏环境：当所有的数据元素都映射到同一个哈希值时，哈希表退化为一个链表，此时查找的时间复杂度为                                        O                            (                            n                            )                                  O(n)                     O(n)，此中n是数据元素的个数。
  
• 匀称环境：在合理的哈希函数和适当的负载因子（即哈希表中已存储元素的数目与哈希表巨细的比值）下，哈希查找的匀称时间复杂度为                                        O                            (                            1                            )                                  O(1)                     O(1)或接近                                        O                            (                            1                            )                                  O(1)                     O(1)。
  

优缺点

• 优点
  
  
  
  • 查找速率快：在抱负环境下，哈希查找可以或许在常数时间内完成查找操纵，这使得它在大规模数据处理中具有很高的效率。
    
  • 对数据无顺序要求：与二分查找等算法不同，哈希查找不需要数据是有序的，数据可以以恣意顺序插入到哈希表中。
    
  
  
• 缺点
  
  
  
  • 哈希函数计划困难：要计划一个完善的哈希函数黑白常困难的，需要思量数据的分布特点等因素，以避免辩说过多导致性能下降。
    
  • 空间开销较大：为了减少辩说，通常需要分配比现实数据量更大的哈希表空间，这可能会造成肯定的空间浪费。
    
  
  

实用场景

• 数据快速查找和插入：在需要频仍进行查找和插入操纵的场景中，如数据库索引、缓存系统等，哈希查找可以或许提供高效的性能。
  
• 数据唯一性判断：可以使用哈希查找来快速判断数据是否已经存在，例如在查重系统中，通过盘算数据的哈希值并在哈希表中查找，可以快速确定命据是否重复。
  
• 海量数据处理：在处理海量数据时，哈希查找可以将数据分散到不同的位置，便于进行分布式存储和处理。
  

树查找

二叉排序树

定义
二叉排序树（Binary Search Tree，BST），也称为二叉查找树、二叉搜索树，它是一种特殊的二叉树。对于树中的恣意一个节点，都满足以下性质：

• 若该节点的左子树不为空，则左子树上所有节点的值均小于该节点的值。
  
• 若该节点的右子树不为空，则右子树上所有节点的值均大于该节点的值。
  
• 该节点的左子树和右子树也分别是二叉排序树。
  

示例
以下是一个简单的二叉排序树示例，树中节点的值分别为 50、30、70、20、40、60、80：

1.         50
2.        /  \
3.      30    70
4.     /  \   / \
5.   20   40 60  80

复制代码

在这个二叉排序树中，节点 50 的左子树（30、20、40）中的所有节点值都小于 50，右子树（70、60、80）中的所有节点值都大于 50。并且节点 30 的左子树（20）节点值小于 30，右子树（40）节点值大于 30，以此类推。
插入操纵
插入新节点时，从根节点开始比较。如果新节点的值小于当前节点的值，则在左子树中继续查找插入位置；如果新节点的值大于当前节点的值，则在右子树中继续查找插入位置，直到找到一个空位置插入新节点。
例如，要在上述二叉排序树中插入节点 35，从根节点 50 开始，35 小于 50，进入左子树；35 大于 30，进入 30 的右子树；此时 30 的右子树节点 40 存在，35 小于 40，进入 40 的左子树，发现为空，将 35 插入该位置。
删除操纵
删除操纵相对复杂，需要分三种环境：

• 要删除的节点是叶子节点：直接删除该节点即可。
  
• 要删除的节点只有一个子节点：用该子节点替换要删除的节点。
  
• 要删除的节点有两个子节点：找到该节点右子树中的最小节点（或左子树中的最大节点），用这个最小节点的值替换要删除节点的值，然后删除右子树中的最小节点。
  

二叉排序树搜索
搜索过程
在二叉排序树中搜索一个特定值的过程如下：

• 从根节点开始，将待搜索的值与根节点的值进行比较。
  
• 如果待搜索的值等于根节点的值，则搜索成功，返回该节点。
  
• 如果待搜索的值小于根节点的值，由于二叉排序树的性质，该值只可能在左子树中，因此在左子树中继续进行搜索。
  
• 如果待搜索的值大于根节点的值，该值只可能在右子树中，因此在右子树中继续进行搜索。
  
• 重复上述步骤，直到找到目标节点或者碰到空节点（表示搜索失败）。
  

代码实现（Python）

1. class TreeNode:
2.     def __init__(self, val=0, left=None, right=None):
3.         self.val = val
4.         self.left = left
5.         self.right = right
7. def searchBST(root, val):
8.     if root is None or root.val == val:
9.         return root
10.     if val < root.val:
11.         return searchBST(root.left, val)
12.     return searchBST(root.right, val)
14. # 构建示例二叉排序树
15. root = TreeNode(50)
16. root.left = TreeNode(30)
17. root.right = TreeNode(70)
18. root.left.left = TreeNode(20)
19. root.left.right = TreeNode(40)
20. root.right.left = TreeNode(60)
21. root.right.right = TreeNode(80)
23. # 搜索值为 60 的节点
24. result = searchBST(root, 60)
25. if result:
26.     print(f"找到了值为 {result.val} 的节点")
27. else:
28.     print("未找到该节点")

复制代码

复杂度分析

• 时间复杂度：匀称环境下，二叉排序树的高度为                                         O                            (                            l                            o                            g                            n                            )                                  O(log n)                     O(logn)（此中                                         n                                  n                     n 是树中节点的数目），搜索操纵的时间复杂度为                                         O                            (                            l                            o                            g                            n                            )                                  O(log n)                     O(logn)。但在最坏环境下，即二叉排序树退化为链表（例如插入的节点值是有序的），树的高度为                                         O                            (                            n                            )                                  O(n)                     O(n)，搜索操纵的时间复杂度会变为                                         O                            (                            n                            )                                  O(n)                     O(n)。
  
• 空间复杂度：主要取决于递归调用栈的深度，匀称环境下为                                         O                            (                            l                            o                            g                            n                            )                                  O(log n)                     O(logn)，最坏环境下为                                         O                            (                            n                            )                                  O(n)                     O(n)。如果使用迭代方式实现搜索，空间复杂度可以优化到                                         O                            (                            1                            )                                  O(1)                     O(1)。
  

应用场景
二叉排序树实用于需要频仍进行插入、删除和搜索操纵的场景，并且数据聚集的规模适中。例如，在一些小型的数据库系统中，用于快速查找特定记载；在编程语言的符号表管理中，用于存储和查找变量名及其相干信息等。
平衡二叉树

定义
平衡二叉树（AVL树）是一种自平衡的二叉搜索树。它满足二叉搜索树的根天性质：对于树中的恣意节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。同时，AVL树还额外要求每个节点的左右子树的高度差（平衡因子）的绝对值不超过 1。平衡因子定义为该节点的左子树高度减去右子树高度。
平衡的重要性
通过保持树的平衡，AVL树可以或许保证在进行插入、删除和查找操纵时的时间复杂度始终为                                    O                         (                         l                         o                         g                         n                         )                              O(log n)                  O(logn)，此中                                    n                              n                  n 是树中节点的数目。如果不进行平衡操纵，二叉搜索树可能会退化为链表，此时这些操纵的时间复杂度会变为                                    O                         (                         n                         )                              O(n)                  O(n)。
平衡二叉树查找过程
平衡二叉树的查找过程与普通二叉搜索树的查找过程根本同等：

• 从根节点开始，将待查找的值 target 与当前节点的值进行比较。
  
• 如果 target 等于当前节点的值，则查找成功，返回该节点。
  
• 如果 target 小于当前节点的值，则在当前节点的左子树中继续查找。
  
• 如果 target 大于当前节点的值，则在当前节点的右子树中继续查找。
  
• 重复上述步骤，直到找到目标节点或者碰到空节点（表示查找失败）。
  

示例代码（Python 实现）

1. # 定义 AVL 树的节点类
2. class TreeNode:
3.     def __init__(self, key):
4.         self.key = key
5.         self.left = None
6.         self.right = None
7.         self.height = 1  # 节点的高度，初始为 1
9. # 定义 AVL 树类
10. class AVLTree:
11.     # 获取节点的高度
12.     def get_height(self, node):
13.         if not node:
14.             return 0
15.         return node.height
17.     # 获取节点的平衡因子
18.     def get_balance(self, node):
19.         if not node:
20.             return 0
21.         return self.get_height(node.left) - self.get_height(node.right)
23.     # 右旋操作
24.     def right_rotate(self, y):
25.         x = y.left
26.         T2 = x.right
28.         x.right = y
29.         y.left = T2
31.         y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
32.         x.height = max(self.get_height(x.left), self.get_height(x.right)) + 1
34.         return x
36.     # 左旋操作
37.     def left_rotate(self, x):
38.         y = x.right
39.         T2 = y.left
41.         y.left = x
42.         x.right = T2
44.         x.height = max(self.get_height(x.left), self.get_height(x.right)) + 1
45.         y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
47.         return y
49.     # 插入节点
50.     def insert(self, root, key):
51.         if not root:
52.             return TreeNode(key)
53.         elif key < root.key:
54.             root.left = self.insert(root.left, key)
55.         else:
56.             root.right = self.insert(root.right, key)
58.         root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
60.         balance = self.get_balance(root)
62.         # 左左情况
63.         if balance > 1 and key < root.left.key:
64.             return self.right_rotate(root)
66.         # 右右情况
67.         if balance < -1 and key > root.right.key:
68.             return self.left_rotate(root)
70.         # 左右情况
71.         if balance > 1 and key > root.left.key:
72.             root.left = self.left_rotate(root.left)
73.             return self.right_rotate(root)
75.         # 右左情况
76.         if balance < -1 and key < root.right.key:
77.             root.right = self.right_rotate(root.right)
78.             return self.left_rotate(root)
80.         return root
82.     # 查找节点
83.     def search(self, root, key):
84.         if root is None or root.key == key:
85.             return root
86.         if key < root.key:
87.             return self.search(root.left, key)
88.         return self.search(root.right, key)
90. # 测试代码
91. if __name__ == "__main__":
92.     avl_tree = AVLTree()
93.     root = None
94.     keys = [9, 5, 10, 0, 6, 11, -1, 1, 2]
96.     for key in keys:
97.         root = avl_tree.insert(root, key)
99.     target = 6
100.     result = avl_tree.search(root, target)
101.     if result:
102.         print(f"找到了节点: {result.key}")
103.     else:
104.         print(f"未找到节点: {target}")

复制代码

代码表明

• TreeNode 类：定义了 AVL 树的节点布局，包含节点的值 key、左右子节点 left 和 right 以及节点的高度 height。
  
• AVLTree 类：
  
  
  
  • get_height 方法：用于获取节点的高度。
    
  • get_balance 方法：用于盘算节点的平衡因子。
    
  • right_rotate 和 left_rotate 方法：分别实现了右旋和左旋操纵，用于调整树的平衡。
    
  • insert 方法：插入新节点，并在插入后检查树的平衡环境，须要时进行旋转操纵以保持树的平衡。
    
  • search 方法：实现了查找功能，通过递归的方式在树中查找目标节点。
    
  
  
• 测试部门：创建一个 AVL 树，插入一系列节点，然后查找目标节点 6，并输出查找效果。
  

通过这种方式，我们可以在平衡二叉树中高效地进行查找操纵。
复杂度分析

• 时间复杂度
  
• 
  
  
  
  • 匀称环境：在平衡二叉树（AVL树）中，由于它始终保持着左右子树高度差不超过 1 的平衡特性，树的高度                                                   h                                          h                           h 始终维持在                                                   O                                  (                                  log                                  ⁡                                  n                                  )                                          O(\log n)                           O(logn) 级别，此中                                                   n                                          n                           n 是树中节点的数目。而查找操纵需要从根节点开始，沿着一条路径向下搜索，颠末的节点数最多为树的高度。因此，匀称环境下平衡二叉树查找操纵的时间复杂度为                                                   O                                  (                                  log                                  ⁡                                  n                                  )                                          O(\log n)                           O(logn)。例如，当树中有 1024 个节点时，树的高度约莫为                                                                              log                                        ⁡                                                  2                                              1024                                  =                                  10                                          \log_2{1024}=10                           log2​1024=10，查找操纵最多只需比较 10 次。
    
  
  
• 
  
  
  
  • 最坏环境：由于平衡二叉树严格保证了树的平衡性，即使在最坏环境下，树的高度依然是                                                   O                                  (                                  log                                  ⁡                                  n                                  )                                          O(\log n)                           O(logn)，所以查找操纵的时间复杂度仍然是                                                   O                                  (                                  log                                  ⁡                                  n                                  )                                          O(\log n)                           O(logn)。这与普通二叉搜索树不同，普通二叉搜索树在最坏环境下（退化为链表）查找时间复杂度会达到                                                   O                                  (                                  n                                  )                                          O(n)                           O(n)。
    
  
  

空间复杂度

• 平衡二叉树查找操纵的空间复杂度主要取决于递归调用栈的深度。在递归查找过程中，每次递归调用会在栈上分配肯定的空间。由于查找路径的长度最长为树的高度，而树的高度为                                         O                            (                            log                            ⁡                            n                            )                                  O(\log n)                     O(logn)，所以查找操纵的空间复杂度为                                         O                            (                            log                            ⁡                            n                            )                                  O(\log n)                     O(logn)。如果采用迭代方式实现查找，空间复杂度可以优化到                                         O                            (                            1                            )                                  O(1)                     O(1)，由于只需要使用常数级的额外空间来记载当前节点的位置。
  

适合使用的场景

• 当数据聚集需要频仍进行插入、删除和查找操纵时，平衡二叉树是一个不错的选择。例如，在数据库的索引系统中，数据会不断地被插入和删除，同时也需要快速地查找特定的数据记载。平衡二叉树可以或许在保证插入和删除操纵相对高效的同时，确保查找操纵的时间复杂度始终为                                              O                               (                               log                               ⁡                               n                               )                                      O(\log n)                        O(logn)。
  
• 对于一些对查找速率要求极高的应用，如搜索引擎的缓存系统、及时数据处理系统等，平衡二叉树的高效查找性能可以或许满足这些场景的需求。以搜索引擎的缓存系统为例，需要快速地查找缓存中是否存在某个网页的信息，平衡二叉树可以在较短的时间内完成查找操纵，提高系统的响应速率。
  
• 如果只需要快速查找特定的数据，而不需要数据始终保持严格的有序性，平衡二叉树可以很好地满足需求。例如，在一些游戏的物品管理系统中，需要快速查找某个物品的属性信息，平衡二叉树可以高效地实现这一功能，而不需要像排序数组那样始终保持数据的严格有序。
  

红黑树

定义
红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。通过对任何一条从根到叶子的路径上各个节点着色方式的限定，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。红黑树必须满足以下五个性质：

• 每个节点要么是红色，要么是黑色。
  
• 根节点是黑色。
  
• 每个叶子节点（NIL节点，空节点）是黑色。
  
• 如果一个节点是红色的，则它的两个子节点都是黑色的。
  
• 对每个节点，从该节点到其所有子女叶节点的简单路径上，均包含相同数目的黑色节点。
  

示例
以下是一个简单的红黑树示例（为方便表示，这里用括号内的 R 表示红色节点，B 表示黑色节点）：

1.         (50B)
2.        /      \
3.     (30R)      (70R)
4.    /    \      /    \
5. (20B)  (40B) (60B)  (80B)

复制代码

在这个红黑树中，根节点 50 是黑色，红色节点 30 和 70 的子节点都是黑色，并且从每个节点到其所有子女叶节点的简单路径上黑色节点的数目相同。
红黑树查找
查找过程
红黑树的查找过程与普通二叉搜索树的查找过程根本相同，具体步骤如下：

• 从根节点开始，将待查找的值与根节点的值进行比较。
  
• 如果待查找的值等于根节点的值，则查找成功，返回该节点。
  
• 如果待查找的值小于根节点的值，由于红黑树也是二叉搜索树，该值只可能在左子树中，因此在左子树中继续进行查找。
  
• 如果待查找的值大于根节点的值，该值只可能在右子树中，因此在右子树中继续进行查找。
  
• 重复上述步骤，直到找到目标节点或者碰到空节点（表示查找失败）。
  

代码实现（Python）

1. class TreeNode:
2.     def __init__(self, val=0, color='R', left=None, right=None):
3.         self.val = val
4.         self.color = color
5.         self.left = left
6.         self.right = right
8. def searchRedBlackTree(root, val):
9.     if root is None or root.val == val:
10.         return root
11.     if val < root.val:
12.         return searchRedBlackTree(root.left, val)
13.     return searchRedBlackTree(root.right, val)
15. # 构建简单红黑树示例（这里只是简单构建，未完整体现插入调整逻辑）
16. root = TreeNode(50, 'B')
17. root.left = TreeNode(30, 'R')
18. root.right = TreeNode(70, 'R')
19. root.left.left = TreeNode(20, 'B')
20. root.left.right = TreeNode(40, 'B')
21. root.right.left = TreeNode(60, 'B')
22. root.right.right = TreeNode(80, 'B')
24. # 查找值为 60 的节点
25. result = searchRedBlackTree(root, 60)
26. if result:
27.     print(f"找到了值为 {result.val} 的节点")
28. else:
29.     print("未找到该节点")

复制代码

复杂度分析

• 时间复杂度：由于红黑树是接近平衡的，其高度始终保持在                                         O                            (                            l                            o                            g                            n                            )                                  O(log n)                     O(logn) 级别（此中                                         n                                  n                     n 是树中节点的数目），因此查找操纵的时间复杂度为                                         O                            (                            l                            o                            g                            n                            )                                  O(log n)                     O(logn)。这意味着在大规模数据聚会集，红黑树查找可以或许保持较高的效率。
  
• 空间复杂度：主要取决于递归调用栈的深度，匀称环境下为                                         O                            (                            l                            o                            g                            n                            )                                  O(log n)                     O(logn)，最坏环境下也为                                         O                            (                            l                            o                            g                            n                            )                                  O(log n)                     O(logn)。如果使用迭代方式实现查找，空间复杂度可以优化到                                         O                            (                            1                            )                                  O(1)                     O(1)。
  

应用场景
红黑树在很多领域都有广泛的应用，以下是一些常见的场景：

• 编程语言的标准库：如 Java 的 TreeMap 和 TreeSet、C++ 的 STL 中的 map 和 set 等，使用红黑树的特性实现了有序的键值对存储和快速查找功能。
  
• 操纵系统的内存管理：在操纵系统中，红黑树可用于管理内存块的分配和开释，通过红黑树可以快速查找合适的内存块。
  
• 数据库索引：在数据库系统中，红黑树可以作为索引布局，提高数据的查找效率，特殊是对于需要频仍进行插入、删除和查找操纵的场景。
  

B 树和B+数查询

B树

定义
B 树是一种自平衡的多路搜索树，它可以或许保持数据有序，并且答应在对数时间内进行插入、删除和查找操纵。B 树的每个节点可以有多个子节点（通常大于 2），并且所有叶子节点都在同一层。一个 m 阶的 B 树需要满足以下条件：

• 每个节点最多有 m 个子节点。
  
• 除根节点和叶子节点外，每个节点至少有                                         ⌈                            m                            /                            2                            ⌉                                  \lceil m/2 \rceil                     ⌈m/2⌉ 个子节点。
  
• 根节点至少有 2 个子节点（除非它是叶子节点）。
  
• 所有叶子节点都在同一层。
  
• 每个节点中的键值按升序排列，并且键值的数目比子节点数目少 1。
  

示例
下面是一个 3 阶 B 树的简单示例：

1.           [30, 60]
2.         /    |    \
3.     [10, 20] [40, 50] [70, 80]

复制代码

在这个 3 阶 B 树中，根节点包含两个键值 30 和 60，有三个子节点。每个子节点包含两个键值，并且键值是有序排列的。
B 树查找过程

• 从根节点开始，将待查找的值与根节点中的键值进行比较。
  
• 如果待查找的值等于根节点中的某个键值，则查找成功，返回该键值所在的位置。
  
• 如果待查找的值小于根节点中的某个键值，则进入该键值左侧的子节点继续查找。
  
• 如果待查找的值大于根节点中的所有键值，则进入最右侧的子节点继续查找。
  
• 重复上述步骤，在子节点中继续比较和查找，直到找到目标键值或者到达叶子节点。如果到达叶子节点仍未找到目标键值，则查找失败。
  

代码实现（Python 伪代码）

1. class BTreeNode:
2.     def __init__(self, is_leaf=False):
3.         self.is_leaf = is_leaf
4.         self.keys = []
5.         self.child = []
7. class BTree:
8.     def __init__(self, m):
9.         self.root = BTreeNode(is_leaf=True)
10.         self.m = m
12.     def search(self, key):
13.         return self._search(self.root, key)
15.     def _search(self, node, key):
16.         i = 0
17.         while i < len(node.keys) and key > node.keys[i]:
18.             i += 1
19.         if i < len(node.keys) and key == node.keys[i]:
20.             return node
21.         if node.is_leaf:
22.             return None
23.         return self._search(node.child[i], key)
25. # 示例使用
26. b_tree = BTree(3)
27. # 这里省略插入节点的代码
28. result = b_tree.search(40)
29. if result:
30.     print("找到了键值 40")
31. else:
32.     print("未找到键值 40")

复制代码

复杂度分析

• 时间复杂度：B 树的高度                                         h                                  h                     h 与节点数目                                         n                                  n                     n 的关系为                                         h                            =                            O                            (                                                   log                                  ⁡                                                      ⌈                                  m                                  /                                  2                                  ⌉                                                 n                            )                                  h = O(\log_{\lceil m/2 \rceil} n)                     h=O(log⌈m/2⌉​n)，此中                                         m                                  m                     m 是 B 树的阶数。因此，B 树查找操纵的时间复杂度为                                         O                            (                                                   log                                  ⁡                                                      ⌈                                  m                                  /                                  2                                  ⌉                                                 n                            )                                  O(\log_{\lceil m/2 \rceil} n)                     O(log⌈m/2⌉​n)，在现实应用中，由于                                         m                                  m                     m 通常较大，查找效率较高。
  
• 空间复杂度：主要取决于树中节点的数目，空间复杂度为                                         O                            (                            n                            )                                  O(n)                     O(n)。
  

应用场景
B 树常用于文件系统和数据库系统中，由于它可以有用减少磁盘 I/O 次数。在这些系统中，数据通常存储在磁盘上，磁盘 I/O 操纵的时间开销较大，B 树的多路特性使得每次磁盘 I/O 可以读取或写入多个键值，从而提高了系统的性能。
B + 树

定义
B + 树是 B 树的一种变体，它与 B 树的主要区别在于：

• 所有的数据都存储在叶子节点中，非叶子节点只存储索引信息。
  
• 叶子节点之间通过指针相连，形成一个有序链表。
  

示例
以下是一个简单的 B + 树示例：

1.          [30, 60]
2.         /      \
3.     [10, 20]    [40, 50, 70, 80]
4.     |         /   |   \
5.     10       40   50   70 - 80 （叶子节点相连）

复制代码

在这个 B + 树中，非叶子节点只包含索引键值 30 和 60，所有的数据（10、20、40、50、70、80）都存储在叶子节点中，并且叶子节点通过指针形成了有序链表。
B + 树查找过程

• 准确查找：从根节点开始，按照与 B 树雷同的方式，将待查找的值与非叶子节点中的键值进行比较，确定进入哪个子节点继续查找，直到到达叶子节点。在叶子节点中线性查找目标键值。
  
• 范围查找：先通过准确查找找到范围的起始键值所在的叶子节点，然后使用叶子节点之间的指针顺序遍历，直到找到范围的结束键值或超出范围。
  

代码实现（Python 伪代码）

1. class BPlusTreeNode:
2.     def __init__(self, is_leaf=False):
3.         self.is_leaf = is_leaf
4.         self.keys = []
5.         self.child = []
6.         self.next = None
8. class BPlusTree:
9.     def __init__(self, m):
10.         self.root = BPlusTreeNode(is_leaf=True)
11.         self.m = m
13.     def search(self, key):
14.         node = self.root
15.         while not node.is_leaf:
16.             i = 0
17.             while i < len(node.keys) and key > node.keys[i]:
18.                 i += 1
19.             node = node.child[i]
20.         for k in node.keys:
21.             if k == key:
22.                 return True
23.         return False
25. # 示例使用
26. b_plus_tree = BPlusTree(3)
27. # 这里省略插入节点的代码
28. result = b_plus_tree.search(50)
29. if result:
30.     print("找到了键值 50")
31. else:
32.     print("未找到键值 50")

复制代码

复杂度分析

• 时间复杂度：与 B 树雷同，B + 树的查找操纵时间复杂度也为                                         O                            (                                                   log                                  ⁡                                                      ⌈                                  m                                  /                                  2                                  ⌉                                                 n                            )                                  O(\log_{\lceil m/2 \rceil} n)                     O(log⌈m/2⌉​n)。对于范围查找，由于叶子节点之间有指针相连，时间复杂度为                                         O                            (                            k                            +                                                   log                                  ⁡                                                      ⌈                                  m                                  /                                  2                                  ⌉                                                 n                            )                                  O(k + \log_{\lceil m/2 \rceil} n)                     O(k+log⌈m/2⌉​n)，此中                                         k                                  k                     k 是范围内键值的数目。
  
• 空间复杂度：同样为                                         O                            (                            n                            )                                  O(n)                     O(n)，主要用于存储树中的节点。
  

应用场景
B + 树在数据库系统中应用广泛，如 MySQL 的 InnoDB 存储引擎默认使用 B + 树作为索引布局。由于 B + 树的布局非常适合范围查询，并且由于所有数据都存储在叶子节点，使得数据库的插入、删除和查找操纵更加高效和稳固。同时，叶子节点的有序链表布局也方便进行顺序访问，提高了数据的读取效率。
分块查找

也称为索引顺序查找，它是一种介于顺序查找和二分查找之间的查找方法。以下从根本思想、实现步骤、复杂度分析、优缺点和实用场景等方面具体介绍：
根本思想
分块查找将一个线性表分成若干个块，每个块内的元素可以是无序的，但块与块之间是有序的，即后一个块中所有元素的值都大于前一个块中所有元素的值。同时，还需要创建一个索引表，索引表中记载了每个块的最大关键字以及该块在原线性表中的起始位置，索引表是按关键字有序排列的。
实现步骤
分块查找主要分为两步：

• 确定待查元素所在的块：使用二分查找或顺序查找在索引表中查找，根据索引表中记载的块的最大关键字，确定待查元素可能存在于哪个块中。
  
• 在块内查找元素：在确定的块中使用顺序查找的方法查找待查元素。
  

示例及代码实现
假设我们有一个线性表 [22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48]，将其分成 3 个块，每个块有 4 个元素。
索引表为 [(22, 0), (44, 4), (48, 8)]，此中每个元组的第一个元素是块的最大关键字，第二个元素是块在原线性表中的起始位置。
以下是 Python 代码实现：

1. def block_search(arr, index_table, target):
2.     # 第一步：在索引表中确定所在块
3.     block_index = -1
4.     for i in range(len(index_table)):
5.         if target <= index_table[i][0]:
6.             block_index = i
7.             break
8.     if block_index == -1:
9.         return -1
11.     # 第二步：在块内进行顺序查找
12.     start = index_table[block_index][1]
13.     if block_index == len(index_table) - 1:
14.         end = len(arr)
15.     else:
16.         end = index_table[block_index + 1][1]
17.     for i in range(start, end):
18.         if arr[i] == target:
19.             return i
20.     return -1
22. # 线性表
23. arr = [22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48]
24. # 索引表
25. index_table = [(22, 0), (44, 4), (48, 8)]
26. target = 24
27. result = block_search(arr, index_table, target)
28. if result != -1:
29.     print(f"元素 {target} 在数组中的索引是 {result}")
30. else:
31.     print(f"未找到元素 {target}")

复制代码

复杂度分析

• 时间复杂度：设线性表长度为                                         n                                  n                     n，分成                                         b                                  b                     b 个块，每个块有                                         s                                  s                     s 个元素（                                        n                            =                            b                            ×                            s                                  n = b \times s                     n=b×s）。在索引表中查找块的时间复杂度，如果使用顺序查找为                                         O                            (                            b                            )                                  O(b)                     O(b)，使用二分查找为                                         O                            (                                                   log                                  ⁡                                          2                                      b                            )                                  O(\log_2b)                     O(log2​b)；在块内进行顺序查找的时间复杂度为                                         O                            (                            s                            )                                  O(s)                     O(s)。所以，分块查找的匀称时间复杂度为                                         O                            (                            b                            +                            s                            )                                  O(b + s)                     O(b+s) 或                                         O                            (                                                   log                                  ⁡                                          2                                      b                            +                            s                            )                                  O(\log_2b + s)                     O(log2​b+s)。当                                         s                            =                                       n                                            s = \sqrt{n}                     s=n             ​ 时，时间复杂度达到最优，为                                         O                            (                                       n                                      )                                  O(\sqrt{n})                     O(n             ​)。
  
• 空间复杂度：主要是索引表占用的额外空间，为                                         O                            (                            b                            )                                  O(b)                     O(b)，此中                                         b                                  b                     b 是块的数目。
  

优缺点

• 优点：
  
  
  
  • 对数据的要求相对较低，不需要像二分查找那样数据必须完全有序，只需要块间有序、块内可以无序，这在数据动态变化时比较方便维护。
    
  • 查找效率比顺序查找高，尤其是在数据量较大时。
    
  
  
• 缺点：需要额外的存储空间来存储索引表，增加了空间开销。
  

实用场景

• 数据量较大且分布不匀称：当数据量较大，且数据的分布不太规则时，分块查找可以通过合理分块，提高查找效率。
  
• 数据动态变化：由于分块查找只要求块间有序，在数据插入、删除时，只需要调整相应块内的数据，对整体的块间顺序影响较小，相比于完全有序的数据布局更易于维护。
  

斐波那契查找和插值查找在特定场景下有其独特的上风，但整体而言，它们不如顺序查找、二分查找等方法常用，以下为你具体分析：
斐波那契查找和插值查找

斐波那契查找

• 原理：斐波那契查找是在二分查找的基础上，使用斐波那契数列来确定分割点。它通过斐波那契数列的特性，将有序数组分成两部门进行查找，使得分割点更偏向于数据分布较麋集的一侧。
  
• 不常用的原因
  
  
  
  • 实现复杂度相对较高：需要对斐波那契数列有肯定的相识和处理，要天生斐波那契数列并根据其规律进行查找区间的划分，相较于二分查找，实现起来更复杂，代码编写和理解资源更高。
    
  • 实用场景受限：它主要实用于对数据存储在磁盘等外部存储装备上的查找场景，由于它在某些环境下可以减少磁盘 I/O 次数。但在现代盘算机系统中，内存访问速率有了极大提升，且磁盘存储装备的性能也不断改进，这种减少磁盘 I/O 的上风不再那么显着。
    
  
  
• 常用场景：在一些对内存使用和数据分布有特殊要求的嵌入式系统或特定算法中可能会使用斐波那契查找。例如，在某些资源受限的嵌入式装备中，当需要对有序数据进行查找时，斐波那契查找可以在肯定程度上平衡查找效率和资源消耗。
  

插值查找

• 原理：插值查找是对二分查找的一种改进，它根据待查找关键字在数据会集的大抵位置，动态土地算分割点。通过估计目标值在数组中的位置，插值查找可以更快地缩小查找范围，尤其实用于数据匀称分布的有序数组。
  
• 不常用的原因
  
  
  
  • 对数据分布要求高：插值查找的效率依靠于数据的匀称分布。如果数据分布不匀称，插值查找的性能可能会大幅下降，乃至不如二分查找。在现实应用中，很多数据集的数据分布并不匀称，这限定了插值查找的广泛使用。
    
  • 边界环境处理复杂：当数据分布极端不匀称时，插值查找盘算出的分割点可能会超出合理范围，需要进行额外的边界检查和处理，增加了算法的复杂度。
    
  
  
• 常用场景：在数据匀称分布且数据量较大的场景下，插值查找能发挥出显着的上风。例如，在一些科学盘算、地理信息系统等领域，数据可能具有较好的匀称性，此时使用插值查找可以显着提高查找效率。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。