時(shí)間、空間復(fù)雜度比較

查找算法平均時(shí)間復(fù)雜度空間復(fù)雜度查找條件

順序查找	O(n)	O(1)	無(wú)序或有序
二分查找(折半查找)	O(log2n)	O(1)	有序
插值查找	O(log2(log2n))	O(1)	有序
斐波那契查找	O(log2n)	O(1)	有序
哈希查找	O(1)	O(n)	無(wú)序或有序
二叉查找樹(shù)(二叉搜索樹(shù)查找)	O(log2n)
紅黑樹(shù)	O(log2n)
2-3樹(shù)	O(log2n - log3n)
B樹(shù)/B+樹(shù)	O(log2n)

1 順序查找

算法思路：

對(duì)于任意一個(gè)序列，從一端開(kāi)始，順序掃描，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字與給定值k相比較，若相等則表示查找成功；若掃描結(jié)束仍沒(méi)有找到關(guān)鍵字等于k的結(jié)點(diǎn)，表示查找失敗。

代碼：

#include
#include
#define keyType int
//2020.05.24
typedef struct
{
keyType key;//查找表中每個(gè)數(shù)據(jù)元素的值
}ElemType;
typedef struct
{
ElemType *elem;//存放查找表中數(shù)據(jù)元素的數(shù)組
int length;//記錄查找表中數(shù)據(jù)的總數(shù)量
}SSTable;
//創(chuàng)建查詢數(shù)據(jù)
void Create(SSTable **st,int length)
{
(*st)=(SSTable*)malloc(sizeof(SSTable));
(*st)->length=length;
(*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
printf("輸入表中的數(shù)據(jù)元素：\n");
//根據(jù)查找表中數(shù)據(jù)元素的總長(zhǎng)度，在存儲(chǔ)時(shí)，從數(shù)組下標(biāo)為 1 的空間開(kāi)始存儲(chǔ)數(shù)據(jù)
for (int i=1; i<=length; i++)
{
scanf("%d",&((*st)->elem[i].key));
}
}
//順序查找函數(shù)，其中key為要查找的元素
int Search_seq(SSTable *str,keyType key)
{
//str->elem[0].key=key;//將關(guān)鍵字作為一個(gè)數(shù)據(jù)元素存放到查找表的第一個(gè)位置，起監(jiān)視哨的作用
int len = str->length;
//從最后一個(gè)數(shù)據(jù)元素依次遍歷，一直遍歷到數(shù)組下標(biāo)為0
for(int i=1; i {
if(str->elem[i].key == key)
{
return i;
}
}
//如果 i=0，說(shuō)明查找失敗；查找成功返回要查找元素key的位置i
return 0;
}
int main()
{
SSTable *str;
int num;
printf("請(qǐng)輸入創(chuàng)建數(shù)據(jù)元素的個(gè)數(shù)：\n");
scanf("%d",&num);
Create(&str, num);
getchar();
printf("請(qǐng)輸入要查找的數(shù)據(jù)：\n");
int key;
scanf("%d",&key);
int location=Search_seq(str, key);
if (location==0) {
printf("查找失敗");
}else{
printf("要查找的%d的順序?yàn)?#xff1a;%d",key,location);
}
return 0;
}

運(yùn)行結(jié)果：

查找成功查找失敗

2 二分查找(折半查找)

算法思路：

確定查找范圍low=0，high=N-1，計(jì)算中項(xiàng)mid=(low+high)/2。

若mid==x或low>=high,則結(jié)束查找；否則，向下繼續(xù)。

若amidx，說(shuō)明待查找的元素值只可能在比中項(xiàng)元素小的范圍內(nèi)，則把mid-1的值賦給higt，并重新計(jì)算mid，轉(zhuǎn)去執(zhí)行步驟2。

說(shuō)明：

• 查找元素必須是有序的，如果是無(wú)序的則要先進(jìn)行排序操作。

• 在做查找的過(guò)程中，如果 low 指針和 high 指針的中間位置在計(jì)算時(shí)位于兩個(gè)關(guān)鍵字中間，即求得 mid 的位置不是整數(shù)，需要統(tǒng)一做取整操作。

折半查找的前提條件是需要有序表順序存儲(chǔ)，對(duì)于靜態(tài)查找表，一次排序后不再變化，折半查找能得到不錯(cuò)的效率。但對(duì)于需要頻繁執(zhí)行插入或刪除操作的數(shù)據(jù)集來(lái)說(shuō)，維護(hù)有序的排序會(huì)帶來(lái)不小的工作量，那就不建議使用。

——《大話數(shù)據(jù)結(jié)構(gòu)》

代碼：

#include
#include
#define keyType int
typedef struct
{
keyType key;//查找表中每個(gè)數(shù)據(jù)元素的值
}ElemType;
typedef struct
{
ElemType *elem;//存放查找表中數(shù)據(jù)元素的數(shù)組
int length;//記錄查找表中數(shù)據(jù)的總數(shù)量
}SSTable;
//創(chuàng)建查詢數(shù)據(jù)
void Create(SSTable **st,int length)
{
(*st)=(SSTable*)malloc(sizeof(SSTable));
(*st)->length=length;
(*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
printf("輸入表中的數(shù)據(jù)元素：\n");
//根據(jù)查找表中數(shù)據(jù)元素的總長(zhǎng)度，在存儲(chǔ)時(shí)，從數(shù)組下標(biāo)為 1 的空間開(kāi)始存儲(chǔ)數(shù)據(jù)
for (int i=1; i<=length; i++)
{
scanf("%d",&((*st)->elem[i].key));
}
}
//折半查找函數(shù) key為要查找的元素
int Search_Bin(SSTable *str,keyType key)
{
int low=1;//初始狀態(tài) low 指針指向第一個(gè)關(guān)鍵字
int high=str->length;//high 指向最后一個(gè)關(guān)鍵字
int mid;
while (low<=high)
{
mid=(low+high)/2;//int 本身為整形，所以，mid 每次為取整的整數(shù)
if(str->elem[mid].key==key)//如果 mid 指向的同要查找的相等，返回 mid 所指向的位置
{
return mid;
}
else if(str->elem[mid].key>key)//如果mid指向的關(guān)鍵字較大，則更新 high 指針的位置
{
high=mid-1;
}
//反之，則更新 low 指針的位置
else
{
low=mid+1;
}
}
return 0;
}
int main()
{
SSTable *str;
int num;
printf("請(qǐng)輸入創(chuàng)建數(shù)據(jù)元素的個(gè)數(shù)：\n");
scanf("%d",&num);
Create(&str, num);
getchar();
printf("請(qǐng)輸入要查找的數(shù)據(jù)：\n");
int key;
scanf("%d",&key);
int location=Search_Bin(str, key);
if (location==0) {
printf("沒(méi)有查找到");
}else{
printf("要查找的%d的順序?yàn)?#xff1a;%d",key,location);
}
return 0;
}

運(yùn)行結(jié)果：

查找成功沒(méi)有查找到

3 插值查找

插值查找基于二分查找算法，將查找點(diǎn)的選擇改進(jìn)為自適應(yīng)選擇，可以提高查找效率。當(dāng)然，差值查找也屬于有序查找

算法思路：

確定查找范圍low=0，high=N-1，計(jì)算中項(xiàng)mid=low+(key-a[low])/(a[high]-a[low])*(high-low)。

若mid==x或low>=high,則結(jié)束查找；否則，向下繼續(xù)。

若amidx，說(shuō)明待查找的元素值只可能在比中項(xiàng)元素小的范圍內(nèi)，則把mid-1的值賦給higt，并重新計(jì)算mid，轉(zhuǎn)去執(zhí)行步驟2。

說(shuō)明：

• 插值查找是基于折半查找進(jìn)行了優(yōu)化的查找方法。
• 當(dāng)表長(zhǎng)較大，而關(guān)鍵字分布又比較均勻的查找表來(lái)說(shuō)，插值查找算法的平均性能要比折半查找要好得多。

代碼：

#include
int array[10] = { 1, 4, 9, 16, 27, 31, 33, 35, 45, 64 };
int InsertionSearch(int data)
{
int low = 0;
int high = 10 - 1;
int mid = -1;
int comparisons = 1;
int index = -1;
while(low <= high)
{
printf("比較 %d 次\n" , comparisons );
printf("low : %d, list[%d] = %d\n", low, low, array[low]);
printf("high : %d, list[%d] = %d\n", high, high, array[high]);
comparisons++;
mid = low + (((double)(high - low) / (array[high] - array[low])) * (data - array[low]));
printf("mid = %d\n",mid);
// 沒(méi)有找到
if(array[mid] == data)
{
index = mid;
break;
}
else
{
if(array[mid] < data)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
}
printf("比較次數(shù): %d\n", --comparisons);
return index;
}
int main()
{
int location = InsertionSearch(27); //測(cè)試代，查27，可以找到
if(location != -1)
{
printf("查找元素順序?yàn)? %d\n" ,(location+1));
}
else
{
printf("沒(méi)有查找到");
}
return 0;
}

運(yùn)行結(jié)果：

運(yùn)行結(jié)果

4 斐波那契查找

斐波那契查找與折半查找很相似，他是根據(jù)斐波那契序列的特點(diǎn)對(duì)有序表進(jìn)行分割的。他要求開(kāi)始表中記錄的個(gè)數(shù)為某個(gè)斐波那契數(shù)小1，及n=F(k)-1；開(kāi)始將k值與第F(k-1)位置的記錄進(jìn)行比較(及mid=low+F(k-1)-1).

算法思路：

相等，mid位置的元素即為所求

大于，low=mid+1,k-=2;

小于，high=mid-1,k-=1。

說(shuō)明：

low=mid+1說(shuō)明待查找的元素在[mid+1,high]范圍內(nèi)，k-=2 說(shuō)明范圍[mid+1,high]內(nèi)的元素個(gè)數(shù)為n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1個(gè)，所以可以遞歸的應(yīng)用斐波那契查找。

代碼：

#include "stdafx.h"
#include
#include
using namespace std;
const int max_size=20;//斐波那契數(shù)組的長(zhǎng)度
/*構(gòu)造一個(gè)斐波那契數(shù)組*/
void Fibonacci(int * F)
{
F[0]=0;
F[1]=1;
for(int i=2;i F[i]=F[i-1]+F[i-2];
}
/*定義斐波那契查找法*/
int FibonacciSearch(int *a, int n, int key) //a為要查找的數(shù)組,n為要查找的數(shù)組長(zhǎng)度,key為要查找的關(guān)鍵字
{
int low=0;
int high=n-1;
int F[max_size];
Fibonacci(F);//構(gòu)造一個(gè)斐波那契數(shù)組F
int k=0;
while(n>F[k]-1)//計(jì)算n位于斐波那契數(shù)列的位置
++k;
int * temp;//將數(shù)組a擴(kuò)展到F[k]-1的長(zhǎng)度
temp=new int [F[k]-1];
memcpy(temp,a,n*sizeof(int));
for(int i=n;i temp[i]=a[n-1];
while(low<=high)
{
int mid=low+F[k-1]-1;
if(key {
high=mid-1;
k-=1;
}
else if(key>temp[mid])
{
low=mid+1;
k-=2;
}
else
{
if(mid return mid; //若相等則說(shuō)明mid即為查找到的位置
else
return n-1; //若mid>=n則說(shuō)明是擴(kuò)展的數(shù)值,返回n-1
}
}
delete [] temp;
return 0;
}
int main()
{
int a[] = {0,1,4,35,47,53,62,78,88,99};
int key=47;
int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
if(index == 0)
{
cout< }
else
{
cout< }
return 0;
}

運(yùn)行結(jié)果：

47的位置為5

5 哈希查找

哈希表：

我們使用一個(gè)下標(biāo)范圍比較大的數(shù)組來(lái)存儲(chǔ)元素。可以設(shè)計(jì)一個(gè)函數(shù)(哈希函數(shù)， 也叫做散列函數(shù))，使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值(即數(shù)組下標(biāo))相對(duì)應(yīng)，于是用這個(gè)數(shù)組單元來(lái)存儲(chǔ)這個(gè)元素；也可以簡(jiǎn)單的理解為，按照關(guān)鍵字為每一個(gè)元素"分類"，然后將這個(gè)元素存儲(chǔ)在相應(yīng)"類"所對(duì)應(yīng)的地方。但是，不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對(duì)應(yīng)的，因此極有可能出現(xiàn)對(duì)于不同的元素，卻計(jì)算出了相同的函數(shù)值，這樣就產(chǎn)生了"沖突"，換句話說(shuō)，就是把不同的元素分在了相同的"類"之中。后面我們將看到一種解決"沖突"的簡(jiǎn)便做法。

"直接定址"與"解決沖突"是哈希表的兩大特點(diǎn)。

哈希函數(shù)：

規(guī)則：通過(guò)某種轉(zhuǎn)換關(guān)系，使關(guān)鍵字適度的分散到指定大小的的順序結(jié)構(gòu)中，越分散，則以后查找的時(shí)間復(fù)雜度越小，空間復(fù)雜度越高。

算法思路：

如果所有的鍵都是整數(shù)，那么就可以使用一個(gè)簡(jiǎn)單的無(wú)序數(shù)組來(lái)實(shí)現(xiàn)：將鍵作為索引，值即為其對(duì)應(yīng)的值，這樣就可以快速訪問(wèn)任意鍵的值。這是對(duì)于簡(jiǎn)單的鍵的情況，我們將其擴(kuò)展到可以處理更加復(fù)雜的類型的鍵。

用給定的哈希函數(shù)構(gòu)造哈希表；

根據(jù)選擇的沖突處理方法(常見(jiàn)方法：拉鏈法和線性探測(cè)法)解決地址沖突；

在哈希表的基礎(chǔ)上執(zhí)行哈希查找；

代碼：

#include
#include
#define SUCCESS 1
#define UNSUCCESS 0
#define OVERFLOW -1
#define OK 1
#define ERROR -1
#define MAXNUM 9999 // 用于初始化哈希表的記錄 key
typedef int Status;
typedef int KeyType;
// 哈希表中的記錄類型
typedef struct
{
KeyType key;
}RcdType;
// 哈希表類型
typedef struct
{
RcdType *rcd;
int size;
int count;
int *tag;
}HashTable;
// 哈希表每次重建增長(zhǎng)后的大小
int hashsize[] = { 11, 31, 61, 127, 251, 503 };
int index = 0;
// 初始哈希表
Status InitHashTable(HashTable &H, int size)
{
int i;
H.rcd = (RcdType *)malloc(sizeof(RcdType)*size);
H.tag = (int *)malloc(sizeof(int)*size);
if (NULL == H.rcd || NULL == H.tag) return OVERFLOW;
KeyType maxNum = MAXNUM;
for (i = 0; i < size; i++)
{
H.tag[i] = 0;
H.rcd[i].key = maxNum;
}
H.size = size;
H.count = 0;
return OK;
}
// 哈希函數(shù)：除留余數(shù)法
int Hash(KeyType key, int m)
{
return (3 * key) % m;
}
// 處理哈希沖突：線性探測(cè)
void collision(int &p, int m)
{
p = (p + 1) % m;
}
// 在哈希表中查詢
Status SearchHash(HashTable H, KeyType key, int &p, int &c)
{
p = Hash(key, H.size);
int h = p;
c = 0;
while ((1 == H.tag[p] && H.rcd[p].key != key) || -1 == H.tag[p])
{
collision(p, H.size); c++;
}
if (1 == H.tag[p] && key == H.rcd[p].key) return SUCCESS;
else return UNSUCCESS;
}
//打印哈希表
void printHash(HashTable H)
{
int i;
printf("key : ");
for (i = 0; i < H.size; i++)
printf("%3d ", H.rcd[i].key);
printf("\n");
printf("tag : ");
for (i = 0; i < H.size; i++)
printf("%3d ", H.tag[i]);
printf("\n\n");
}
// 函數(shù)聲明：插入哈希表
Status InsertHash(HashTable &H, KeyType key);
// 重建哈希表
Status recreateHash(HashTable &H)
{
RcdType *orcd;
int *otag, osize, i;
orcd = H.rcd;
otag = H.tag;
osize = H.size;
InitHashTable(H, hashsize[index++]);
//把所有元素，按照新哈希函數(shù)放到新表中
for (i = 0; i < osize; i++)
{
if (1 == otag[i])
{
InsertHash(H, orcd[i].key);
}
}
return OK;
}
// 插入哈希表
Status InsertHash(HashTable &H, KeyType key)
{
int p, c;
if (UNSUCCESS == SearchHash(H, key, p, c))
{ //沒(méi)有相同key
if (c*1.0 / H.size < 0.5)
{ //沖突次數(shù)未達(dá)到上線
//插入代碼
H.rcd[p].key = key;
H.tag[p] = 1;
H.count++;
return SUCCESS;
}
else recreateHash(H); //重構(gòu)哈希表
}
return UNSUCCESS;
}
// 刪除哈希表
Status DeleteHash(HashTable &H, KeyType key)
{
int p, c;
if (SUCCESS == SearchHash(H, key, p, c))
{
//刪除代碼
H.tag[p] = -1;
H.count--;
return SUCCESS;
}
else return UNSUCCESS;
}
int main()
{
printf("-----哈希表-----\n");
HashTable H;
int i;
int size = 11;
KeyType array[8] = { 22, 41, 53, 46, 30, 13, 12, 67 };
KeyType key;
//初始化哈希表
printf("初始化哈希表\n");
if (SUCCESS == InitHashTable(H, hashsize[index++])) printf("初始化成功\n");
//插入哈希表
printf("插入哈希表\n");
for (i = 0; i <= 7; i++)
{
key = array[i];
InsertHash(H, key);
printHash(H);
}
//刪除哈希表
printf("刪除哈希表中key為12的元素\n");
int p, c;
if (SUCCESS == DeleteHash(H, 12))
{
printf("刪除成功，此時(shí)哈希表為：\n");
printHash(H);
}
//查詢哈希表
printf("查詢哈希表中key為67的元素\n");
if (SUCCESS == SearchHash(H, 67, p, c)) printf("查詢成功\n");
//再次插入，測(cè)試哈希表的重建
printf("再次插入，測(cè)試哈希表的重建：\n");
KeyType array1[8] = { 27, 47, 57, 47, 37, 17, 93, 67 };
for (i = 0; i <= 7; i++)
{
key = array1[i];
InsertHash(H, key);
printHash(H);
}
getchar();
return 0;
}

6 二叉樹(shù)查找

二叉查找樹(shù)是先對(duì)待查找的數(shù)據(jù)進(jìn)行生成樹(shù)，確保樹(shù)的左分支的值小于右分支的值，然后在就行和每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)比較大小，查找最適合的范圍。這個(gè)算法的查找效率很高，但是如果使用這種查找方法要首先創(chuàng)建樹(shù)。

算法思路：

若b是空樹(shù)，則搜索失敗：

若x等于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則查找成功：

若x小于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則搜索左子樹(shù)：

查找右子樹(shù)。

代碼：

遞歸和非遞歸

//非遞歸查找算法
BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p)
{
//查找函數(shù)返回指向關(guān)鍵字值為key的結(jié)點(diǎn)指針，不存在則返回NULL
p=NULL;
while(T!=NULL&&key!=T->data)
{
p=T; //指向被查找結(jié)點(diǎn)的雙親
if(keydata)
T=T->lchild; //查找左子樹(shù)
else
T=T->rchild; //查找右子樹(shù)
}
return T;
}
//遞歸算法
Status Search_BST(BiTree T, int key, BiTree f, BiTree *p)
{
//查找BST中是否存在key，f指向T雙親，其初始值為NULL
//若查找成功，指針p指向數(shù)據(jù)元素結(jié)點(diǎn)，返回true；
//若失敗，p指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)并返回false
if(!T)
{
*p=f;
return false;
}
else if(key==T->data)
{ //查找成功
*p=T;
return true;
}
else if(keydata)
return Search_BST(T->lchild,key,T,p); //遞歸查找左子樹(shù)
else
return Search_BST(T->rchild,key,T,p); //遞歸查找右子樹(shù)
}

7 2-3樹(shù)

2-3樹(shù)運(yùn)行每個(gè)節(jié)點(diǎn)保存1個(gè)或者兩個(gè)的值。對(duì)于普通的2節(jié)點(diǎn)(2-node)，他保存1個(gè)key和左右兩個(gè)自己點(diǎn)。對(duì)應(yīng)3節(jié)點(diǎn)(3-node)，保存兩個(gè)Key，2-3查找樹(shù)的定義如下：

要么為空，要么：

對(duì)于2節(jié)點(diǎn)，該節(jié)點(diǎn)保存一個(gè)key及對(duì)應(yīng)value，以及兩個(gè)指向左右節(jié)點(diǎn)的節(jié)點(diǎn)，左節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，所有的值都比key要小，右節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，所有的值比key要大。

對(duì)于3節(jié)點(diǎn)，該節(jié)點(diǎn)保存兩個(gè)key及對(duì)應(yīng)value，以及三個(gè)指向左中右的節(jié)點(diǎn)。左節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，所有的值均比兩個(gè)key中的最小的key還要小；中間節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，中間節(jié)點(diǎn)的key值在兩個(gè)跟節(jié)點(diǎn)key值之間；右節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，節(jié)點(diǎn)的所有key值比兩個(gè)key中的最大的key還要大。

算法思路:

要判斷一個(gè)鍵是否在樹(shù)中，我們先將它和根結(jié)點(diǎn)中的鍵比較。如果它和其中的任何一個(gè)相等，查找命中。否則我們就根據(jù)比較的結(jié)果找到指向相應(yīng)區(qū)間的鏈接，并在其指向的子樹(shù)中遞歸地繼續(xù)查找。如果這是個(gè)空鏈接，查找未命中。

2-3 樹(shù)中查找鍵為H的節(jié)點(diǎn)2-3 樹(shù)中查找鍵為B的節(jié)點(diǎn)

代碼：

two_three *search23(two_three *t, element x)
{
while(t)
{
if (x < t->data_l)
{
t = t->left_child;
}
else if (x > t->data_l && x < t->data_r)
{
t = t->middle_child;
}
else if (x > t->data_r)
{
t = t->right_child;
}
else
{
return t;
}
}
return NULL;
}

8 紅黑樹(shù)

2-3查找樹(shù)能保證在插入元素之后能保持樹(shù)的平衡狀態(tài)，最壞情況下即所有的子節(jié)點(diǎn)都是2-node，樹(shù)的高度為lgn，從而保證了最壞情況下的時(shí)間復(fù)雜度。但是2-3樹(shù)實(shí)現(xiàn)起來(lái)比較復(fù)雜，于是就有了一種簡(jiǎn)單實(shí)現(xiàn)2-3樹(shù)的數(shù)據(jù)結(jié)構(gòu)，即紅黑樹(shù)(Red-Black Tree)。

理解紅黑樹(shù)一句話就夠了：紅黑樹(shù)就是用紅鏈接表示3-結(jié)點(diǎn)的2-3樹(shù)。

現(xiàn)在我們對(duì)2-3樹(shù)進(jìn)行改造，改造成一個(gè)二叉樹(shù)。怎么改造呢？對(duì)于2節(jié)點(diǎn)，保持不變；對(duì)于3節(jié)點(diǎn)，我們首先將3節(jié)點(diǎn)中左側(cè)的元素標(biāo)記為紅色，然后我們將其改造成圖3的形式；

再將3節(jié)點(diǎn)的位于中間的子節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為父節(jié)點(diǎn)中那個(gè)紅色的節(jié)點(diǎn)，如圖4的所示；最后我們將圖4的形式改為二叉樹(shù)的樣子，如圖5所示。圖5是不是很熟悉，沒(méi)錯(cuò)，這就是我們常常提到的大名鼎鼎的紅黑樹(shù)了。如下圖所示。

2-3樹(shù)轉(zhuǎn)紅黑樹(shù)

為什么使用紅黑樹(shù)：

• 紅黑樹(shù)是一種平衡樹(shù)，他復(fù)雜的定義和規(guī)則都是為了保證樹(shù)的平衡性。如果樹(shù)不保證他的平衡性就是下圖：很顯然這就變成一個(gè)鏈表了。
• 保證平衡性的最大的目的就是降低樹(shù)的高度，因?yàn)闃?shù)的查找性能取決于樹(shù)的高度。所以樹(shù)的高度越低搜索的效率越高！
• 這也是為什么存在二叉樹(shù)、搜索二叉樹(shù)等，各類樹(shù)的目的。

紅黑樹(shù)性質(zhì)：

• 每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。
• 根節(jié)點(diǎn)是黑色。
• 每個(gè)葉子節(jié)點(diǎn)(NIL)是黑色。
• 每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色。
• 任意一結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)。

算法思路：

紅黑樹(shù)的思想就是對(duì)2-3查找樹(shù)進(jìn)行編碼，尤其是對(duì)2-3查找樹(shù)中的3-nodes節(jié)點(diǎn)添加額外的信息。紅黑樹(shù)中將節(jié)點(diǎn)之間的鏈接分為兩種不同類型，紅色鏈接，他用來(lái)鏈接兩個(gè)2-nodes節(jié)點(diǎn)來(lái)表示一個(gè)3-nodes節(jié)點(diǎn)。黑色鏈接用來(lái)鏈接普通的2-3節(jié)點(diǎn)。特別的，使用紅色鏈接的兩個(gè)2-nodes來(lái)表示一個(gè)3-nodes節(jié)點(diǎn)，并且向左傾斜，即一個(gè)2-node是另一個(gè)2-node的左子節(jié)點(diǎn)。這種做法的好處是查找的時(shí)候不用做任何修改，和普通的二叉查找樹(shù)相同。

代碼：

#define BLACK 1
#define RED 0
#include
using namespace std;
class bst
{
private:
struct Node
{
int value;
bool color;
Node *leftTree, *rightTree, *parent;
Node() : value(0), color(RED), leftTree(NULL), rightTree(NULL), parent(NULL) { }
Node* grandparent()
{
if (parent == NULL)
{
return NULL;
}
return parent->parent;
}
Node* uncle()
{
if (grandparent() == NULL)
{
return NULL;
}
if (parent == grandparent()->rightTree)
return grandparent()->leftTree;
else
return grandparent()->rightTree;
}
Node* sibling()
{
if (parent->leftTree == this)
return parent->rightTree;
else
return parent->leftTree;
}
};
void rotate_right(Node *p)
{
Node *gp = p->grandparent();
Node *fa = p->parent;
Node *y = p->rightTree;
fa->leftTree = y;
if (y != NIL)
y->parent = fa;
p->rightTree = fa;
fa->parent = p;
if (root == fa)
root = p;
p->parent = gp;
if (gp != NULL)
{
if (gp->leftTree == fa)
gp->leftTree = p;
else
gp->rightTree = p;
}
}
void rotate_left(Node *p)
{
if (p->parent == NULL)
{
root = p;
return;
}
Node *gp = p->grandparent();
Node *fa = p->parent;
Node *y = p->leftTree;
fa->rightTree = y;
if (y != NIL)
y->parent = fa;
p->leftTree = fa;
fa->parent = p;
if (root == fa)
root = p;
p->parent = gp;
if (gp != NULL)
{
if (gp->leftTree == fa)
gp->leftTree = p;
else
gp->rightTree = p;
}
}
void inorder(Node *p)
{
if (p == NIL)
return;
if (p->leftTree)
inorder(p->leftTree);
cout << p->value << " ";
if (p->rightTree)
inorder(p->rightTree);
}
string outputColor(bool color)
{
return color ? "BLACK" : "RED";
}
Node* getSmallestChild(Node *p)
{
if (p->leftTree == NIL)
return p;
return getSmallestChild(p->leftTree);
}
bool delete_child(Node *p, int data)
{
if (p->value > data)
{
if (p->leftTree == NIL)
{
return false;
}
return delete_child(p->leftTree, data);
}
else if (p->value < data)
{
if (p->rightTree == NIL)
{
return false;
}
return delete_child(p->rightTree, data);
}
else if (p->value == data)
{
if (p->rightTree == NIL)
{
delete_one_child(p);
return true;
}
Node *smallest = getSmallestChild(p->rightTree);
swap(p->value, smallest->value);
delete_one_child(smallest);
return true;
}
else
{
return false;
}
}
void delete_one_child(Node *p)
{
Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL)
{
p = NULL;
root = p;
return;
}
if (p->parent == NULL)
{
delete p;
child->parent = NULL;
root = child;
root->color = BLACK;
return;
}
if (p->parent->leftTree == p)
{
p->parent->leftTree = child;
}
else
{
p->parent->rightTree = child;
}
child->parent = p->parent;
if (p->color == BLACK)
{
if (child->color == RED)
{
child->color = BLACK;
}
else
delete_case(child);
}
delete p;
}
void delete_case(Node *p)
{
if (p->parent == NULL)
{
p->color = BLACK;
return;
}
if (p->sibling()->color == RED)
{
p->parent->color = RED;
p->sibling()->color = BLACK;
if (p == p->parent->leftTree)
rotate_left(p->sibling());
else
rotate_right(p->sibling());
}
if (p->parent->color == BLACK && p->sibling()->color == BLACK
&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK)
{
p->sibling()->color = RED;
delete_case(p->parent);
}
else if (p->parent->color == RED && p->sibling()->color == BLACK
&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK)
{
p->sibling()->color = RED;
p->parent->color = BLACK;
}
else
{
if (p->sibling()->color == BLACK)
{
if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED
&& p->sibling()->rightTree->color == BLACK)
{
p->sibling()->color = RED;
p->sibling()->leftTree->color = BLACK;
rotate_right(p->sibling()->leftTree);
}
else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
&& p->sibling()->rightTree->color == RED)
{
p->sibling()->color = RED;
p->sibling()->rightTree->color = BLACK;
rotate_left(p->sibling()->rightTree);
}
}
p->sibling()->color = p->parent->color;
p->parent->color = BLACK;
if (p == p->parent->leftTree)
{
p->sibling()->rightTree->color = BLACK;
rotate_left(p->sibling());
}
else
{
p->sibling()->leftTree->color = BLACK;
rotate_right(p->sibling());
}
}
}
void insert(Node *p, int data)
{
if (p->value >= data)
{
if (p->leftTree != NIL)
insert(p->leftTree, data);
else
{
Node *tmp = new Node();
tmp->value = data;
tmp->leftTree = tmp->rightTree = NIL;
tmp->parent = p;
p->leftTree = tmp;
insert_case(tmp);
}
}
else
{
if (p->rightTree != NIL)
insert(p->rightTree, data);
else
{
Node *tmp = new Node();
tmp->value = data;
tmp->leftTree = tmp->rightTree = NIL;
tmp->parent = p;
p->rightTree = tmp;
insert_case(tmp);
}
}
}
void insert_case(Node *p)
{
if (p->parent == NULL)
{
root = p;
p->color = BLACK;
return;
}
if (p->parent->color == RED)
{
if (p->uncle()->color == RED)
{
p->parent->color = p->uncle()->color = BLACK;
p->grandparent()->color = RED;
insert_case(p->grandparent());
}
else
{
if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent)
{
rotate_left(p);
rotate_right(p);
p->color = BLACK;
p->leftTree->color = p->rightTree->color = RED;
}
else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent)
{
rotate_right(p);
rotate_left(p);
p->color = BLACK;
p->leftTree->color = p->rightTree->color = RED;
}
else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent)
{
p->parent->color = BLACK;
p->grandparent()->color = RED;
rotate_right(p->parent);
}
else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent)
{
p->parent->color = BLACK;
p->grandparent()->color = RED;
rotate_left(p->parent);
}
}
}
}
void DeleteTree(Node *p)
{
if (!p || p == NIL)
{
return;
}
DeleteTree(p->leftTree);
DeleteTree(p->rightTree);
delete p;
}
public:
bst()
{
NIL = new Node();
NIL->color = BLACK;
root = NULL;
}
~bst()
{
if (root)
DeleteTree(root);
delete NIL;
}
void inorder()
{
if (root == NULL)
return;
inorder(root);
cout << endl;
}
void insert(int x)
{
if (root == NULL)
{
root = new Node();
root->color = BLACK;
root->leftTree = root->rightTree = NIL;
root->value = x;
}
else
{
insert(root, x);
}
}
bool delete_value(int data)
{
return delete_child(root, data);
}
private:
Node *root, *NIL;
};
int main()
{
cout << "---【紅黑樹(shù)】---" << endl;
// 創(chuàng)建紅黑樹(shù)
bst tree;
// 插入元素
tree.insert(2);
tree.insert(9);
tree.insert(-10);
tree.insert(0);
tree.insert(33);
tree.insert(-19);
// 順序打印紅黑樹(shù)
cout << "插入元素后的紅黑樹(shù)：" << endl;
tree.inorder();
// 刪除元素
tree.delete_value(2);
// 順序打印紅黑樹(shù)
cout << "刪除元素 2 后的紅黑樹(shù)：" << endl;
tree.inorder();
// 析構(gòu)
tree.~bst();
getchar();
return 0;
}

9 B樹(shù)/B+樹(shù)

在計(jì)算機(jī)科學(xué)中，B樹(shù)(B-tree)是一種樹(shù)狀數(shù)據(jù)結(jié)構(gòu)，它能夠存儲(chǔ)數(shù)據(jù)、對(duì)其進(jìn)行排序并允許以O(shè)(log n)的時(shí)間復(fù)雜度運(yùn)行進(jìn)行查找、順序讀取、插入和刪除的數(shù)據(jù)結(jié)構(gòu)。B樹(shù)，概括來(lái)說(shuō)是一個(gè)節(jié)點(diǎn)可以擁有多于2個(gè)子節(jié)點(diǎn)的二叉查找樹(shù)。與自平衡二叉查找樹(shù)不同，B-樹(shù)為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫操作。B-tree算法減少定位記錄時(shí)所經(jīng)歷的中間過(guò)程，從而加快存取速度。普遍運(yùn)用在數(shù)據(jù)庫(kù)和文件系統(tǒng)。

——維基百科

B 樹(shù)可以看作是對(duì)2-3查找樹(shù)的一種擴(kuò)展，即他允許每個(gè)節(jié)點(diǎn)有M-1個(gè)子節(jié)點(diǎn)。

• 定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子；且M>2；
• 根結(jié)點(diǎn)的兒子數(shù)為[2, M]；
• 除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]；
• 每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1(取上整)和至多M-1個(gè)關(guān)鍵字；(至少2個(gè)關(guān)鍵字)
• 非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
• 非葉子結(jié)點(diǎn)的指針：P[1], P[2], …, P[M]；其中P[1]指向關(guān)鍵字小于K[1]的 子樹(shù)，P[M]指向關(guān)鍵字大于K[M-1]的子樹(shù)，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹(shù)；
• 所有葉子結(jié)點(diǎn)位于同一層；

如：(M=3)

算法思路：

從根結(jié)點(diǎn)開(kāi)始，對(duì)結(jié)點(diǎn)內(nèi)的關(guān)鍵字(有序)序列進(jìn)行二分查找，如果命中則結(jié)束，否則進(jìn)入查詢關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)；重復(fù)，直到所對(duì)應(yīng)的兒子指針為空，或已經(jīng)是葉子結(jié)點(diǎn)；

• 關(guān)鍵字集合分布在整顆樹(shù)中；
• 任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中；
• 搜索有可能在非葉子結(jié)點(diǎn)結(jié)束；
• 其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找；
• 自動(dòng)層次控制；

代碼：

BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)
{
int i = 0;
while (i < tree->keynum && key > tree->key[i])
{
++i;
}

// 查找關(guān)鍵字
if (i < tree->keynum && tree->key[i] == key)
{
*pos = i;
return tree;
}

// tree 為葉子節(jié)點(diǎn)，找不到 key，查找失敗返回
if (tree->isLeaf)
{
return NULL;
}

// 節(jié)點(diǎn)內(nèi)查找失敗，但 tree->key[i - 1]< key < tree->key[i]，
// 下一個(gè)查找的結(jié)點(diǎn)應(yīng)為 child[i]

// 從磁盤讀取第 i 個(gè)孩子的數(shù)據(jù)
disk_read(&tree->child[i]);

// 遞歸地繼續(xù)查找于樹(shù) tree->child[i]
return BTree_recursive_search(tree->child[i], key, pos);
}

B+樹(shù)：

B+樹(shù)是B樹(shù)的變體，也是一種多路搜索樹(shù)：

其定義基本與B-樹(shù)同，除了：

• 非葉子結(jié)點(diǎn)的子樹(shù)指針與關(guān)鍵字個(gè)數(shù)相同；
• 非葉子結(jié)點(diǎn)的子樹(shù)指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹(shù), B樹(shù)是開(kāi)區(qū)間
• 為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針;
• 所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)；

如:(M=3)

1

算法思路：

B+的搜索與B樹(shù)也基本相同，區(qū)別是B+樹(shù)只有達(dá)到葉子結(jié)點(diǎn)才命中(B樹(shù)可以在 非葉子結(jié)點(diǎn)命中)，其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找；

• 所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中(稠密索引)，且鏈表中的關(guān)鍵字恰好是有序的；
• 不可能在非葉子結(jié)點(diǎn)命中；
• 非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引(稀疏索引)，葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層；
• 更適合文件索引系統(tǒng)；

參考資料

https://www.sohu.com/a/296278527_478315

https://www.cnblogs.com/exzlc/p/12203744.htm

這2天，我發(fā)現(xiàn)一個(gè)超級(jí)好玩的社區(qū)，有興趣的同學(xué)，可以掃碼回復(fù)?github?試試！

長(zhǎng)按掃碼，回復(fù) C語(yǔ)言 有驚喜！

總結(jié)

以上是生活随笔為你收集整理的tail -f 查找关键字_C语言九种查找算法 | 总有一款适合你的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。