數據結構與算法查找

NO IMAGE

數據結構與算法系列文章
數據結構與算法 – 時間複雜度
數據結構與算法 – 線性表
數據結構與算法 – 樹形結構
數據結構與算法 – 查找

目錄

一、查找的定義
二、線性表的查找
   2.1 、順序查找
   2.2、二分查找
   2.3、分塊查找
三、樹表查找
   3.1 、二叉排序樹
   3.2 、平衡二叉樹

一、查找的定義

    查找 又稱檢索,是數據處理中經常使用的一種重要運算。採用何種查找方法,首先取決於使用哪種數據結構來表示“表”,及表中的數據元素按何種方式組織。
    查找有內查找和外查找之分。若整個查找過程都在內存進行,則稱為內查找;反之,若查找過程需要訪問外存,則稱為外查找。
    關鍵字 是指數據元素(記錄)中某個項或組合項的值,用它可以標識一個數據元素(記錄)。能唯一確定一個數據元素(記錄)的關鍵字,稱為主關鍵字;而不能唯一確定一個數據元素(記錄)的關鍵字,稱為次關鍵字。
    查找表 是指由具有同一類型(屬性)的數據元素(記錄)組成的集合。分為靜態查表和動態查找表。
    靜態查找是指僅對查找表進行查找操作,而不改變查找表中的數據元素。動態查找是指除進行查找操作外,可能還要進行向表中插入或刪除數據元素的操作。

數據結構與算法查找

二、線性表的查找

    2.1 、順序查找

    順序查找( Sequential Search) 是一種最基本也是最簡單的查找方法。它的基本思想是***蠻力法***,從表的一端開始,順序掃描線性表,逐個進行結點關鍵字值與給定的值k相比較,若當前掃描到的結點關鍵字與k相等,則查找成功;若掃描整個表後,仍未找到關鍵字與給定值k相等的結點,則查找失敗。
    順序查找方法既適用於線性表的順序存儲結構,也適用於線性表的鏈式存儲結構。使用單鏈表作存儲結構時,查找必須從頭指針開始,因此只能進行順序查找。順序查找代碼如下:

    //蠻力法的算法 
int n = 100; //規模
int k = 20;  //查找目標元素
NSMutableArray * array = [NSMutableArray array];
for (int i = 0; i < n; i++) {
NSNumber * number = @(arc4random()%n);
[array addObject:number];
}
for (int i = 0; i < n; i++) {
NSNumber * number = array[i];
if ([number intValue] == k) {
NSLog(@"找了%d次 目標元素索引為%d", i,i);
break;
}
if(i == n - 1){
NSLog(@"沒有查找到目標元素");
}
}

    順序查找算法的 時間複雜度 為O(n)。
    順序查找的優點是算法簡單,且對錶的結構無任何要求,無論用順序表還是鏈表來存放結點,也無論結點是否按關鍵字有序,都同樣適用。順序查找的缺點是查找效率低,當n較大時,不宜採用順序查找。對於線性鏈表,只能進行順序查找。

    2.2 、二分查找

    二分查找( Binary Search)又稱折半查找 ,是一種效率較高的查找方法。但是,二分查找要求線性表是 有序表 ,即表中的數據元素按關鍵字有序組織,並且要用順序表作為表的存儲結構。
    在下面討論中,假設有序表是遞增有序的。
    二分查找的基本思想是減治法,首先將待查找的k值和有序表R中間位置mid=(1+m)/2上的結點的關鍵字進行比較:
    (1)若相等,則查找完成。
    (2)若R[mid]。key>k,則說明待查找的結點在表的前半部分中,可在前半部分表中繼續進行二分查找。
    (3)若R[mid]。key<k,則說明待查找的結點在表的後半部分中,可在後半部分表中繼續進行二分查找。
    這樣,經過一次關鍵字的比較就縮小一半查找區間;如此反覆,直到找到關鍵字為k的結點(查找成功),或當前的查找區間為空(查找失敗)。
    二分查找示例代碼如下:

數據結構與算法查找


int n = 100; //規模
int key = 39; //查找目標元素
//初始化元素數組
NSMutableArray * array = [NSMutableArray array];
for (int i = 0; i < n; i++) {
NSNumber * number = @(arc4random()%n);
[array addObject:number];
}
//對數組進行排序 升序
NSArray *sortedArray = [array sortedArrayUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
return [obj1 compare:obj2]; //升序
}];
//初始化查找元素的區間
int begin = 0;
int end = (int)sortedArray.count;
//查找目標元素索引
int keyIndex = BinarySearch(sortedArray, key, begin, end);
//二分查找遞歸函數 返回目標元素索引 -1表示沒有查找到
int BinarySearch(NSArray *sortedArray, int key, int begin, int end) {
//查找次數
static int i = 0;
i++;
//查找區間中間元素索引
int mid = -1;
mid = (begin + end)/2;
if(begin > end){
NSLog(@"沒有查找到目標元素");
return -1;
}
if ([sortedArray[mid] intValue] > key) {
end = mid - 1;
return BinarySearch(sortedArray, key, begin, end);
}else if([sortedArray[mid] intValue] == key){
NSLog(@"找了%d次 目標元素索引為%d",i,mid);
return mid;
}else {
begin = mid + 1;
return BinarySearch(sortedArray, key, begin, end);
}
}

    二分查找算法的效率為O(log n)(以2為底的對數)。效率比順序查找高,缺點是隻適用於有序順序表。

    2.3 、分塊查找

    分塊查找( Blocking Search)又稱索引順序查找 ,是一種性能介於順序查找和二分查找之間的查找方法。
    它要求按如下的索引方式來存儲查找表:將表均分為b塊,前b-1塊中的結點數為S=[n/b],第b塊的結點數小於等於S;每一塊中的關鍵字不一定有序,但前一塊中的最大關鍵字必須小於後一塊中的最小關鍵字,即要求表是“分塊有序”的;抽取各塊中的最大關鍵字及其塊起始位置構成一個索引表ID[b],即IDi中存放著第i塊的最大關鍵字及該塊在表R中的起始位置。由於表R是分塊有序的,所以索引表是一個遞增有序表。

數據結構與算法查找

    分塊查找的基本思想是 分治法 ,首先,查找索引表,因為索引表是有序表,故可採用二分查找或順序查找,以確定待查的結點在哪塊;然後,在已確定的塊中進行順序查找。

數據結構與算法查找

    顯然,當S=n時AS取極小值√n+1,即當採用順序查找確定塊時,應將各塊中的結點數選定為√n。
    例如,若表有10000個結點,則應把它分成100個塊,每塊中含100個結點。用順序查找確定塊,分塊查找平均需要做100次比較,而順序查找平均需要做5000次比較,二分查找最多需要14次比較。由此可見,分塊查找算法的效率介於順序查找和二分查找之間。

    分塊查找的優點是,在表中插入或刪除一個記最時,只要找到該記錄所屬的塊, 就在該塊中進行插入或刪除運算,因塊內記錄的存放是任意的,所以,插入或刪除比較容易,無須移動大量記錄。分塊查找的主要代價是需要增加一個輔助數組存儲索引表和對初始表進行分塊排序建立索引表的運算 。

三、樹表查找

    由上可知,當用線性表作為查找表的組織形式時,上面的三種查找法中,其中以二分查找效率最高。但由於二分查找要求表中結點按其關鍵字有序組織,且不能用鏈表作存儲結構,因此,當表的元素插入或刪除操作頻繁時,為維護表的有序性,勢必要移動表中大量的結點,這種由移動結點引起的額外的時間開銷,就會抵消二分查找的優點。在這種情況下,可採用以下的幾種特殊的樹或二叉樹作為查找表的存儲結構,在此將它們統稱為 樹表

    3.1 、二叉排序樹

    二又排序樹( Binary Sort Tree)又稱為二叉查找樹 ,是一種特殊的二叉樹。其定義為:二又排序樹或者是一棵空樹,或者是具有如下性質的二叉樹:
    (1)若它的左子樹非空,則左子樹上所有的結點的值均小於根結點的值。
    (2)若它的右子樹非空,則右子樹上所有的結點的值均大於根結點的值。
    (3)左、右子樹本身又各是一棵二又排序樹。
    從二叉排序樹的定義可得出二叉排序樹的一個重要性質:按中序遍歷該樹所得到的中序序列是一個遞增有序序列 。例如下圖:

數據結構與算法查找

       3.1.1 、二叉排序樹的插入和生成

    在二叉排序樹中插入新的結點,只要保證插入後仍符合二又排序樹的定義即可。插入過程和示意圖如下:
    (1)若二叉排序樹為空,則待插入結點s作為根結點插入到空樹中。
    (2)當二叉排序樹非空,將待插結點的關鍵字s->key和樹根的關鍵字t->key進行比較,若s->key=t->key,則說明此樹中已有此結點,無須插入;若s->keykey,則將待插結點
s插入根的左子樹中,否則將s插入根的右子樹中。
    (3)子樹中的插入過程與步驟(1)和步驟(2)相同,直到把結點
s作為新的結點插入二叉排序樹中,或直到發現該樹中已有此*s結點為止。
    顯然,插入過程從根結點開始逐層向下查找插入位置,且插入的結點必然是葉結點。

數據結構與算法查找

       3.1.2 、二叉排序樹的刪除

    從二叉排序樹中刪除一個結點,不能把以該結點為根結點的子樹都刪去,只能刪掉該結點,並且還要保證刪除後所得的二叉樹仍然是二叉排序樹。即在二叉排序樹中刪去一個結點相當於刪去有序序列中的一個結點。

    刪除操作必須首先進行查找,以確定被刪除結點是否在二又排序樹中。若不在,則不做任何操作;否則,設找到被刪除的結點是p,f指向p的雙親,刪除操作可按p是否有左子樹來分別處理(當然也可按p是否有右子樹來處理):
    (1)若被刪除的結點p沒有左子樹,則刪除p時只要將p的右子樹按照二叉排序樹的特性鏈接到合適的位置即可,若p是根結點(有右子樹),則只要將p的右子樹的根作為新的根結點;若p不是根結點,則刪除p時必須將它與其雙親f之間的鏈接斷開。所以,恰好可利用此鏈將待鏈接的p的右子樹鏈接到f的左(或右)鏈域上,即若p是f的左孩子,則將米p的右子樹鏈接到f的左鏈上,否則將p的右子樹鏈接到f的右鏈上,其指針變化如圖所示。顯然,若p的右指針樹為空,則p是樹葉,此時,p-> rchild=NULL,相當於將空樹鏈接到f的左(或右)鏈域中。
    (2)若被刪除結點p有左子樹,p也可能有右子樹,因此,刪除p時應考慮p的左子樹、右子樹鏈接到合適的位置,並保持二又排序樹的特性。此時有兩種操作:一是令p的左子樹直接鏈接到p的雙親f的左(或右)鏈域上,而p的右子樹下接到p的中序前驅結點S的右鏈上(s是p的左子樹中最右下的結點,即s是p的左子樹中關鍵字的值最大的結點),它的鏈域為空,其指針變化情況如圖所示;另一種是以p的中序前驅S頂替p(即把S的數據複製到p中),將s的左子樹直接上接到s的雙親結點q的左(或右)鏈域上,然後刪去*s,其指針變化情況如圖所示。顯然,前一種操作法可能增加樹的深度,不如後一種做法好。

數據結構與算法查找

       3.1.3 、二叉排序樹查找

    因為二叉排序樹可看做是一個有序表,所以,在二叉排序樹上進行查找,和二分法類似,也是一個逐步縮小查找範圍的過程。實際上在前面介紹的二叉排序樹的插入和刪除操作中都使用了查找操作。
    查找算法思想如下:首先將待查關鍵字key與根節點關鍵字t進行比較:
    a.如果key = t, 則返回根節點指針。
    b.如果key < t,則進一步查找左子書。
    c.如果key > t,則進一步查找右子樹。

    在二叉排序樹上進行查找,若查找成功,則是從根結點出發走一條從根到待查結點的路徑:若查找不成功,則是從根結點出發走一條從根到某個葉子結點的路徑。因此與二分查找類似,和關鍵字比較的次數不超過樹的深度。然而,二分查找法查找長度為n的有序表,其判定樹是唯一的,而含有n個結點的二叉排序樹的形態卻不唯一。對於含有同樣一組結點的表,由於結點插入的先後次序不同,所構成的二叉排序樹的形態和深度也不同,如下圖所示的樹:

數據結構與算法查找

//二叉排序樹查找算法
#include <stdio.h>
#include <stdlib.h>
typedef struct BSTNode {
int data;
struct BSTNode *lTree,*rTree;
}BSTNode,*BSTree;
//遞歸實現二叉排序樹的插入操作
void InsertBST(BSTree &BT,BSTNode *BN) {
if(BT==NULL)
BT=BN;
else if(BT->data > BN->data)
InsertBST(BT->lTree,BN);
else
InsertBST(BT->rTree,BN);
}
//刪除操作
//判斷它屬於哪種類型
//1、葉子節點。
//2、只有左子樹或者只有右子樹。
//3、既有左子樹,又有右子樹。
bool deleteBST(BSTree &BT,BSTNode *BN) {
BSTNode* tmp;
if(BN->lTree == NULL && BN->rTree == NULL)
delete BN;
else if(BN->lTree == NULL) {
tmp=BN;
BN=BN->rTree;
delete tmp;
}   else if(BN->rTree == NULL)  {
tmp=BN;
BN=BN->lTree;
delete tmp;
}    else
{
tmp=BN;
BSTNode * s = BN->lTree;
while (s->rTree) 
{ 
tmp = s; 
s = s->rTree; 
} 
BN->data = s->data;
if (tmp != BN) {
tmp->rTree = s->lTree;
}
else { 
tmp->lTree = s->lTree;
}
delete s;
}
return true;
}
//創建二叉排序樹
void CreateBST(BSTree &BT,int n)  {  
BT=NULL;//這裡一定要將BT置空,表示剛開始的時候是空樹,不置空的話,編譯器分配的BT是非空的  
int i,j;  
int r[100];  
BSTNode *s;  
for(j=0;j<n;j++)  
cin>>r[j];  
for(i=0;i<n;i++)  {  
s=new BSTNode;  
s->data=r[i];  
s->lTree=NULL;  
s->rTree=NULL;  
InsertBST(BT,s);  
}  
}
//遞歸實現搜索查找
BSTNode* searchBST(BSTree &BT,int value) {
if(BT==NULL)
return  NULL;
if(BT->data==value)
return BT;
if(BT->data>value)
return searchBST(BT->lTree,value);
if(BT->data<value)
return searchBST(BT->rTree,value);
}
int main() {
BSTree bt;
BSTNode * bn;
CreateBST(bt,20);
searchBST(bt,16);
return 0;
}

二叉排序樹的查的效率也為O(log n)(以2為底的對數)。二叉排序樹的查找和二分查找相差不大,並且二又排序樹的插入和刪除結點十分方便,無須移動大量結點,所以,對於需要經常做插入、刪除和查找運算的表,宜釆用二叉排序樹結構。

    3.2 、平衡二叉樹

    平衡二叉樹( Balanced Binary Tree或 Height-Balanced Tree)又稱為AVL樹 。它或者是一棵空樹,或者是任何結點的左子樹和右子樹的深度最多相差1的二又樹。若將二叉樹上的結點的 平衡因子 ( Balance Factor,BF)定義為該結點的左子樹的深度減去右子樹的深度,則平衡二叉樹上所有結點的平衡因子只可能是-1、0和1。只要二又樹上有一個結點的平衡因子的絕對值大於1,則該二叉樹就是不平衡的。平衡二叉樹的結點結構如下圖所示:

數據結構與算法查找

       3.2.1 、平衡二叉樹的構造

    動態的保持二叉排序樹平衡的方法,其基本思想是:在構造二叉樹的過程中,當插入一個結點時,首先,檢查是否因插入結點而破壞了樹的平衡性,若是,則找出其中最小不平衡子樹,在保持排序樹特性的前提下,調整最小不平衡子樹中各結點之間的鏈接關係,以達到新的平衡。
    所謂最小不平衡樹,是指以離插入結點最近、且平衡因子絕對值大於1的結點作為根的子樹。為了方便,不妨假設二叉排序樹最小不平衡樹的根結點是A,調整該子樹的規律可歸納為以下4種情況:

數據結構與算法查找

數據結構與算法查找

數據結構與算法查找

數據結構與算法查找

   含有N個結點的AVL樹,樹的高度h=O(log n)(以2為底的對數)。由於在AVL樹上查找時,和關鍵字比較的次數不會超過樹的高度h,且不再蛻變成單支樹的情形。因此,查找AVL樹的時間複雜度是O(log n)(以2為底的對數)。然而,動態平衡過程仍需耗費不少的時間,故在實際應用中是否採用AVL樹,還要根據具體情況而定。一般情況下,若結點關鍵字是隨機分佈的,並且系統對平均查找長度沒有苛求,則可使用二又排序樹。

注:文中的圖片均轉摘自網絡

如果需要跟我交流的話:
※ Github: github.com/wsl2ls
※ 簡書:www.jianshu.com/u/e15d1f644…
※ 微信公眾號:iOS2679114653
※ QQ:1685527540

相關文章

SDMemoryCache中的NSMapTable

關於IOS屬性atomic(原子性)的理解

GYHttpMock:使用及源碼解析

IOS組件化方案總結