06排序 + 查找（D2_查找（D1_基础学习））
目录
温故而知新
--------------------------------
讲解一：基础理论
一、什么是查找
二、为什么需要查找
--------------------------------
讲解二：代码学习
一、顺序查找
1. 算法原理
2. 算法步骤
3. Java代码实现
4. 适用场景
5. 知识小结
二、二分查找
1. 算法原理
2. 算法步骤
3. Java代码实现
4. 适用场景
5. 知识小结
三、插值查找
1. 算法原理
2. 算法步骤
3. Java代码实现
4. 适用场景
5. 知识小结
四、斐波那契查找
1. 介绍斐波那契数列
2. 算法步骤
3. Java代码实现
4. 适用场景
5. 知识小结
五、哈希查找
1. 算法原理
2. 算法步骤
3. Java代码实现
4. 适用场景
5. 知识小结
六、二叉树查找
1. 算法原理
2. 算法步骤
3. Java代码实现
4. 适用场景
5. 知识小结
七、2-3树查找
1. 算法原理
2. 算法步骤
3. Java代码实现
4. 适用场景
5. 知识小结
八、红黑树查找
1. 算法原理
2. 算法步骤
3. Java代码实现
4. 适用场景
5. 知识小结
九、B树/B+树查找
1. 算法原理
2. 算法步骤
3. Java代码实现
B树
B+树
4. 适用场景
5. 知识小结
十、知识小结
1. 数组
2. 树
3. 散列表
4. 另话
5. 总的来说
温故而知新
在Java编程中，查找（搜索）是一项常见任务。不同的查找算法在不同的数据结构和数据量下表现
出不同的性能特点。
本文将详细分析Java中常见的查找算法，包括顺序查找、二分查找、插值查找、斐波那
契查找、哈希查找、二叉树查找、2-3树查找、红黑树查找、B树/B+树查找等，并探讨它们的适用
场景和性能比较。
--------------------------------
讲解一：基础理论
一、什么是查找
查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，
比如，我们常见的数组，链表，符号表，树，图等等
二、为什么需要查找
查找算法的目的就是要尽可能快的找到满足给定条件的元素，设想有一种方法，能让你直接拿到该
元素，那么该方法的时间复杂度，就是O(1). 当然，这是最理想的情况，现实中我们要根据不同的
数据结构，使用不同的方法，来不断的接近理想值。
那么，所谓的查找算法，为什么有的快，有的慢呢？你可以这样去理解。其实所有的查找算法都在
做一件事，那就是排除
每一次查找操作，其实都是在做排除，如果说有一种方法能以O(1)的复杂度，找到元素，那么其实
说明，它可以一下子排除候选集中的所有不相关元素，当然，这种算法，还是最理想化的。
不同查找算法的优劣其实也就是看它能不能一次排除更多的元素，比如暴力穷举法，这种方式就是
一次只能排除一个元素，显然是最慢的，如果一次能排除一半的元素，那么这就是二分，如果每一
次都能排除一大半的元素呢？
所以学习查找算法时，要考虑这个算法，一次能排除多少元素，那么排除的越多，就是越好的。
因为讲查找都是基于某一数据结构，所以本篇文章介绍各个数据结构下的查找算法，讲解每个算法
时，关注的是它排除了多少元素。
(其实也就是时间复杂度了）
--------------------------------
讲解二：代码学习
一、顺序查找
顺序查找（Sequential Search）是一种基础的查找算法，也被称为线性查找。它是一种逐个遍历
数据集，逐个比较目标值和数据集中元素的查找方法。虽然它在大数据集下性能较差，但在小规模
数据集中，顺序查找仍然是一种简单且直观的解决方案。
1. 算法原理
顺序查找算法的原理非常简单：从数据集的第一个元素开始，逐个与目标值进行比较，直到找到相
等的元素或遍历完整个数据集。如果找到相等的元素，返回该元素的位置；如果遍历完整个数据集
都没有找到相等的元素，返回一个特殊的标识（如-1），表示目标值不存在于数据集中。
2. 算法步骤
顺序查找的实现步骤非常直观：
步骤一：遍历数组： 从数组的第一个元素开始，逐个与目标值比较。
步骤二：比较元素： 将当前遍历到的元素与目标值进行比较。
步骤三：找到目标值： 如果找到相等的元素，返回该元素的索引（位置）。
步骤四：遍历完整个数组： 如果遍历完整个数组都没有找到相等的元素，返回-1。
3. Java代码实现
顺序查找（Sequential Search）是一种基本的搜索算法，它按顺序逐个检查数组中的元素，直到
找到目标元素或搜索完整个数组。
以下是Java代码实现顺序查找的例子：
public class SequentialSearch {
public static int sequentialSearch(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
return i; // 如果找到目标元素，返回它的索引
}
}
return -1; // 如果未找到目标元素，返回-1表示未找到
}
public static void main(String[] args) {
int[] array = {2, 5, 1, 9, 7, 3, 6, 8, 4};
int target = 7;
int result = sequentialSearch(array, target);
if (result != -1) {
System.out.println("目标元素 " + target + " 在数组中的索引位置为: " + result);
} else {
System.out.println("目标元素 " + target + " 未在数组中找到。");
}
}
}在这个例子中，sequentialSearch 方法接收一个整数数组 array 和一个目标值 target 作为参数。
它使用for循环遍历数组，如果找到与目标值相等的元素，则返回该元素的索引。如果循环结束仍
未找到目标元素，则返回 -1 表示未找到。
在 main 方法中，我们创建了一个整数数组 array，并调用 sequentialSearch 方法来查找目标元
素 7。根据查找的结果，程序将输出目标元素在数组中的索引位置或者提示未找到目标元素。
4. 适用场景
顺序查找适用于以下场景：
- 小规模数据集：当数据集规模较小且不需要频繁查找时，顺序查找是一种简单有效的选择。
- 数据集无序：顺序查找不依赖数据的有序性，可以在无序的数据集中进行查找操作。
5. 知识小结
顺序查找虽然不是最高效的查找算法，但它的简单性和直观性使得它在某些场景下非常有用。
在处理小规模、无序数据集的情况下，顺序查找是一个可靠的选择。
二、二分查找
二分查找算法是一种高效的搜索算法，也称为折半查找。
它适用于有序数组，通过每次将待查找范围缩小一半，快速定位目标元素的位置。
1. 算法原理
二分查找的基本思想是：将待查找区间的中间元素与目标元素进行比较，如果相等则查找成功，返回元
素下标；
如果中间元素大于目标元素，则在左半部分继续查找；如果中间元素小于目标元素，则在右半部分继续
查找。
不断缩小查找范围，直到找到目标元素或者区间为空。
2. 算法步骤
步骤一：确定查找范围
- 初始化左指针left为数组第一个元素的下标，右指针right为数组最后一个元素的下标。
步骤二：查找中间元素
- 计算中间元素的下标mid：mid = (left + right) / 2。
步骤三：比较中间元素
- 将中间元素与目标元素进行比较：
- 如果中间元素等于目标元素，则查找成功，返回mid。
- 如果中间元素大于目标元素，则将right指针移到mid - 1。
- 如果中间元素小于目标元素，则将left指针移到mid + 1。
步骤四：重复查找
- 重复步骤二和步骤三，直到left大于right，表示查找失败。
3. Java代码实现
当你需要在有序数组中查找特定元素时，二分查找是一种高效的算法。
以下是Java中的二分查找算法的实现：
public class BinarySearch {
// 二分查找函数
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 如果找到目标元素，返回索引
if (arr[mid] == target) {
return mid;
}
// 如果目标元素在左侧，缩小右边界
if (arr[mid] > target) {
right = mid - 1;
}
// 如果目标元素在右侧，缩小左边界
else {
left = mid + 1;
}
}
// 如果数组中没有找到目标元素，返回-1表示未找到
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
int target = 7;
int result = binarySearch(arr, target);
if (result != -1) {
System.out.println("元素 " + target + " 在数组中的索引为: " + result);
} else {
System.out.println("元素 " + target + " 不在数组中。");
}
}
}在这个例子中，binarySearch 函数接收一个有序数组 arr 和一个目标值 target，并返回目标值在数
组中的索引。如果找到目标值，返回它的索引；如果未找到，返回 -1。
在 main 函数中，我们创建一个有序数组，然后调用 binarySearch 函数来查找目标元素的索引。
如果找到，就输出目标元素的索引；如果未找到，输出提示信息。
4. 适用场景
- 有序数组的查找：二分查找适用于有序数组，能够快速定位目标元素。
- 数据查询优化：在大规模有序数据集中，二分查找能够提高查找效率，常用于数据库查询等场景。
5. 知识小结
二分查找是一种高效的查找算法，其时间复杂度为O(log n)，相比线性查找具有明显的性能优势。
但需要注意的是，二分查找只适用于有序数据。在实际应用中，根据数据特点选择合适的查找算法，可以有效提
高程序的运行效率。
三、插值查找
插值查找（Interpolation Search）是一种基于数学插值的查找算法，它是二分查找的改进版本。
插值查找算法适用于均匀分布的有序数据集，通过估算目标值的位置，它能够更快速地定位到目标
元素。
1. 算法原理
插值查找算法的核心思想是根据目标元素的预估位置来缩小查找范围。
假设我们要查找的数据集是有序的，如果该数据集在数值上是均匀分布的，那么插值查找会非常高
效。
它的查找位置的计算公式如下：
其中，arr 是待查找的有序数组，left 和 right 分别表示当前查找范围的左右边界，value 是目标元素的值。
2. 算法步骤
步骤一：计算估计位置：
- 使用上述的公式计算目标元素的估计位置。
步骤二：比较估计值与目标值：
- 如果估计值等于目标值，查找成功，返回估计位置。
- 如果估计值小于目标值，在估计位置的右侧继续查找。
- 如果估计值大于目标值，在估计位置的左侧继续查找。
步骤三：
- 重复步骤一和步骤二，直到找到目标元素或查找范围缩小到只包含一个元素。
3. Java代码实现
插值查找是一种查找算法，用于在有序数组或列表中快速定位目标元素。
它是根据目标元素在数组中的大致位置进行估算，从而提高查找效率。
以下是Java代码实现插值查找算法的示例：
public class InterpolationSearch {
public static int interpolationSearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right && target >= array[left] && target <= array[right]) {
// 使用插值公式估算目标元素在数组中的位置
int pos = left + ((target - array[left]) * (right - left)) / (array[right] - array[left]);
if (array[pos] == target) {
return pos; // 找到目标元素，返回位置
}
if (array[pos] < target) {
left = pos + 1; // 目标元素在右边，更新左边界
} else {
right = pos - 1; // 目标元素在左边，更新右边界
}
}
return -1; // 没有找到目标元素
}
public static void main(String[] args) {
int[] array = {1, 3, 5, 7, 9, 11, 13, 15};
int target = 7;
int result = interpolationSearch(array, target);
if (result != -1) {
System.out.println("目标元素 " + target + " 在数组中的位置为：" + result);
} else {
System.out.println("目标元素 " + target + " 未找到");
}
}
}在这个示例中，interpolationSearch 方法接受一个有序整数数组 array 和一个目标元素 target 作为
参数，并返回目标元素在数组中的位置。在每一步迭代中，根据插值公式估算目标元素在数组中的
位置，并将搜索范围缩小到该位置的左边或右边。如果找到目标元素，返回其位置；如果未找到，
返回 -1。
请注意，插值查找适用于均匀分布的数据。在某些情况下，插值查找可能不如二分查找准确。在实
际应用中，你需要根据数据分布的特点选择合适的查找算法。
4. 适用场景
插值查找算法适用于以下场景：
- 数据集是有序的。
- 数据集在数值上是均匀分布的。
5. 知识小结
在这些条件下，插值查找算法的效率较高。然而，如果数据分布不均匀，插值查找可能不如二分查
找那么高效。
插值查找算法的时间复杂度为O(log(log(n)))，它相较于普通二分查找，在均匀分布的数据集中的查
找速度更快。
四、斐波那契查找
斐波那契查找算法是一种基于分割思想的查找算法，它通过将数组分割成按照斐波那契数列定义的
特殊比例，来确定查找范围。与二分查找类似，斐波那契查找也是一种高效的有序数组查找算法，
但其优势
在于在特定情况下比二分查找的性能更好。
1. 介绍斐波那契数列
斐波那契数列是一个经典的数学问题，定义如下：
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)斐波那契数列的前几个数是：0, 1, 1, 2, 3, 5, 8, 13, 21, …
2. 算法步骤
斐波那契查找的基本思想是，将数组按照斐波那契数列的比例分割成两部分，
然后根据查找值与分割点的比较，确定查找范围，从而提高查找效率。
算法步骤如下：
步骤一：
- 计算斐波那契数列，直到第一个大于等于待查找数组长度的数。
步骤二：
- 将待查找数组长度扩展至斐波那契数列的值，并用原数组最后一个元素填充。
步骤三：
- 初始化左右指针，以及斐波那契数列的分割点。
步骤四：
- 在数组中进行查找，比较查找值与分割点的大小，缩小查找范围。
步骤五：
- 若找到目标元素，返回其索引；若查找范围缩小至一个元素且不等于目标元素，说明查找失败。
3. Java代码实现
以下是斐波那契查找算法的Java实现示例：
public class FibonacciSearch {
public static int fibonacciSearch(int[] arr, int target) {
int[] fibonacci = generateFibonacci(arr.length);
int k = 0;
while (fibonacci[k] - 1 < arr.length) {
k++;
}
int[] temp = Arrays.copyOf(arr, fibonacci[k] - 1);
for (int i = arr.length; i < temp.length; i++) {
temp[i] = arr[arr.length - 1];
}
int left = 0;
int right = temp.length - 1;
while (left <= right) {
int mid = left + fibonacci[k - 1] - 1;
if (target < temp[mid]) {
right = mid - 1;
k -= 2;
} else if (target > temp[mid]) {
left = mid + 1;
k -= 1;
} else {
if (mid < arr.length) {
return mid;
} else {
return arr.length - 1;
}
}
}
return -1;
}
private static int[] generateFibonacci(int n) {
int[] fibonacci = new int[n];
fibonacci[0] = 1;
fibonacci[1] = 1;
for (int i = 2; i < n; i++) {
fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
}
return fibonacci;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = 11;
int result = fibonacciSearch(arr, target);
if (result != -1) {
System.out.println("目标元素在数组中的索引为：" + result);
} else {
System.out.println("目标元素不在数组中。");
}
}
}4. 适用场景
斐波那契查找算法是一种高效的有序数组查找算法，它的时间复杂度为O(log n)，相对于普通的二分查找，
斐波那契查找的性能更好。
然而，在实际应用中，由于其需要生成斐波那契数列并进行数组扩展，可能会带来一定的额外开
销。
5. 知识小结
在选择查找算法时，我们需要综合考虑数据规模、数据分布和性能要求等因素，选择合适的算法来
提高程序的运行效率。
五、哈希查找
1. 算法原理
哈希查找（Hash Search）利用哈希函数将关键字映射到数组的特定位置，即哈希表。通过直接访
问哈希表的索引，可以快速定位目标元素。哈希函数负责将关键字映射到哈希表中的特定位置，这
个位置通常称为桶（bucket）。
2. 算法步骤
- 初始化哈希表：创建一个具有足够容量的哈希表，通常使用数组实现。
- 插入元素： 将关键字经过哈希函数计算得到索引，然后将元素插入到对应索引的桶中。
- 查找元素： 将待查找的关键字经过哈希函数计算得到索引，然后在对应索引的桶中查找目标元素。
3. Java代码实现
哈希查找算法是通过哈希函数将关键字映射到哈希表的某个位置，以加快查找速度。
以下是一个使用Java实现哈希查找算法的简单例子：
import java.util.LinkedList;
class HashTable {
private LinkedList<String>[] table;
private int size;
// 构造函数，初始化哈希表
public HashTable(int size) {
this.size = size;
table = new LinkedList[size];
for (int i = 0; i < size; i++) {
table[i] = new LinkedList<>();
}
}
// 哈希函数，将字符串转换为哈希表的索引
private int hash(String key) {
return key.hashCode() % size;
}
// 插入操作
public void insert(String key) {
int index = hash(key);
table[index].add(key);
}
// 查找操作
public boolean search(String key) {
int index = hash(key);
return table[index].contains(key);
}
// 删除操作
public void delete(String key) {
int index = hash(key);
table[index].remove(key);
}
}
public class Main {
public static void main(String[] args) {
HashTable hashTable = new HashTable(10);
// 插入数据
hashTable.insert("apple");
hashTable.insert("banana");
hashTable.insert("cherry");
// 查找数据
System.out.println("Search 'apple': " + hashTable.search("apple")); // 输出 true
System.out.println("Search 'grape': " + hashTable.search("grape")); // 输出 false
// 删除数据
hashTable.delete("apple");
System.out.println("Search 'apple' after deletion: " + hashTable.search("apple")); // 输出 false
}
}在这个例子中，我们创建了一个 HashTable 类，包含了插入、查找和删除操作。hash方法使用
Java内置的hashCode 函数将字符串映射到哈希表的索引。请注意，这只是一个简单的哈希查找算
法实现，实际应用中可能需要处理冲突、扩容等问题。
4. 适用场景
哈希查找适用于关键字唯一性要求高、数据量大但分布均匀的情况。
在散列冲突（多个关键字映射到同一个索引位置）较少的情况下，哈希查找具有很好的性能。
5. 知识小结
哈希查找算法通过哈希函数将关键字映射到数组索引，实现了快速的查找操作。然而，需要注意处
理散列冲突的情况，常见的方法包括开放地址法和链地址法。选择合适的哈希函数和处理冲突的方
法是使用哈希查找的关键。
六、二叉树查找
二叉树查找是一种常见的数据结构和算法，用于在有序数据集中高效地查找目标元素。
1. 算法原理
二叉树查找算法基于二叉树数据结构，其中每个节点最多有两个子节点：左子节点和右子节点。算
法利用二叉树的有序性质，从根节点开始比较目标元素与当前节点的值，根据比较结果决定向左子
树或右子树查找，直到找到目标元素或遍历完整个树。
2. 算法步骤
步骤1: 初始化
- 从根节点开始，将当前节点设为根节点。
步骤2: 比较
- 比较目标元素与当前节点的值。
- 如果目标元素等于当前节点的值，查找成功，返回当前节点。
- 如果目标元素小于当前节点的值，转到左子树；如果大于，转到右子树。
步骤3: 遍历
- 重复步骤2，直到找到目标元素或当前节点为空。
3. Java代码实现
在Java中实现一个二叉搜索树（Binary Search Tree，BST），需要定义一个树的节点类，并且实
现插入和查找操作。
以下是一个简单的二叉搜索树实现：
首先，定义一个树的节点类：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}然后，定义一个二叉搜索树类，包含插入和查找操作：
public class BinarySearchTree {
private TreeNode root;
public BinarySearchTree() {
this.root = null;
}
// 插入节点
public void insert(int val) {
root = insertRec(root, val);
}
private TreeNode insertRec(TreeNode root, int val) {
if (root == null) {
root = new TreeNode(val);
return root;
}
if (val < root.val) {
root.left = insertRec(root.left, val);
} else if (val > root.val) {
root.right = insertRec(root.right, val);
}
return root;
}
// 查找节点
public boolean search(int val) {
return searchRec(root, val);
}
private boolean searchRec(TreeNode root, int val) {
if (root == null) {
return false;
}
if (root.val == val) {
return true;
}
if (val < root.val) {
return searchRec(root.left, val);
}
return searchRec(root.right, val);
}
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);
System.out.println(tree.search(4)); // 输出: true
System.out.println(tree.search(6)); // 输出: false
}
}在这个例子中，BinarySearchTree 类包含了 insert 方法用于插入节点，和 search 方法用于查找节
点。你可以通过创建一个BinarySearchTree 的对象，然后调用 insert 方法插入节点，再调用
search 方法查找节点。
4. 适用场景
二叉树查找适用于静态数据集，即数据不经常插入或删除的情况。
它的平均时间复杂度为O(log n)，在有序数据集中表现出色。适用场景包括：
- 字典查找
- 数据库索引
- 文件系统查找
- 检索有序数据
5. 知识小结
二叉树查找算法是一种高效的查找方法，通过利用二叉树的有序性，可以快速查找目标元素。它适
用于静态数据集，但对于动态数据集，可能需要其他更复杂的数据结构，如红黑树或B树。了解二叉树查
找算法有助于优化程序的查找性能。在实际编程中，可以使用递归或迭代方式实现二叉树查找，根
据数据集的特点选择合适的方式。
七、2-3树查找
1. 算法原理
2-3树是一种自平衡查找树，它的每个节点可以包含2个或3个子节点，同时满足以下性质：
- 所有叶子节点在同一层级。
- 每个节点要么是2-节点（含有一个元素），要么是3-节点（含有两个元素）。
- 2-节点的两个子节点分别比父节点的元素小和大。
- 3-节点的三个子节点分别比父节点的两个元素小、中和大。
2-3树的插入和删除操作会使树保持平衡，确保树的高度最小，从而提供高效的查找、插入和删除性能。
2. 算法步骤
插入操作：
- 在2-3树中查找插入位置，如果为2-节点，直接插入；如果为3-节点，分裂成两个2-节点，向上递归。
- 如果向上递归导致父节点为3-节点，继续分裂，直到树的根节点。
删除操作：
- 在2-3树中找到要删除的节点，删除操作分情况讨论。
- 删除节点后，根据需要进行节点的合并和分裂，确保树的平衡性。
3. Java代码实现
以下是2-3树查找算法的Java代码实现：
class TreeNode {
int[] keys;
TreeNode[] children;
int numKeys;
boolean isLeaf;
public TreeNode(int key) {
this.keys = new int[3];
this.children = new TreeNode[4];
this.keys[0] = key;
this.numKeys = 1;
this.isLeaf = true;
}
}
public class TwoThreeTree {
private TreeNode root;
public TwoThreeTree() {
root = null;
}
public boolean search(int key) {
return searchKey(root, key);
}
private boolean searchKey(TreeNode node, int key) {
if (node == null) {
return false;
}
for (int i = 0; i < node.numKeys; i++) {
if (node.keys[i] == key) {
return true;
} else if (key < node.keys[i]) {
return searchKey(node.children[i], key);
}
}
return searchKey(node.children[node.numKeys], key);
}
public void insert(int key) {
if (root == null) {
root = new TreeNode(key);
} else {
TreeNode newNode = insertKey(root, key);
if (newNode != null) {
TreeNode newRoot = new TreeNode(newNode.keys[0]);
newRoot.children[0] = root;
newRoot.children[1] = newNode.children[0];
newRoot.children[2] = newNode.children[1];
root = newRoot;
root.isLeaf = false;
}
}
}
private TreeNode insertKey(TreeNode node, int key) {
if (node.isLeaf) {
if (node.numKeys < 3) {
insertIntoNode(node, key);
return null;
} else {
return splitNode(node, key);
}
} else {
int i;
for (i = 0; i < node.numKeys; i++) {
if (key < node.keys[i]) {
TreeNode child = insertKey(node.children[i], key);
if (child == null) {
return null;
} else {
insertIntoNode(node, child.keys[0]);
node.children[i + 1] = node.children[i];
node.children[i] = child.children[0];
node.children[i + 1] = child.children[1];
}
return node.numKeys < 3 ? null : splitNode(node, child.keys[1]);
}
}
TreeNode child = insertKey(node.children[i], key);
if (child == null) {
return null;
} else {
insertIntoNode(node, child.keys[0]);
node.children[i + 1] = child.children[1];
node.children[i] = child.children[0];
}
return node.numKeys < 3 ? null : splitNode(node, child.keys[1]);
}
}
private void insertIntoNode(TreeNode node, int key) {
int i = node.numKeys - 1;
while (i >= 0 && key < node.keys[i]) {
node.keys[i + 1] = node.keys[i];
i--;
}
node.keys[i + 1] = key;
node.numKeys++;
}
private TreeNode splitNode(TreeNode node, int key) {
TreeNode newNode = new TreeNode(0);
TreeNode left = node;
TreeNode right = new TreeNode(0);
int i = 0;
while (i < 2 && key > node.keys[i]) {
i++;
}
if (i == 0) {
right.keys[0] = node.keys[1];
right.keys[1] = node.keys[2];
right.numKeys = 2;
} else if (i == 1) {
right.keys[0] = node.keys[2];
right.numKeys = 1;
}
node.numKeys = i;
newNode.keys[0] = key;
newNode.children[0] = left;
newNode.children[1] = right;
newNode.numKeys = 1;
return newNode;
}
public void printTree() {
printTree(root, 0);
}
private void printTree(TreeNode node, int level) {
if (node != null) {
for (int i = 0; i < node.numKeys; i++) {
printTree(node.children[i], level + 1);
for (int j = 0; j < level; j++) {
System.out.print(" ");
}
System.out.println(node.keys[i]);
}
printTree(node.children[node.numKeys], level + 1);
}
}
public static void main(String[] args) {
TwoThreeTree tree = new TwoThreeTree();
tree.insert(10);
tree.insert(20);
tree.insert(5);
tree.insert(6);
tree.insert(12);
tree.insert(30);
tree.insert(7);
System.out.println("2-3树的结构：");
tree.printTree();
System.out.println("查找结果：");
System.out.println("查找5：" + tree.search(5));
System.out.println("查找15：" + tree.search(15));
}
}这段代码演示了一个简单的2-3树的实现，包括插入和查找操作。你可以根据需要扩展它。在这个
例子中，TreeNode类表示2-3树的节点。TwoThreeTree 类包含插入和查找方法，并提供了一个用于打
印树的辅助方法。
希望这能帮到你！
4. 适用场景
- 当需要高效的查找、插入和删除操作时，特别是在动态数据集上。
- 当数据集需要频繁地进行修改操作时，2-3树的自平衡性能保证了树的高度较小，提供了快速的操作性能。
5. 知识小结
2-3树是一种自平衡查找树，通过节点的合并和分裂，保持树的平衡性，提供了高效的查找、插入
和删除操作。在动态数据集和需要频繁修改操作的情况下，2-3树是一个优秀的选择。
八、红黑树查找
1. 算法原理
红黑树是一种自平衡的二叉查找树，它在每个节点上都增加了一个额外的属性表示节点的颜色，可
以是红色或黑色。
红黑树满足以下性质：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL节点，空节点）是黑色。
- 如果一个节点是红色，其子节点必须是黑色。
- 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点，这被称为黑高度相同。
这些性质保证了红黑树的平衡性，最长的路径不超过最短路径的两倍，保证了在增删查改等操作时
的高效性。
2. 算法步骤
插入操作： 当插入一个节点时，首先按照二叉查找树的规则找到其应该插入的位置，然后将节点
颜色设为红色。
如果违反了红黑树的性质，通过旋转和颜色变换来修复。
删除操作： 删除一个节点时，首先按照二叉查找树的规则找到替代节点。如果被删除的节点或替
代节点是红色，可以直接删除。如果被删除的节点是黑色，则可能破坏了红黑树的性质，需要通过
旋转和颜色变换来修复。
3. Java代码实现
红黑树（Red-Black Tree）是一种自平衡二叉搜索树，它在插入和删除操作时通过颜色变换和旋转
来保持树的平衡。
以下是一个使用Java实现红黑树查找算法的基本示例：
class Node {
int data;
Node parent;
Node left;
Node right;
int color;
}
public class RedBlackTree {
private Node root;
private Node TNULL;
// 初始化节点和树的边界
static {
TNULL = new Node();
TNULL.color = 0;
TNULL.left = null;
TNULL.right = null;
}
// 插入节点
private void insert(int key) {
Node node = new Node();
node.parent = null;
node.data = key;
node.left = TNULL;
node.right = TNULL;
node.color = 1; // 新插入的节点为红色
Node y = null;
Node x = this.root;
while (x != TNULL) {
y = x;
if (node.data < x.data) {
x = x.left;
} else {
x = x.right;
}
}
node.parent = y;
if (y == null) {
root = node;
} else if (node.data < y.data) {
y.left = node;
} else {
y.right = node;
}
if (node.parent == null){
node.color = 0;
return;
}
if (node.parent.parent == null) {
return;
}
fixInsert(node);
}
// 修复插入导致的红黑树不平衡
private void fixInsert(Node k){
Node u;
while (k.parent.color == 1) {
if (k.parent == k.parent.parent.right) {
u = k.parent.parent.left;
if (u.color == 1) {
u.color = 0;
k.parent.color = 0;
k.parent.parent.color = 1;
k = k.parent.parent;
} else {
if (k == k.parent.left) {
k = k.parent;
rightRotate(k);
}
k.parent.color = 0;
k.parent.parent.color = 1;
leftRotate(k.parent.parent);
}
} else {
u = k.parent.parent.right;
if (u.color == 1) {
u.color = 0;
k.parent.color = 0;
k.parent.parent.color = 1;
k = k.parent.parent;
} else {
if (k == k.parent.right) {
k = k.parent;
leftRotate(k);
}
k.parent.color = 0;
k.parent.parent.color = 1;
rightRotate(k.parent.parent);
}
}
if (k == root) {
break;
}
}
root.color = 0;
}
// 左旋
private void leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != TNULL) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
// 右旋
private void rightRotate(Node x) {
Node y = x.left;
x.left = y.right;
if (y.right != TNULL) {
y.right.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else if (x == x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
// 查找节点
private Node searchTreeHelper(Node node, int key) {
if (node == TNULL || key == node.data) {
return node;
}
if (key < node.data) {
return searchTreeHelper(node.left, key);
}
return searchTreeHelper(node.right, key);
}
// 公开的查找方法
public Node searchTree(int key) {
return searchTreeHelper(this.root, key);
}
}在这个示例中，我们实现了红黑树的基本操作，包括节点插入（insert）、修复插入导致的红黑树
不平衡（fixInsert）、左旋（leftRotate）、右旋（rightRotate）以及查找节点（searchTree）。
请注意，这只是一个简单的示例，实际的红黑树实现可能会更加复杂，具体实现可能会 据实
际需求进行修改和扩展。
4. 适用场景
- 需要频繁插入和删除操作的大型数据集：红黑树在维持平衡性的同时，插入和删除的性能相对较好。
- 需要快速查找、插入和删除的数据库索引： 数据库中的索引通常使用红黑树来维持数据的有序性和高效的增删查改操作。
5. 知识小结
红黑树是一种自平衡的二叉查找树，通过巧妙的旋转和颜色变换，保持了树的平衡性。
它在大型数据集的插入、删除和查找操作中表现出色。但需要注意的是，红黑树的实现较为复杂，
需要仔细处理各种边界情况。
九、B树/B+树查找
在Java编程中，B树和B+树是常用的自平衡查找树结构，用于高效地存储和检索大量数据。
本文将深入探讨B树和B+树的算法原理、步骤、Java代码实现、适用场景以及总结它们的重要特
点。
1. 算法原理
B树
- B树是一种多路搜索树，每个节点可以包含多个子节点。
- 每个节点有多个关键字，关键字按照升序排列。
- B树的高度是平衡的，使得查找、插入和删除操作都可以在O(log n)时间内完成。
B+树
- B+树也是一种多路搜索树，与B树不同的是，B+树的所有关键字都在叶子节点上。
- 叶子节点通过指针相互连接形成有序链表，提高范围查询的性能。
- B+树的高度也是平衡的，查找、插入和删除操作的性能稳定。
2. 算法步骤
B树
- 从根节点开始，按照关键字的大小进行比较，确定子节点的位置。
- 递归地进入子节点，直到找到目标关键字或达到叶子节点。
- 执行插入、删除或查找操作。
B+树
- 从根节点开始，按照关键字的大小进行比较，确定子节点的位置。
- 递归地进入子节点，直到找到目标关键字或达到叶子节点。
- 执行插入、删除或查找操作。
3. Java代码实现
B树
B树（B-Tree）是一种自平衡的树数据结构，通常用于数据库和文件系统中进行范围查询。
下面是一个简单的B树查找算法的Java实现。
首先，我们定义B树的节点类：
class BTreeNode {
int[] keys;
BTreeNode[] childNodes;
int numKeys;
boolean isLeaf;
public BTreeNode(int degree, boolean isLeaf) {
this.keys = new int[2 * degree - 1];
this.childNodes = new BTreeNode[2 * degree];
this.numKeys = 0;
this.isLeaf = isLeaf;
}
}然后，我们定义B树类，包含插入和查找操作：
public class BTree {
private BTreeNode root;
private int degree;
public BTree(int degree) {
this.degree = degree;
this.root = new BTreeNode(degree, true);
}
public void insert(int key) {
BTreeNode r = this.root;
if (r.numKeys == 2 * degree - 1) {
BTreeNode newNode = new BTreeNode(degree, false);
newNode.childNodes[0] = r;
splitChild(newNode, 0);
this.root = newNode;
insertNonFull(newNode, key);
} else {
insertNonFull(r, key);
}
}
private void insertNonFull(BTreeNode x, int key) {
int i = x.numKeys - 1;
if (x.isLeaf) {
while (i >= 0 && key < x.keys[i]) {
x.keys[i + 1] = x.keys[i];
i--;
}
x.keys[i + 1] = key;
x.numKeys++;
} else {
while (i >= 0 && key < x.keys[i]) {
i--;
}
i++;
if (x.childNodes[i].numKeys == 2 * degree - 1) {
splitChild(x, i);
if (key > x.keys[i]) {
i++;
}
}
insertNonFull(x.childNodes[i], key);
}
}
private void splitChild(BTreeNode x, int i) {
BTreeNode y = x.childNodes[i];
BTreeNode z = new BTreeNode(degree, y.isLeaf);
x.numKeys++;
for (int j = x.numKeys - 1; j > i; j--) {
x.keys[j] = x.keys[j - 1];
x.childNodes[j + 1] = x.childNodes[j];
}
x.keys[i] = y.keys[degree - 1];
x.childNodes[i + 1] = z;
z.numKeys = degree - 1;
for (int j = 0; j < degree - 1; j++) {
z.keys[j] = y.keys[j + degree];
}
if (!y.isLeaf) {
for (int j = 0; j < degree; j++) {
z.childNodes[j] = y.childNodes[j + degree];
}
}
y.numKeys = degree - 1;
}
public boolean search(int key) {
return search(root, key);
}
private boolean search(BTreeNode x, int key) {
int i = 0;
while (i < x.numKeys && key > x.keys[i]) {
i++;
}
if (i < x.numKeys && key == x.keys[i]) {
return true;
} else if (x.isLeaf) {
return false;
} else {
return search(x.childNodes[i], key);
}
}
public static void main(String[] args) {
BTree bTree = new BTree(3); // 创建一个度为3的B树
bTree.insert(3);
bTree.insert(8);
bTree.insert(12);
bTree.insert(15);
bTree.insert(20);
bTree.insert(25);
bTree.insert(27);
System.out.println(bTree.search(15)); // 输出 true
System.out.println(bTree.search(30)); // 输出 false
}
}这是一个基本的B树查找算法的实现。
请注意，B树的性能和效率与其度数（degree）有关，你可以根据实际需求调整度数以获得更好的
性能。
B+树
B+树是一种自平衡的树状数据结构，常用于数据库和文件系统的实现。
以下是一个简单的Java实现B+树的查找算法。
请注意，这只是一个基本的示例，实际应用中可能需要更多的功能和错误处理。
import java.util.ArrayList;
import java.util.List;
class BPlusTree {
private Node root;
// 内部节点类
private class Node {
private List<Integer> keys;
private List<Node> children;
private boolean isLeaf;
Node() {
keys = new ArrayList<>();
children = new ArrayList<>();
isLeaf = true;
}
}
// 在B+树中查找指定的值
public boolean search(int value) {
return search(root, value);
}
private boolean search(Node node, int value) {
if (node.isLeaf) {
return node.keys.contains(value);
} else {
int i = 0;
while (i < node.keys.size() && value > node.keys.get(i)) {
i++;
}
return search(node.children.get(i), value);
}
}
// 插入值到B+树中
public void insert(int value) {
if (root == null) {
root = new Node();
root.keys.add(value);
} else {
insert(root, value);
}
}
private void insert(Node node, int value) {
if (node.isLeaf) {
node.keys.add(value);
// 排序
node.keys.sort(null);
} else {
int i = 0;
while (i < node.keys.size() && value > node.keys.get(i)) {
i++;
}
insert(node.children.get(i), value);
}
}
}
public class Main {
public static void main(String[] args) {
BPlusTree tree = new BPlusTree();
tree.insert(5);
tree.insert(8);
tree.insert(3);
System.out.println(tree.search(5)); // 输出true
System.out.println(tree.search(4)); // 输出false
}
}请注意，这只是B+树查找算法的基本实现。在实际应用中，可能需要添加删除、更新等功能，并
且需要考虑更多的性能和边界情况。
此外，为了保持树的平衡，可能需要实现分裂和合并节点的操作。
在真实的场景中，推荐使用现有的B+树实现，例如Java中的TreeMap。
4. 适用场景
B树和B+树适用于需要高效地管理大量数据的场景，例如数据库管理系统、文件系统和搜索引擎索
引。
它们在以下情况下特别有用：
- 数据量大：当数据量较大时，B树和B+树的平衡性确保了高效的查找性能。
- 范围查询：B+树的叶子节点形成有序链表，适合范围查询操作。
- 高度平衡：B树和B+树的高度保持平衡，保证了操作的一致性性能。
5. 知识小结
B树和B+树是高效的查找算法，用于管理大规模数据。它们具有平衡性、高效性和适应性等优点，
适用于各种数据存储和检索需求。选择B树或B+树取决于具体应用场景和性能需求。
十、知识小结
1. 数组
1> 无序数组
方法一：顺序查找
这个就是暴力穷举了，每次只能排除一个，不提，时间复杂度是0(n)。
2> 有序数组
有序数组当然是有序了，不过，它有一个特点，就是它的每一个元素相当于把整个候选集分成了两
部分，每次可以排除一部分。这就比暴力穷举好多了。
方法一：二分查找
这个大家比较熟悉了，每次可以排除一半，时间复杂度是O(log2N)
其实二分查找是一种盲目的猜，猜的就是中间元素就是要找的元素。
那么，我们能不能猜的更准一点呢？其实中有的。
方法二：插值查找
为什么叫插值，其实我也说不清楚，管它呢。。。
现在想象一下如下这个数组
[0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]这个数组也是有序的，但有一个特点，每个元素相差一样，说明它们之间是均匀分布的，那么让你
来查找一个75，你会怎么办？
现在闭眼想象一下，元素都是均匀分布的，所以，你知道，50肯定在中间，90肯定接近末尾，20
肯定离开头比较近。那么，我们可以每次查找时，找到最接近的那个数字，而它的位置大概就在
要找的位置 = （距离开头的距离 / 总的距离）* 真实的距离
所以，我们每次比较的位置就是通过以上公式来计算的，这样，每次就不像2分查找那样，傻傻的
只排除一半了。
适用情况：均匀分布
方法三：Fibonacci 查找
其实也是一种划分数组，进行排除的方式，据说性能优于二分查找，但好像看不懂证明，所以，知
道就好，用到再说，因为你不知道什么情况下优于二分查找
2. 树
这节介绍数下的查找方法，树的排除和数组的排除类似，数组是排除一部分，树更形象一点，排除一个分支。
又另一种方式来说，就是剪枝。
1> 无序树（不限于二叉树）
这种没办法，使用深度或广度方式吧。
2> 二叉有序树
这种类似二分查找，每次排除一个分支
3> 2-3 查找树
这种树长这样。
其实就是有两种结点，2node和3node，和二叉树长的大差不差。查找方式也几乎雷同，只是构建
这颗树比较有难度。。。
4> 红黑树
红黑树就是树2-3树变成了二叉树，2-3树中的3结点变成红色链接，
同样的，这个结构的难度在于建立这个树，查找方法和二叉查找树一样。
再谈，二叉查找树，2-3树，红黑树
以上说了，二叉查找树，2-3树，红黑树，整了这么多，最好也是O(log2N)的效率，而且2-3，红
黑，似乎还要比二叉查找树复杂啊？
其实2-3树，红黑树都有一个目的，就是要尽量接近平衡二叉树，只有接近了平衡二叉树，才能有
O(log2N)的。
这里我们其实还忽略了另一个方面，就是这个结构并不仅仅用来查找，在实际项目中，还要增加，
删除结构中的元素，对于二叉查找树，
随着增加，删除的增多，慢慢的变的不平衡了，不平衡了，查找效率就下来了，而为了维持平衡，
要付出巨大的插入，删除代价，这显然是不可接受的（因为我们的实际业务不仅仅是要求查找效率
高）而2-3树，红黑树就在插入和删除时，能尽量维持平衡，这也就在插入，删除，查找之间找到
了一种平衡点。
5> B 树
B树是2-3树的更一般化，它也是一种平衡树，结点也是有序的，每个结点可以有多个值，所以，很
好理解嘛，它长这样，它的查找算法，你也大概能猜到吧
6> B+ 树
B+树和B树类似，关于B树，B+树的应用，可以参考[数据库基础概念]中关于索引的讨论一文
3. 散列表
我们知道元素是在计算机中存储的，那么每个元素，就有一个地址，找到了这个地址，想当于找到
了这个元素。
其实无论是数组也好，树也好，我们拿一个元素来检查是不是要找的值，实际上是先通过地址来得
到元素的。所以说，地址很关键。
最简单的地址就是数组的Index了。
那么说，能不能直接定位到要查找元素的地址呢？假如我们有一个函数，可以根据元素的值，来计
算出它应该出现的地址。
是不是就不能一个个去比较了呢？就像下面这个公式
address = f(x) x为要查找的元素而散列表的思想就是来自于此。以上函数就是散列表中最关键的hash函数。
散列表一般长这样
一般散列表的结构都是有一个数组+链表来组成的。理想情况下，可以根据要查找的元素，直接计
算出地址。但那是理想情况下。
散列表的关键设计就是散列函数了，这个函数要让值均匀分布才好
4. 另话
其实，以上讨论的都是在一个数据集上的查找操作。
在实际应用中，我们的数据集上还上增加和删除操作。
有的算法和数据结构对查找有好，但是对增加和删除不友好。
所以我们要根据自己的数据集的特点，看查找，增加，删除，更新这些操作在该数据集上的频率等
等，再选择是否需要使用这个数据结构。
当然还要考虑到实际计算机中不同存储体系的性能差距，如B树，B+树在数据库中的应用就体现了
这一点。
5. 总的来说
顺序查找： 适用于小规模无序数据集。
二分查找： 适用于有序数据集，时间复杂度为O(log n)。
插值查找： 适用于均匀分布的有序数据集。
斐波那契查找： 适用于大型有序数据集，但数据分布不均匀。
哈希查找： 适用于关键字唯一性要求高的情况，但可能存在哈希冲突。
二叉树查找： 适用于动态数据集，频繁插入和删除操作。
2-3树查找： 适用于需要维持平衡性的动态数据集。
红黑树查找： 适用于高效查找、插入和删除操作的大型数据集。
B树/B+树查找： 适用于大规模数据集，频繁插入和删除操作。
不同的查找算法适用于不同的场景，选择合适的查找算法可以有效提高程序的运行效率。