网站未经授权推广别人的产品,网站建设写代码,广州推广工具,如何对网站做镜像目录 温故而知新
--------------------------------
讲解一#xff1a;基础理论
一、什么是查找
二、为什么需要查找
--------------------------------
讲解二#xff1a;代码学习
一、顺序查找
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. 知识小结
六、二叉树查找
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为数组最后一个元素的下标。
步骤二查找中间元素
计算中间元素的下标midmid (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 LinkedListString[] 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)); // 输出 trueSystem.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 TreeBST需要定义一个树的节点类并且实
现插入和查找操作。
以下是一个简单的二叉搜索树实现
首先定义一个树的节点类
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)); // 输出: trueSystem.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)); // 输出 trueSystem.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 ListInteger keys;private ListNode 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)); // 输出trueSystem.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树查找 适用于大规模数据集频繁插入和删除操作。
不同的查找算法适用于不同的场景选择合适的查找算法可以有效提高程序的运行效率。
