[数据结构]查找

by Posted on

本文将展示数据结构中常见的查找方式以及使用它们的具体实现步骤。

1. 静态查找表和动态表找表

我们先看它们的定义

静态查找表（static search table）   只对查找表进行“查找”操作的一类查找表

动态查找表（dynamic search table）对查找表不仅进行“查找”操作，在查找过程中还同时插入新的数据元素或删除已有数据元素的一类查找表。

简单来说，静态表找表更像是我们平常所说的“查找”这么一个含义，它只对我们的查找表进行检索，搜索我们想要找的元素而不对其进行任何修改操作；与之相反，动态表找表则是对查找表进行搜索后，可以对其进行增加、删除、修改等操作的找表方式。

静态查找表 包含以下几种常见的方式：顺序查找、折半查找、索引顺序查找。

动态查找表 包含以下几种常见的方式：二叉排序树、平衡二叉树查找、2-3树查找、B-树查找、B+树查找、哈希表查找。

2.静态表找表

2.1顺序查找

顺序查找就是最普通的线性递增查找。

基本思想是，从表中第一个记录开始，逐个进行记录的关键字与给定值的比较，若某个记录的关键字与给定值比较相等，则查找成功；反之，若直至最后一个记录，其关键字与给定值比较都不等，则表明表中没有所查记录，查找不成功。

顺序查找的优点是，算法简单，且对表的结构无任何要求，无论用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。但是，顺序查找的缺点是，查找效率低，平均查找长度较大，特别是当n很大时，查找效率较低。

顺序查找查找平均长度：

假设查找每个记录的概率相等，即Pi = 1/n，则在等概率情况下顺序查找的平均查找长度为:

时间复杂度：T = O(n)

C++示例：

函数体：

int SequentialSearch(int* orilist, int length, int key)
{     
    int i;
    for(i = 0;i < length; ++i)
    {
        if(orilist[i] == key)
            return i;
    }
    return -1;
}

检验：

int orilist[] = {12, 23, 34, 53, 32, 24, 14, 15, 66, 77, 88, 99};
cout << "SequentialSearch: the index of 14 is " <<  SequentialSearch(orilist, 12, 66) << endl;

2.2折半查找

折半查找实际上为二分法在查找中的一种应用。

有个重要的前提就是：查找表必须已经排序才能使用折半查找。

折半查找基本思想是首先以整个表作为查找范围，用查找条件中给定值k与中间位置结点的关键字进行比较，若相等，则查找成功，否则根据比较结果缩小查找范围。如果k值小于关键字的值，由表的有序性可知查找的数据元素只有可能在表的左半部分（这里假设表为升序排列），所以继续对左子表进行折半查找；若k值大于中间结点的关键字值，则可判定查找的数据元素只可能在表的右半部，所以继续对右子表进行折半查找。

例：

已知一个有11个数据元素的有序表（关键字即为数据元素的值）：(04, 15, 20, 27, 39, 46, 59, 61, 78, 82, 95)，现要查找关键字为27和86的数据元素。下面分别给出查找过程，其中的方括号表示当前的查找区间，“↑”指向中间位置、下界和上界。查找给定值key = 27的过程如下：

图1、折半查找

时间复杂度：T = O(log2 n)

C++示例：

函数体：

int BinarySearch(int* orilist, int length, int key)
// orilist must be a sorted list in BinarySearch.
{
    int low,mid,high;
    low = 0;           //loweset index
    high = length - 1;          //highest index
    mid = (low + high) / 2; // middle element index
    while(low <= high)
    {
        if(key < orilist[mid])
            high = mid - 1;
        else if(key > orilist[mid])
            low = mid + 1;
        else
            return mid;
        mid = (low + high) / 2;
    } 
    return 0;
}

检验：

int orisortedlist[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
cout << "BinarySearch: the index of 4 is " <<  BinarySearch(orisortedlist, 12, 4) << endl;

2.3索引顺序查找

实现：

①先查找索引表。索引表是有序表，可进行折半查找或顺序查找，以确定待查的结点在哪一块；

②在已确定的块中进行顺序查找，由于块内无序，因此只能用顺序查找。

下面两种均是索引表查找，一种是查找表中按索引表的关键字分成了不同的块，而块内部是无序的，这种我们通过索引表找到块后，在块的内部通过顺序查找找到被搜索的内容；另一种则是块内部有序的，对于这种表，我们通过索引表找到块后，在块的里面可以通过顺序查找也可以通过折半查找来进行进一步搜索。

图2、索引表查找
图3、索引表查找

按我个人之见，索引表查找像是用索引表对一个表进行“粗查找”，在确定大致范围（也就算块）后再进行“细查找”，以此来降低查找需要的总次数，提升效率，不过这也是一种以空间换时间的做法。

C++示例：

struct结构体：

// Block is used in BlockSearch.
struct Block
{
    int maxvalue;
    int firstindex;
    int length;
} Blocks[3];

函数体：

int BlockSearch(int* orilist, Block* Blocks, int Blockslength, int key)
{
    for (int i = 0; i < Blockslength; ++i)
    {
        if (key < Blocks[i].maxvalue)
        {
            for (int j = Blocks[i].firstindex; j < Blocks[i].firstindex + Blocks[i].length; ++j)
            {
                if (orilist[j] == key)
                {
                    return j;
                }
            }
            return -1;
        }
    }
    return -1;
}

检验：

    int blocklist[] = {8, 16, 4, 20, 44, 33, 22, 50, 99, 56, 70, 100};
    Blocks[0].firstindex = 0;
    Blocks[0].maxvalue = 20;
    Blocks[0].length = 4;
    Blocks[1].firstindex = 4;
    Blocks[1].maxvalue = 50;
    Blocks[1].length = 4;
    Blocks[2].firstindex = 8;
    Blocks[2].maxvalue = 100;
    Blocks[2].length = 4;
    cout << "BlockSearch: the index of 33 is " <<  BlockSearch(blocklist, Blocks, 3, 33) << endl;

3.动态查表

3.1二叉排序树

定义：

二叉排序树（binary sort tree, BST）又称二叉查找（搜索）树（binary search tree, BST），是一种常用的动态查找表。 
二叉排序树可用非递归形式定义，即二叉排序树是一棵二叉树，它或者为空，或者具有如下性质：
①任一非叶子结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值；

②任一非叶子结点若有右孩子，则该结点的关键字值小于其右孩子结点的关键字值。

简单概括：

这是一颗二叉树，在树中有规律：左子节点数值 < 本节点数值 < 右子节点数值

图4、二叉排序树

二叉排序树增添元素：

例如，从空树出发，经过一系列的查找插入操作之后，可生成一棵二叉树。设查找的关键字序列为{38, 24, 17, 40, 45}，则生成的二叉排序树如图所示。

图5、二叉排序树增添元素

二叉排序树删除元素：

算法思想是在二叉排序树中删除任意一个结点时，都必须保证删除后的二叉树仍然是二叉排序树。在下列讨论过程中，假设被删结点为p，其双亲结点为f，删除过程如下。

①如果p为叶子结点，则直接删除该结点；如果p为根结点，则删除后二叉排序树变为空树。

②如果p只有左子树或只有右子树，可直接将f中指向p的指针改为指向p的左子树或右子树；如果p是f的左孩子，则p的左子树或右子树变为f的左孩子，否则p的左子树或右子树变为f的右孩子。

③如果p既有左子树又有右子树，根据二叉排序树的特点，可用p的中序下的前驱结点的值（或其中序下的后继结点的值）代替p的值，同时删除其中序下的前驱结点（或其中序下的后继结点），若p的中序前驱无右子树或p的中序后继无左子树，则转为②。

另外，还可直接将p的右子树代替p，同时将p的左子树变为p右子树中序第一个结点的左孩子，也可直接将p的左子树代替p，同时将p的右子树变为p左子树中序最后一个结点的右孩子。删除过程如下图所示。

图6、 二叉排序树删除元素

C++示例：

struct结构体：

struct BSTnode
{
    int value;
    BSTnode* leftnode = nullptr, * rightnode = nullptr;
};

函数体：

将元素插入到结点中

BSTnode* InsertElemnt(BSTnode* insertednode, int key)
{
    if (insertednode == nullptr)
    {
        insertednode = new BSTnode;
        insertednode->value = key;
    }
    else
    {
        if (key < insertednode->value)
        {
            if (insertednode->leftnode)
            {
                InsertElemnt(insertednode->leftnode, key);
            }
            else
            {
                insertednode->leftnode = new BSTnode;
                insertednode->leftnode->value = key;
            }
            
        }
        else
        {
            if (insertednode->rightnode)
            {
                InsertElemnt(insertednode->rightnode, key);
            }
            else
            {
                insertednode->rightnode = new BSTnode;
                insertednode->rightnode->value = key;
            }
        }
    }
    return insertednode;
}

构造BST

BSTnode* BuildBST(int* orilist, int length)
{
    if (length == 0)
    {
        return nullptr;
    }
    else if (length == 1)
    {
        BSTnode* ans = new BSTnode;
        ans->value = orilist[0];
        return ans;
    }
    else
    {
        BSTnode* head = new BSTnode;
        head->value = orilist[0];
        for (int i = 1; i < length; ++i)
        {
            head = InsertElemnt(head, orilist[i]);
        }
        return head;
    }
}

BST搜索

bool BSTSearch(BSTnode* head, int key)
{
    BSTnode* p = head;
    while (p->value != key)
    {
        if (p->leftnode || p->rightnode)
        {
            if (key < p->value)
            {
                if (p->leftnode)
                {
                    p = p->leftnode;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                if (p->rightnode)
                {
                    p = p->rightnode;
                }
                else
                {
                    return false;
                }
            }
        }
        else
        {
            return false;
        }
    }
    return true;
}

测试

int orilist[] = { 12, 23, 34, 53, 32, 24, 14, 15, 66, 77, 88, 99 };
BSTnode* BSThead = BuildBST(orilist, 12);
cout << "BSTSearch: hava 14 is " << BSTSearch(BSThead, 14) << endl;
cout << "BSTSearch: hava 16 is " << BSTSearch(BSThead, 16) << endl;

3.2平衡二叉树

平衡二叉树（balanced binary tree，BBT）又称AVL树。它或者是一棵空树，或者具有下列性质：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

图7、平衡二叉树

判断平衡二叉树，C++源码

#include <iostream>
using namespace std;

template <typename E>
class TreeNode
{
public:
    E value; // store the value (name、mark) of the node.
    TreeNode* left = nullptr; // Left child node.
    TreeNode* right = nullptr; // Right child node.
    int height; // Node's height.

    //functions
    TreeNode() {};
    TreeNode(E _value) : value(_value) {};
    TreeNode(TreeNode* _left, TreeNode* _right) : left(_left), right(_right) {};
    TreeNode(E _value, TreeNode* _left, TreeNode* _right) : value(_value), left(_left), right(_right) {};

};

template <typename E>
bool isBalanced(TreeNode<E>* _root);

int main()
{
    //Test Data
    //TreeNode<string>* H = new TreeNode<string>("H");
    TreeNode<string>* G = new TreeNode<string>("G");
    TreeNode<string>* E = new TreeNode<string>("E", G, nullptr);
    TreeNode<string>* F = new TreeNode<string>("F");
    TreeNode<string>* D = new TreeNode<string>("D");
    TreeNode<string>* B = new TreeNode<string>("B", D, E);
    TreeNode<string>* C = new TreeNode<string>("C", F, nullptr);
    TreeNode<string>* A = new TreeNode<string>("A", B, C);

    bool ans = isBalanced<string>(A);
    if (ans)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }

    return 0;
}
template <typename E>
bool isBalanced(TreeNode<E>* _root)
{
    if (!_root->left && !_root->right)
    {
        _root->height = 1;
        return true;
    }
    else
    {
        int leftheight = 0, rightheight = 0;
        bool leftBalanced = true, rightBalanced = true;
        if (_root->left)
        {
            leftBalanced = isBalanced(_root->left);
            leftheight = _root->left->height;
        }
        if (_root->right)
        {
            rightBalanced = isBalanced(_root->right);
            rightheight = _root->right->height;
        }

        _root->height = leftheight > rightheight ? leftheight + 1 : rightheight + 1;
        if (!leftBalanced || !rightBalanced)
        {
            return false;
        }
        else
        {
            if (abs(leftheight - rightheight) > 1)
            {
                return false;
            }
            else
            {
                return true;
            }
        }
    }
}

3.3 2-3树

2-3树是最简单的B-树(或-树)结构，其每个非叶节点都有两个或三个子女，而且所有叶都在同一层上。2-3树不是二叉树，其节点可拥有3个孩子。

2-3树的结点插入与删除：(此处转载自: 2-3树的插入和删除原理 – straightup – 博客园 (cnblogs.com) ，对原文有部分错误纠正、部分冗余内容删除、部分内容细化)

插入：

原有一2-3树如下：

情况一 空树

创建一个二节点作为根节点即可。

情况二 二节点的叶子节点

插入3: 直接插入,将该二节点变为三节点即可

情况三 三节点的叶子节点 ( 父节点为二节点 )

插入5:

1.根据左小右大,5应该插到6的左边,但是6所在的节点已经是三节点,且由于叶子节点必须要在同一层次(不能单独往下延伸)

2.不能够往下走,那就只能往上走,且父节点是二节点可扩展为三节点 3.将扩展节点的右节点的最左元素6上移,调整叶子节点(结果如图)

情况四 三节点的叶子节点 ( 父节点为三节点 )

插入11:

1.根据数值应该插入到10的右边,但10所在的节点已经为三节点了,同时其父节点也为三节点

2.继续往上找,父节点的父节点为二节点可扩展 3.将扩展的节点的右节点的最左元素12上移 4.9,10,11按照中序遍历的方式调整

情况五 三节点的叶子节点 ( 父节点及其以上均为三节点 )

插入2:

1.按照数值大小,应该插入到1的右边,但1所在节点及其上面的所有节点都是三节点了,挤不下了,这时候就要增加高度了

2.从下往上拆,最后全部节点都变为二节点

删除：

情况一 删除元素所在节点是三节点

直接删除,将三节点变为二节点即可

情况二 删除元素位于二节点 ( 父节点为二节点 , 右孩子为三节点)

删除1:

1.删掉1

2.左旋转,将4放到1所在的位置,6放到4所在的位置

情况三 删除元素位于二节点 ( 父节点为二节点 , 右孩子也为二节点)

删除4:

(要保持叶子在同一层)

1.首先要知道一点:图中7是根节点的直接前继,根节点的直接后继则是9

2.将后继9拿过来帮忙,放到8的位置,8则去左边帮忙,放到7的位置(本质也是左旋)

3.6,7也左旋调整

情况四 删除元素位于二节点 ( 父节点为三节点 )

删除10:

1.将父节点由三节点变为二节点

2.扩展原先父节点的中间节点

3.4 B-树（B树）

部分参考、截取自 ：

图解：什么是B树？（心中有 B 树，做人要虚心）一文读懂B-树 – 知乎 (zhihu.com)

B树、B+树详解 – Assassinの – 博客园 (cnblogs.com)

定义条件：

① 树中每个结点至多有m 棵子树；

② 若根结点不是叶子结点，则至少有两棵子树；

③ 除根之外的所有非叶子结点至少有[m/2]棵子树；(“[]”于此代表向上取址)

④ 所有的非叶子结点中包含下列信息数据：(P0, K1, P1, K2, P2, …, Kn, Pn)，其中，Ki（1≤i≤n）为关键字，且Ki＜Ki+1，Pi（1≤i≤n）为指向子树根结点的指针，且指针Pi–1所指子树中所有结点的关键字均小于Ki (i=1, 2, …, n)，Pn所指子树中所有结点的关键字均大于Kn，n（[m/2]-1≤n≤m-1）为关键字的个数； (“[]”于此代表向上取址)

结点数就是子树数目范围-1

⑤ 所有叶子结点都出现在同一层次上，且不包含任何信息（实际上这些结点不存在，指向这些结点的指针为空）。

下面是一个m取4的B-树

B-树中序遍历

B-树：

中序遍历结果：

插入元素：

例子1：

原B-树：

m取4，子树数目取[2,4]，结点元素数目取[1,3]。

插入关键字 I ：

例子2：

一棵m=5的B-树：

删除

首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除；删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中，然后是移动之后的情况；如果没有，直接删除。

  • 某结点中元素数目小于（m/2）-1,(m/2)向上取整，则需要看其某相邻兄弟结点是否丰满；
  • 如果丰满（结点中元素个数大于(m/2)-1），则向父节点借一个元素来满足条件；
  • 如果其相邻兄弟都不丰满，即其结点数目等于(m/2)-1，则该结点与其相邻的某一兄弟结点进行“合并”成一个结点；

接下来还以5阶B树为例，详细讲解删除的动作；

  • 关键要领，元素个数小于 2（m/2 -1）就合并，大于4（m-1）就分裂

如图依次删除依次删除【8】,【20】,【18】,【5】

首先删除元素【8】，当然首先查找【8】，【8】在一个叶子结点中，删除后该叶子结点元素个数为2，符合B树规则，操作很简单，咱们只需要移动【11】至原来【8】的位置，移动【12】至【11】的位置（也就是结点中删除元素后面的元素向前移动）

 下一步，删除【20】,因为【20】没有在叶子结点中，而是在中间结点中找到，咱们发现他的继承者【23】(字母升序的下个元素)，将【23】上移到【20】的位置，然后将孩子结点中的【23】进行删除，这里恰好删除后，该孩子结点中元素个数大于2，无需进行合并操作。

下一步删除【18】，【18】在叶子结点中,但是该结点中元素数目为2，删除导致只有1个元素，已经小于最小元素数目2,而由前面我们已经知道：如果其某个相邻兄弟结点中比较丰满（元素个数大于ceil(5/2)-1=2），则可以向父结点借一个元素，然后将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中，在这个实例中，右相邻兄弟结点中比较丰满（3个元素大于2），所以先向父节点借一个元素【23】下移到该叶子结点中，代替原来【19】的位置，【19】前移；然【24】在相邻右兄弟结点中上移到父结点中，最后在相邻右兄弟结点中删除【24】，后面元素前移。

最后一步删除【5】， 删除后会导致很多问题，因为【5】所在的结点数目刚好达标，刚好满足最小元素个数（ceil(5/2)-1=2）,而相邻的兄弟结点也是同样的情况，删除一个元素都不能满足条件，所以需要该节点与某相邻兄弟结点进行合并操作；首先移动父结点中的元素（该元素在两个需要合并的两个结点元素之间）下移到其子结点中，然后将这两个结点进行合并成一个结点。所以在该实例中，咱们首先将父节点中的元素【4】下移到已经删除【5】而只有【6】的结点中，然后将含有【4】和【6】的结点和含有【1】,【3】的相邻兄弟结点进行合并成一个结点。

也许你认为这样删除操作已经结束了，其实不然，在看看上图，对于这种特殊情况，你立即会发现父节点只包含一个元素【7】，没达标（因为非根节点包括叶子结点的元素K必须满足于2=<K<=4，而此处的K=1），这是不能够接受的。如果这个问题结点的相邻兄弟比较丰满，则可以向父结点借一个元素。而此时兄弟节点元素刚好为2，刚刚满足，只能进行合并，而根结点中的唯一元素【13】下移到子结点，这样，树的高度减少一层。

3.4 B+树

B+树和B-树的主要区别如下：

B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。

B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。

查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束

B-树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次。

有m个子树的中间节点包含有m个元素（B树中是k-1个元素）。

B+树长得像下面这样：

B+树的查找：

对B+树可进行两种查找运算：一种是利用head指针从最小关键字开始顺序查找，另一种是利用root指针从根结点开始进行随机查找。在查找过程中，若非叶子结点上的关键字等于给定值，此时并不结束查找，而是继续向下直到叶子结点，其余的操作同B–树的查找类似。

下面例子来自MySQL索引底层：B+树详解 – 知乎 (zhihu.com)，这种B+树形式与我们刚刚所讲有点不同，供参考。

假设我们要查的值为32.

第一次磁盘 I/O，查找磁盘块1，即根节点(36,43),因为32小于36，因此访问根节点的左边第一个孩子节点

第二次磁盘 I/O, 查找磁盘块2，即根节点的第一个孩子节点，获得区间(28,32),遍历即可得32.

B+ 树范围查询

假设我们要查找区间 [32,40]区间的值.

第一步先访问根节点，发现区间的左端点32小于36,则访问根节点的第一个左子树(28,32);

第二步访问节点(28,32)，找到32，于是开始遍历链表，把[32,40]区间值找出来，这也是B+树比B-树高效的地方。

B+树的插入：

B+树的删除也仅在叶子结点中进行，当叶子结点中的最大关键字被删除时，其在非叶子结点中的值可作为一个“分界关键字”存在，若因删除而使结点中关键字的个数小于[m/2](向上取整)，则需要和兄弟结点进行合并，合并的过程与B–树类似。

  • 1.B+树插入都是在叶子结点进行的，就是插入前，需要先找到要插入的叶子结点。
  • 2.如果被插入关键字的叶子节点，当前含有的关键字数量是小于阶数m，则直接插入。
  • 3.如果插入关键字后，叶子节点当前含有的关键字数目等于阶数m，则插，该节点开始「分裂」为两个新的节点，一个节点包含⌊m/2⌋ 个关键字，另外一个关键字包含⌈m/2⌉个关键值。(⌊m/2⌋表示向下取整，⌈m/2⌉表示向上取整，如⌈3/2⌉=2)。
  • 4.分裂后，需要将第⌈m/2⌉的关键字上移到父结点。如果这时候父结点中包含的关键字个数小于m，则插入操作完成。
  • 5.分裂后，需要将⌈m/2⌉的关键字上移到父结点。如果父结点中包含的关键字个数等于m，则继续分裂父结点。

以一颗4阶的B+树为例子吧，4阶的话，关键值最多3(m-1)个。假设插入以下数据43，48，36，32,37,49,28.

1.在空树中插入43

这时候根结点就一个关键值，此时它是根结点也是叶子结点。

2.依次插入48，36

这时候跟节点拥有3个关键字，已经满了

3.继续插入 32，发现当前节点关键字已经不小于阶数4了，于是分裂 第⌈4/2⌉=2(下标0,1,2)个，也即43上移到父节点。

4.继续插入37，49，前节点关键字都是还没满的，直接插入，如下：

5.最后插入28，发现当前节点关键字也是不小于阶数4了，于是分裂，于是分裂， 第 ⌈4/2⌉=2个，也就是36上移到父节点，因父子节点只有2个关键值，还是小于4的，所以不用继续分裂，插入完成

B+树的删除

B+树的删除也仅在叶子结点中进行，当叶子结点中的最大关键字被删除时，其在非叶子结点中的值可作为一个“分界关键字”存在，若因删除而使结点中关键字的个数小[m/2](向上取整)，则需要和兄弟结点进行合并，合并的过程与B–树类似。

  • 找到包含关键值的结点，如果关键字个数大于⌈m/2⌉-1，直接删除即可;
  • 找到包含关键值的结点,如果关键字个数大于⌈m/2⌉-1，并且关键值是当前节点的最大(小)值，并且该关键值存在父子节点中，那么删除该关键字，同时需要相应调整父节点的值。
  • 找到包含关键值的结点，如果删除该关键字后，关键字个数小于⌈m/2⌉，并且其兄弟结点有多余的关键字，则从其兄弟结点借用关键字
  • 找到包含关键值的结点，如果删除该关键字后，关键字个数小于⌈m/2⌉，并且其兄弟结点没有多余的关键字，则与兄弟结点合并。
  • 如果关键字个数大于⌈m/2⌉，直接删除即可;

Published by vk

发表回复