數(shù)據(jù)結(jié)構(gòu)與算法系列文章
數(shù)據(jù)結(jié)構(gòu)與算法 - 時(shí)間復(fù)雜度
數(shù)據(jù)結(jié)構(gòu)與算法 - 線性表
數(shù)據(jù)結(jié)構(gòu)與算法 - 樹形結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)與算法 - 查找

目錄

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

一、查找的定義

? ? 查找 又稱檢索，是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算。采用何種查找方法，首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來(lái)表示“表”，及表中的數(shù)據(jù)元素按何種方式組織。
? ? 查找有內(nèi)查找和外查找之分。若整個(gè)查找過(guò)程都在內(nèi)存進(jìn)行，則稱為內(nèi)查找；反之，若查找過(guò)程需要訪問外存，則稱為外查找。
? ? 關(guān)鍵字 是指數(shù)據(jù)元素(記錄)中某個(gè)項(xiàng)或組合項(xiàng)的值，用它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(記錄)。能唯一確定一個(gè)數(shù)據(jù)元素(記錄)的關(guān)鍵字，稱為主關(guān)鍵字；而不能唯一確定一個(gè)數(shù)據(jù)元素(記錄)的關(guān)鍵字，稱為次關(guān)鍵字。
? ? 查找表 是指由具有同一類型(屬性)的數(shù)據(jù)元素(記錄)組成的集合。分為靜態(tài)查表和動(dòng)態(tài)查找表。
? ? 靜態(tài)查找是指僅對(duì)查找表進(jìn)行查找操作，而不改變查找表中的數(shù)據(jù)元素。動(dòng)態(tài)查找是指除進(jìn)行查找操作外，可能還要進(jìn)行向表中插入或刪除數(shù)據(jù)元素的操作。

平均查找長(zhǎng)度

二、線性表的查找

? ? 2.1 、順序查找

? ? 順序查找( Sequential Search) 是一種最基本也是最簡(jiǎn)單的查找方法。它的基本思想是蠻力法，從表的一端開始，順序掃描線性表，逐個(gè)進(jìn)行結(jié)點(diǎn)關(guān)鍵字值與給定的值k相比較，若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與k相等，則查找成功；若掃描整個(gè)表后，仍未找到關(guān)鍵字與給定值k相等的結(jié)點(diǎn)，則查找失敗。
? ? 順序查找方法既適用于線性表的順序存儲(chǔ)結(jié)構(gòu)，也適用于線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。使用單鏈表作存儲(chǔ)結(jié)構(gòu)時(shí)，查找必須從頭指針開始，因此只能進(jìn)行順序查找。順序查找代碼如下：

    //蠻力法的算法 
    int n = 100; //規(guī)模
    int k = 20;  //查找目標(biāo)元素
    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次 目標(biāo)元素索引為%d", i,i);
            break;
        }
        if(i == n - 1){
            NSLog(@"沒有查找到目標(biāo)元素");
        }
    }

? ? 順序查找算法的 時(shí)間復(fù)雜度 為O(n)。
? ? 順序查找的優(yōu)點(diǎn)是算法簡(jiǎn)單，且對(duì)表的結(jié)構(gòu)無(wú)任何要求，無(wú)論用順序表還是鏈表來(lái)存放結(jié)點(diǎn)，也無(wú)論結(jié)點(diǎn)是否按關(guān)鍵字有序，都同樣適用。順序查找的缺點(diǎn)是查找效率低，當(dāng)n較大時(shí)，不宜采用順序查找。對(duì)于線性鏈表，只能進(jìn)行順序查找。

? ? 2.2 、二分查找

? ? 二分查找( Binary Search)又稱折半查找 ，是一種效率較高的查找方法。但是，二分查找要求線性表是 有序表 ，即表中的數(shù)據(jù)元素按關(guān)鍵字有序組織，并且要用順序表作為表的存儲(chǔ)結(jié)構(gòu)。
? ? 在下面討論中，假設(shè)有序表是遞增有序的。
? ? 二分查找的基本思想是減治法，首先將待查找的k值和有序表R中間位置mid=(1+m)/2上的結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較：
? ? (1)若相等，則查找完成。
? ? (2)若R[mid]。key>k，則說(shuō)明待查找的結(jié)點(diǎn)在表的前半部分中，可在前半部分表中繼續(xù)進(jìn)行二分查找。
? ? (3)若R[mid]。key<k，則說(shuō)明待查找的結(jié)點(diǎn)在表的后半部分中，可在后半部分表中繼續(xù)進(jìn)行二分查找。
? ? 這樣，經(jīng)過(guò)一次關(guān)鍵字的比較就縮小一半查找區(qū)間；如此反復(fù)，直到找到關(guān)鍵字為k的結(jié)點(diǎn)(查找成功)，或當(dāng)前的查找區(qū)間為空(查找失敗)。
? ? 二分查找示例代碼如下：

二分查找示例圖

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

? ? 二分查找算法的效率為O(log n)(以2為底的對(duì)數(shù))。效率比順序查找高，缺點(diǎn)是只適用于有序順序表。

? ? 2.3 、分塊查找

? ? 分塊查找( Blocking Search)又稱索引順序查找 ，是一種性能介于順序查找和二分查找之間的查找方法。
? ? 它要求按如下的索引方式來(lái)存儲(chǔ)查找表：將表均分為b塊，前b-1塊中的結(jié)點(diǎn)數(shù)為S=[n/b]，第b塊的結(jié)點(diǎn)數(shù)小于等于S；每一塊中的關(guān)鍵字不一定有序，但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字，即要求表是“分塊有序”的；抽取各塊中的最大關(guān)鍵字及其塊起始位置構(gòu)成一個(gè)索引表ID[b]，即IDi中存放著第i塊的最大關(guān)鍵字及該塊在表R中的起始位置。由于表R是分塊有序的，所以索引表是一個(gè)遞增有序表。

分塊查找示意圖

? ? 分塊查找的基本思想是 分治法 ，首先，查找索引表，因?yàn)樗饕硎怯行虮?，故可采用二分查找或順序查找，以確定待查的結(jié)點(diǎn)在哪塊；然后，在已確定的塊中進(jìn)行順序查找。

分塊查找的平均長(zhǎng)度

? ? 顯然，當(dāng)S=n時(shí)AS取極小值√n+1，即當(dāng)采用順序查找確定塊時(shí)，應(yīng)將各塊中的結(jié)點(diǎn)數(shù)選定為√n。
? ? 例如，若表有10000個(gè)結(jié)點(diǎn)，則應(yīng)把它分成100個(gè)塊，每塊中含100個(gè)結(jié)點(diǎn)。用順序查找確定塊，分塊查找平均需要做100次比較，而順序查找平均需要做5000次比較，二分查找最多需要14次比較。由此可見，分塊查找算法的效率介于順序查找和二分查找之間。

? ? 分塊查找的優(yōu)點(diǎn)是，在表中插入或刪除一個(gè)記最時(shí)，只要找到該記錄所屬的塊， 就在該塊中進(jìn)行插入或刪除運(yùn)算，因塊內(nèi)記錄的存放是任意的，所以，插入或刪除比較容易，無(wú)須移動(dòng)大量記錄。分塊查找的主要代價(jià)是需要增加一個(gè)輔助數(shù)組存儲(chǔ)索引表和對(duì)初始表進(jìn)行分塊排序建立索引表的運(yùn)算 。

三、樹表查找

? ? 由上可知，當(dāng)用線性表作為查找表的組織形式時(shí)，上面的三種查找法中，其中以二分查找效率最高。但由于二分查找要求表中結(jié)點(diǎn)按其關(guān)鍵字有序組織，且不能用鏈表作存儲(chǔ)結(jié)構(gòu)，因此，當(dāng)表的元素插入或刪除操作頻繁時(shí)，為維護(hù)表的有序性，勢(shì)必要移動(dòng)表中大量的結(jié)點(diǎn)，這種由移動(dòng)結(jié)點(diǎn)引起的額外的時(shí)間開銷，就會(huì)抵消二分查找的優(yōu)點(diǎn)。在這種情況下，可采用以下的幾種特殊的樹或二叉樹作為查找表的存儲(chǔ)結(jié)構(gòu)，在此將它們統(tǒng)稱為 樹表 。

? ? 3.1 、二叉排序樹

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

二叉排序樹示意圖

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

? ? 在二叉排序樹中插入新的結(jié)點(diǎn)，只要保證插入后仍符合二又排序樹的定義即可。插入過(guò)程和示意圖如下：
? ? (1)若二叉排序樹為空，則待插入結(jié)點(diǎn)s作為根結(jié)點(diǎn)插入到空樹中。
? ? (2)當(dāng)二叉排序樹非空，將待插結(jié)點(diǎn)的關(guān)鍵字s->key和樹根的關(guān)鍵字t->key進(jìn)行比較，若s->key=t->key，則說(shuō)明此樹中已有此結(jié)點(diǎn)，無(wú)須插入；若s->key<t->key，則將待插結(jié)點(diǎn)s插入根的左子樹中，否則將s插入根的右子樹中。
? ? (3)子樹中的插入過(guò)程與步驟(1)和步驟(2)相同，直到把結(jié)點(diǎn)s作為新的結(jié)點(diǎn)插入二叉排序樹中，或直到發(fā)現(xiàn)該樹中已有此*s結(jié)點(diǎn)為止。
? ? 顯然，插入過(guò)程從根結(jié)點(diǎn)開始逐層向下查找插入位置，且插入的結(jié)點(diǎn)必然是葉結(jié)點(diǎn)。

二叉排序樹的插入和生成示意圖

? ?? ? 3.1.2 、二叉排序樹的刪除

? ? 從二叉排序樹中刪除一個(gè)結(jié)點(diǎn)，不能把以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹都刪去，只能刪掉該結(jié)點(diǎn)，并且還要保證刪除后所得的二叉樹仍然是二叉排序樹。即在二叉排序樹中刪去一個(gè)結(jié)點(diǎn)相當(dāng)于刪去有序序列中的一個(gè)結(jié)點(diǎn)。

? ? 刪除操作必須首先進(jìn)行查找，以確定被刪除結(jié)點(diǎn)是否在二又排序樹中。若不在，則不做任何操作；否則，設(shè)找到被刪除的結(jié)點(diǎn)是p，f指向p的雙親，刪除操作可按p是否有左子樹來(lái)分別處理(當(dāng)然也可按p是否有右子樹來(lái)處理)：
? ? (1)若被刪除的結(jié)點(diǎn)p沒有左子樹，則刪除p時(shí)只要將p的右子樹按照二叉排序樹的特性鏈接到合適的位置即可，若p是根結(jié)點(diǎn)(有右子樹)，則只要將p的右子樹的根作為新的根結(jié)點(diǎn)；若p不是根結(jié)點(diǎn)，則刪除p時(shí)必須將它與其雙親f之間的鏈接斷開。所以，恰好可利用此鏈將待鏈接的p的右子樹鏈接到f的左(或右)鏈域上，即若p是f的左孩子，則將米p的右子樹鏈接到f的左鏈上，否則將p的右子樹鏈接到f的右鏈上，其指針變化如圖所示。顯然，若p的右指針樹為空，則p是樹葉，此時(shí)，p-> rchild=NULL，相當(dāng)于將空樹鏈接到f的左(或右)鏈域中。
? ? (2)若被刪除結(jié)點(diǎn)p有左子樹，p也可能有右子樹，因此，刪除p時(shí)應(yīng)考慮p的左子樹、右子樹鏈接到合適的位置，并保持二又排序樹的特性。此時(shí)有兩種操作：一是令p的左子樹直接鏈接到p的雙親f的左(或右)鏈域上，而p的右子樹下接到p的中序前驅(qū)結(jié)點(diǎn)S的右鏈上(s是p的左子樹中最右下的結(jié)點(diǎn)，即s是p的左子樹中關(guān)鍵字的值最大的結(jié)點(diǎn))，它的鏈域?yàn)榭?，其指針變化情況如圖所示；另一種是以p的中序前驅(qū)S頂替p(即把S的數(shù)據(jù)復(fù)制到p中)，將s的左子樹直接上接到s的雙親結(jié)點(diǎn)q的左(或右)鏈域上，然后刪去*s，其指針變化情況如圖所示。顯然，前一種操作法可能增加樹的深度，不如后一種做法好。

二叉排序樹的刪除示意圖

? ?? ? 3.1.3 、二叉排序樹查找

? ? 因?yàn)槎媾判驑淇煽醋鍪且粋€(gè)有序表，所以，在二叉排序樹上進(jìn)行查找，和二分法類似，也是一個(gè)逐步縮小查找范圍的過(guò)程。實(shí)際上在前面介紹的二叉排序樹的插入和刪除操作中都使用了查找操作。
? ? 查找算法思想如下：首先將待查關(guān)鍵字key與根節(jié)點(diǎn)關(guān)鍵字t進(jìn)行比較：
? ? a.如果key = t, 則返回根節(jié)點(diǎn)指針。
? ? b.如果key < t,則進(jìn)一步查找左子書。
? ? c.如果key > t,則進(jìn)一步查找右子樹。

? ? 在二叉排序樹上進(jìn)行查找，若查找成功，則是從根結(jié)點(diǎn)出發(fā)走一條從根到待查結(jié)點(diǎn)的路徑：若查找不成功，則是從根結(jié)點(diǎn)出發(fā)走一條從根到某個(gè)葉子結(jié)點(diǎn)的路徑。因此與二分查找類似，和關(guān)鍵字比較的次數(shù)不超過(guò)樹的深度。然而，二分查找法查找長(zhǎng)度為n的有序表，其判定樹是唯一的，而含有n個(gè)結(jié)點(diǎn)的二叉排序樹的形態(tài)卻不唯一。對(duì)于含有同樣一組結(jié)點(diǎn)的表，由于結(jié)點(diǎn)插入的先后次序不同，所構(gòu)成的二叉排序樹的形態(tài)和深度也不同，如下圖所示的樹：

結(jié)點(diǎn)插入的先后次序不同

//二叉排序樹查找算法
#include <stdio.h>
#include <stdlib.h>

typedef struct BSTNode {
    int data;
    struct BSTNode *lTree,*rTree;
}BSTNode,*BSTree;

//遞歸實(shí)現(xiàn)二叉排序樹的插入操作
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、葉子節(jié)點(diǎn)。
//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;
}
//創(chuàng)建二叉排序樹
void CreateBST(BSTree &BT,int n)  {  
    BT=NULL;//這里一定要將BT置空，表示剛開始的時(shí)候是空樹，不置空的話，編譯器分配的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);  
    }  
}

//遞歸實(shí)現(xiàn)搜索查找
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為底的對(duì)數(shù))。二叉排序樹的查找和二分查找相差不大，并且二又排序樹的插入和刪除結(jié)點(diǎn)十分方便，無(wú)須移動(dòng)大量結(jié)點(diǎn)，所以，對(duì)于需要經(jīng)常做插入、刪除和查找運(yùn)算的表，宜釆用二叉排序樹結(jié)構(gòu)。

? ? 3.2 、平衡二叉樹

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

平衡二叉樹和非平衡二叉樹

? ?? ? 3.2.1 、平衡二叉樹的構(gòu)造

? ? 動(dòng)態(tài)的保持二叉排序樹平衡的方法，其基本思想是：在構(gòu)造二叉樹的過(guò)程中，當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，首先，檢查是否因插入結(jié)點(diǎn)而破壞了樹的平衡性，若是，則找出其中最小不平衡子樹，在保持排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的鏈接關(guān)系，以達(dá)到新的平衡。
? ? 所謂最小不平衡樹，是指以離插入結(jié)點(diǎn)最近、且平衡因子絕對(duì)值大于1的結(jié)點(diǎn)作為根的子樹。為了方便，不妨假設(shè)二叉排序樹最小不平衡樹的根結(jié)點(diǎn)是A，調(diào)整該子樹的規(guī)律可歸納為以下4種情況：

LR型(先B左旋轉(zhuǎn)，后A右旋轉(zhuǎn))調(diào)整

LL型右旋調(diào)整

RL型(先B右旋轉(zhuǎn)，后A左旋轉(zhuǎn))調(diào)整

RR型左旋調(diào)整

? ?含有N個(gè)結(jié)點(diǎn)的AVL樹，樹的高度h=O(log n)(以2為底的對(duì)數(shù))。由于在AVL樹上查找時(shí)，和關(guān)鍵字比較的次數(shù)不會(huì)超過(guò)樹的高度h，且不再蛻變成單支樹的情形。因此，查找AVL樹的時(shí)間復(fù)雜度是O(log n)(以2為底的對(duì)數(shù))。然而，動(dòng)態(tài)平衡過(guò)程仍需耗費(fèi)不少的時(shí)間，故在實(shí)際應(yīng)用中是否采用AVL樹，還要根據(jù)具體情況而定。一般情況下，若結(jié)點(diǎn)關(guān)鍵字是隨機(jī)分布的，并且系統(tǒng)對(duì)平均查找長(zhǎng)度沒有苛求，則可使用二又排序樹。

注：文中的圖片均轉(zhuǎn)摘自網(wǎng)絡(luò)

推薦學(xué)習(xí)資料:

Swift從入門到精通
每周一道算法題
戀上數(shù)據(jù)結(jié)構(gòu)與算法（一）
戀上數(shù)據(jù)結(jié)構(gòu)與算法（二）

如果需要跟我交流的話：
※ Github： https://github.com/wsl2ls
※ 簡(jiǎn)書：http://www.itdecent.cn/u/e15d1f644bea
※ 微信公眾號(hào)：iOS2679114653
※ QQ：1685527540