????????當(dāng)你需要從大量數(shù)據(jù)中查找某個(gè)元素時(shí)，查找算法就變得非常重要。
??????? 無論你是初學(xué)者還是進(jìn)階者，本文將為你提供簡單易懂、實(shí)用可行的知識(shí)點(diǎn)，幫助你更好地掌握查找在數(shù)據(jù)結(jié)構(gòu)和算法中的重要性，進(jìn)而提升算法解題的能力。接下來讓我們開啟數(shù)據(jù)結(jié)構(gòu)與算法的奇妙之旅吧。
目錄
查找的基本操作
二叉排序樹
平衡二叉樹
紅黑樹的基本操作
B樹
哈希(散列)表基本操作
查找的基本操作
查找：在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素的過程稱為查找。
查找表：用于查找的數(shù)據(jù)集合稱為查找表，它由同一類型的數(shù)據(jù)元素（或記錄）組成。
關(guān)鍵字：數(shù)據(jù)元素中唯一標(biāo)識(shí)該元素的某個(gè)數(shù)據(jù)項(xiàng)的值，使用基于關(guān)鍵字的查找，查找結(jié)果應(yīng)該是唯一的。
查找長度：在查找運(yùn)算中，需要對比關(guān)鍵字的次數(shù)稱為查找長度。
平均查找長度(ASL)：所有查找過程中進(jìn)行關(guān)鍵字的比較次數(shù)的平均值。
ASL的數(shù)量級(jí)反應(yīng)了查找算法時(shí)間復(fù)雜度：
順序查找又稱 “線性查找”，通常用于線性表。其算法思想是：從頭到尾挨個(gè)查找(反過來也可以)。
下面是用 C 語言實(shí)現(xiàn)順序查找算法的基本代碼示例：
#include <stdio.h>
int sequentialSearch(int array[], int n, int target) {
for (int i = 0; i < n; i++) {
if (array[i] == target) {
return i; // 找到匹配的元素，返回索引
}
}
return -1; // 未找到匹配的元素，返回-1
}
int main() {
int array[] = {9, 5, 7, 3, 2, 8};
int n = sizeof(array) / sizeof(array[0]);
int target = 7;
int result = sequentialSearch(array, n, target);
if (result == -1) {
printf("未找到目標(biāo)元素\n");
} else {
printf("目標(biāo)元素在索引 %d 處\n", result);
}
return 0;
}回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：
折半查找又稱 “二分查找”，僅適用于有序的順序表。二分查找通過將待查找的數(shù)據(jù)與數(shù)據(jù)集合的中間元素進(jìn)行比較，從而將查找范圍縮小一半，重復(fù)這個(gè)過程直到找到匹配的元素或者確定找不到為止。
下面是折半查找的相關(guān)概念及代碼實(shí)現(xiàn)（使用C語言）：
#include <stdio.h>
int binarySearch(int array[], int low, int high, int target) {
while (low <= high) {
int mid = (low + high) / 2;
if (array[mid] == target) {
return mid; // 找到匹配的元素，返回索引
} else if (array[mid] < target) {
low = mid + 1; // 目標(biāo)在當(dāng)前中間元素的右側(cè)
} else {
high = mid - 1; // 目標(biāo)在當(dāng)前中間元素的左側(cè)
}
}
return -1; // 未找到匹配的元素，返回-1
}
int main() {
int array[] = {2, 3, 5, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int target = 7;
int result = binarySearch(array, 0, n - 1, target);
if (result == -1) {
printf("未找到目標(biāo)元素\n");
} else {
printf("目標(biāo)元素在索引 %d 處\n", result);
}
return 0;
}回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：?文章來源：http://www.zghlxwxcb.cn/news/detail-717333.html
分塊查找也稱索引順序查找，是一種將數(shù)據(jù)集合劃分為多個(gè)塊，并在每個(gè)塊中建立索引來加速查找過程的一種查找算法。它適用于數(shù)據(jù)集合較大且有序的情況。
下面是分塊查找的相關(guān)概念及代碼實(shí)現(xiàn)（使用C語言）：
#include <stdio.h>
// 定義數(shù)據(jù)塊結(jié)構(gòu)
typedef struct {
int index; // 索引值
int max; // 當(dāng)前塊的最大值
} Block;
int blockSearch(int blocks[], int n, int m, int target) {
// 首先找到所在塊的索引
int blockIndex = -1;
for (int i = 0; i < n; i++) {
if (blocks[i].max >= target) {
blockIndex = i;
break;
}
}
// 若未找到所在塊，則目標(biāo)元素不存在
if (blockIndex == -1) {
return -1;
}
// 在對應(yīng)塊內(nèi)順序查找目標(biāo)元素
int start = blockIndex * m; // 塊的起始位置
int end = (blockIndex + 1) * m - 1; // 塊的結(jié)束位置
for (int i = start; i <= end; i++) {
if (blocks[i] == target) {
return i; // 找到匹配的元素，返回索引
}
}
return -1; // 未找到匹配的元素，返回-1
}
int main() {
Block blocks[] = {{0, 3}, {4, 7}, {8, 11}, {12, 14}};
int n = sizeof(blocks) / sizeof(blocks[0]);
int m = 4;
int target = 10;
int result = blockSearch(blocks, n, m, target);
if (result == -1) {
printf("未找到目標(biāo)元素\n");
} else {
printf("目標(biāo)元素在索引 %d 處\n", result);
}
return 0;
}回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：??
二叉排序樹
二叉排序樹又稱 “二叉查找樹”，一顆二叉樹或者是空二叉樹，或者是具有如下性質(zhì)的二叉樹：
左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字
右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字
左子樹和右子樹又各是一顆二叉排序樹：
以下是二叉排序樹查找、插入、刪掉等相關(guān)的操作代碼：
#include <stdio.h>
#include <stdlib.h>
// 二叉樹節(jié)點(diǎn)定義
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 查找二叉排序樹中是否存在指定值，存在返回1，不存在返回0
int searchBST(TreeNode* root, int val) {
if (root == NULL) {
return 0;
}
if (root->val == val) {
return 1;
} else if (root->val > val) {
return searchBST(root->left, val);
} else {
return searchBST(root->right, val);
}
}
// 插入值為val的節(jié)點(diǎn)到二叉排序樹中，返回插入后的根節(jié)點(diǎn)
TreeNode* insertBST(TreeNode* root, int val) {
// 如果當(dāng)前根節(jié)點(diǎn)為空，則直接將新節(jié)點(diǎn)插入
if (root == NULL) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 如果val比當(dāng)前根節(jié)點(diǎn)小，則遞歸插入到左子樹中
if (val < root->val) {
root->left = insertBST(root->left, val);
} else { // 否則遞歸插入到右子樹中
root->right = insertBST(root->right, val);
}
return root;
}
// 刪除值為val的節(jié)點(diǎn)，返回刪除后的根節(jié)點(diǎn)
TreeNode* deleteBST(TreeNode* root, int val) {
// 如果當(dāng)前節(jié)點(diǎn)為空，則說明沒有找到需要?jiǎng)h除的節(jié)點(diǎn)，直接返回原根節(jié)點(diǎn)
if (root == NULL) {
return root;
}
// 如果需要?jiǎng)h除的節(jié)點(diǎn)比當(dāng)前根節(jié)點(diǎn)小，則遞歸刪除左子樹中的對應(yīng)節(jié)點(diǎn)
if (val < root->val) {
root->left = deleteBST(root->left, val);
return root;
} else if (val > root->val) { // 否則遞歸刪除右子樹中的對應(yīng)節(jié)點(diǎn)
root->right = deleteBST(root->right, val);
return root;
}
// 找到需要?jiǎng)h除的節(jié)點(diǎn)
if (root->left == NULL) { // 情況1：只有右子樹
TreeNode* right = root->right;
free(root);
return right;
} else if (root->right == NULL) { // 情況2：只有左子樹
TreeNode* left = root->left;
free(root);
return left;
} else { // 情況3：同時(shí)存在左右子樹，選擇用其前驅(qū)節(jié)點(diǎn)進(jìn)行替代
TreeNode* pred = root->left;
while (pred->right != NULL) {
pred = pred->right;
}
root->val = pred->val;
root->left = deleteBST(root->left, pred->val);
return root;
}
}
// 中序遍歷二叉排序樹，輸出結(jié)果為有序序列
void inorder(TreeNode* root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
int main() {
// 構(gòu)建二叉排序樹
TreeNode* root = NULL;
root = insertBST(root, 5);
insertBST(root, 3);
insertBST(root, 7);
insertBST(root, 2);
insertBST(root, 4);
insertBST(root, 6);
// 查找操作
printf("%d\n", searchBST(root, 4)); // 輸出1
printf("%d\n", searchBST(root, 8)); // 輸出0
// 刪除操作
root = deleteBST(root, 5);
inorder(root); // 輸出有序序列：2 3 4 6 7
return 0;
}回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：?
平衡二叉樹
平衡二叉樹也稱為AVL樹，是一種二叉排序樹，它的左子樹和右子樹的高度差不超過1，即每個(gè)節(jié)點(diǎn)的左右子樹的高度之差的絕對值都不超過1。
主要目的：在于保證二叉搜索樹的查找效率。在普通的二叉搜索樹中，如果出現(xiàn)極端情況（如數(shù)據(jù)有序插入），樹高會(huì)退化為O(n)，此時(shí)二叉搜索樹的效率就與鏈表一樣了。而平衡二叉樹的高度始終保持在O(log n)級(jí)別，因此在大量動(dòng)態(tài)插入和刪除的數(shù)據(jù)操作時(shí)，平衡二叉樹有著明顯的優(yōu)勢。
結(jié)點(diǎn)的平衡因子 = 左子樹高 - 右子樹高。（結(jié)點(diǎn)的平衡因子的值只可能是 -1、0 或 1）
注意：只要有任一結(jié)點(diǎn)的平衡因子絕對值大于1，就不是平衡二叉樹。
平衡二叉樹的插入：每次調(diào)整的對象都是 “最小不平衡子樹” ， 在插入操作中只要將最小不平衡子樹調(diào)整平衡，則其他祖先結(jié)點(diǎn)都會(huì)恢復(fù)平衡。
調(diào)整最小不平衡子樹(LL)：
調(diào)整最小不平衡子樹(RR)：
上面的兩個(gè)代碼思路大致如下：
調(diào)整最小不平衡子樹(LR)： ?
調(diào)整最小不平衡子樹(RL)： ??
總結(jié)： ?
練習(xí)：
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：
平衡二叉樹的刪除： 平衡二叉樹的刪除和插入操作有異曲同工之妙，其主要特點(diǎn)如下：
平衡二叉樹的刪除操作具體步驟：
1）刪除結(jié)點(diǎn)（方法同 “二叉排序樹”）
2）一路向北(上 )找到最小不平衡子樹，找不到就完結(jié)撒花
3）找最小不平衡子樹下，“個(gè)頭”最高的兒子、孫子
4）根據(jù)孫子的位置，調(diào)整平衡（LL/RR/LR/RL）
5）如果不平衡向上傳導(dǎo)，繼續(xù)2操作
具體的操作如下：
對最小不平衡子樹的旋轉(zhuǎn)可能導(dǎo)致樹變矮，從而導(dǎo)致上層祖先不平衡（不平衡向上傳遞）：
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：?
紅黑樹的基本操作
紅黑樹（Red-Black Tree）是一種自平衡二叉查找樹，它在每個(gè)節(jié)點(diǎn)上增加了一個(gè)存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是紅色或黑色。這個(gè)額外的顏色信息使得紅黑樹相較于普通的二叉查找樹更加平衡，從而能夠確保最壞情況下基本動(dòng)態(tài)集合操作的時(shí)間復(fù)雜度為O(log n)。
平衡二叉樹和紅黑樹的特點(diǎn)及其適用場景：
紅黑樹具有以下五個(gè)性質(zhì)：?
1）每個(gè)節(jié)點(diǎn)不是紅色就是黑色。
2）根節(jié)點(diǎn)是黑色的。
3）每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）。
4）如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)子節(jié)點(diǎn)都是黑色的。
5）對每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉子節(jié)點(diǎn)簡單路徑上，均包含相同數(shù)目的黑色節(jié)點(diǎn)。
將所有特性總結(jié)為的幾句話：左根右、根葉黑、不紅紅、黑路同。
注意：1）從根結(jié)點(diǎn)到葉節(jié)點(diǎn)的最長路徑不大于最短路徑的2倍
?????????? 2）從n個(gè)內(nèi)部節(jié)點(diǎn)的紅黑樹高度?
?????????? 3）紅黑樹查找操作時(shí)間復(fù)雜度 =
下面是一個(gè)簡單的紅黑樹的實(shí)例：
結(jié)點(diǎn)的黑高bh：從某結(jié)點(diǎn)出發(fā)(不含該結(jié)點(diǎn))到達(dá)任一空葉結(jié)點(diǎn)的路徑上黑結(jié)點(diǎn)總數(shù)。
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：?
紅黑樹的刪除操作：
B樹
B樹：又稱多路平衡查找樹，B樹中所有結(jié)點(diǎn)的孩子個(gè)數(shù)的最大值稱為B樹的階，通常用m表示。一顆m階B樹或?yàn)榭諛洌驗(yàn)闈M足如下特性的m叉樹：
1）樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹，即至多含有m-1個(gè)關(guān)鍵字。
2）若根結(jié)點(diǎn)不是終端結(jié)點(diǎn)，則至少有兩棵子樹。
3）除根結(jié)點(diǎn)外的所有非葉結(jié)點(diǎn)至少有[m/2]棵子樹，即至少含有[m/2]-1個(gè)關(guān)鍵字。
4）所有的葉結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（可以視為外部結(jié)點(diǎn)或類似于折半查找找判定樹的查找失敗結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。
B樹的高度：一般求解含n個(gè)關(guān)鍵字的m階B樹，最小高度和最大高度是多少？(不包含葉子結(jié)點(diǎn))
B樹的插入：
B樹的刪除： 若被刪除關(guān)鍵字在非終端結(jié)點(diǎn)，則用直接前驅(qū)或直接后繼來替代被刪除的關(guān)鍵字。
直接前驅(qū)：當(dāng)前關(guān)鍵字左側(cè)指針?biāo)缸訕湎碌?“最右下” 的元素。
直接后繼：當(dāng)前關(guān)鍵字右側(cè)指針?biāo)缸訕渲械?“最坐下” 的元素。
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：?
B+樹的相關(guān)概念：
B+樹是一種變種的B樹，也是一種自平衡的搜索樹。一棵m階的B+樹滿足下列條件：
1）每個(gè)分支結(jié)點(diǎn)最多有m棵子樹（孩子結(jié)點(diǎn)）。
2）非葉根結(jié)點(diǎn)至少有兩棵子樹，其他每個(gè)分支結(jié)點(diǎn)至少有[m/2] 棵子樹。
3）結(jié)點(diǎn)的子樹個(gè)數(shù)與關(guān)鍵字個(gè)數(shù)相等
4）所有葉結(jié)點(diǎn)包含全部關(guān)鍵字及指向相應(yīng)記錄的指針，葉節(jié)點(diǎn)中將關(guān)鍵字按大小順序排列，并且相鄰葉結(jié)點(diǎn)按大小順序相互鏈接起來。
5）所有分支結(jié)點(diǎn)中僅包含它的各個(gè)子節(jié)點(diǎn)中關(guān)鍵字的最大值及指向其子節(jié)點(diǎn)的指針。
B+樹的查找：無論查找成功與否，最終一定都要走到最下面一層結(jié)點(diǎn)。
哈希(散列)表基本操作
哈希表又稱散列表，是一種數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是：數(shù)據(jù)元素的關(guān)鍵字與其存儲(chǔ)地址直接相關(guān)。
舉出以下一個(gè)例子進(jìn)行簡單的說明：
用拉鏈法(又稱鏈接法、鏈地址法)處理“沖突”：把所有“同義詞”存儲(chǔ)在一個(gè)鏈表中。
若不同的關(guān)鍵字通過散列函數(shù)映射到同一個(gè)值，則稱它們?yōu)?“同義詞”；
通過散列函數(shù)確定的位置已經(jīng)存放了其他元素，則稱這種情況為 “沖突”。
散列查找： 我們可以通過散列函數(shù)計(jì)算目標(biāo)元素存儲(chǔ)地址，然后遍歷該地址來找到我們的目標(biāo)
如果查找失敗的情況下，比如如下的這倆種情況：
平均查找長度：如果想求解平均查找長度的話可以采用如下方式進(jìn)行：
裝填因子：裝填因子越大表明沖突越大，查找效率越低。
常見散列函數(shù)的設(shè)計(jì)方法：(設(shè)計(jì)目標(biāo)：讓不同關(guān)鍵字的沖突盡可能的減少)
散列表處理沖突的方法：?
開放定址法有以下三種方式進(jìn)行：
線性探測法：如果當(dāng)前的位置沖突，往后面找有空位的地方然后進(jìn)入即可。
如果想進(jìn)行查找的話也可以采用如下的方式：(分別是成功和失敗的情況)
查找效率分析的話如下：
平方探測法：根據(jù)d給出的公式依次帶入找到對應(yīng)的值
偽序列隨機(jī)法：根據(jù)提供的d值進(jìn)行存放：
總結(jié)：
再散列法：
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：?
文章來源地址http://www.zghlxwxcb.cn/news/detail-717333.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--》掌握數(shù)據(jù)結(jié)構(gòu)中的查找算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
