当前位置：首页 > 公众号精选 > C语言与CPP编程

九种查找算法

时间：2020-07-06 23:00:10
手机看文章

扫描二维码
随时随地手机看文章

[导读]时间、空间复杂度比较 查找算法 平均时间复杂度 空间复杂度 查找条件 顺序查找 O(n) O(1) 无序或有序 二分查找（折半查找） O(log2n) O(1) 有序 插值查找 O(log2(log2n)) O(1) 有序 斐波那契查找 O(log2n) O(1) 有序 哈希查找 O(1) O(n) 无序或有序 二叉查找




时间、空间复杂度比较

查找算法 平均时间复杂度 空间复杂度 查找条件
顺序查找 O(n) O(1) 无序或有序
二分查找（折半查找） O(log2n) O(1) 有序
插值查找 O(log2(log2n)) O(1) 有序
斐波那契查找 O(log2n) O(1) 有序
哈希查找 O(1) O(n) 无序或有序
二叉查找树（二叉搜索树查找） O(log2n)

红黑树 O(log2n)

2-3树 O(log2n - log3n)

B树/B+树 O(log2n)

1 顺序查找

算法思路：

对于任意一个序列，从一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

代码：

#include <stdio.h>
#include <stdlib.h>
#define keyType int
//2020.05.24
typedef struct
{
	keyType key;//查找表中每个数据元素的值
}ElemType;

typedef struct
{
	ElemType *elem;//存放查找表中数据元素的数组
	int length;//记录查找表中数据的总数量
}SSTable;

//创建查询数据
void Create(SSTable **st,int length)
{
	(*st)=(SSTable*)malloc(sizeof(SSTable));
	(*st)->length=length;
	(*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
	printf("输入表中的数据元素：\n");
	//根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据
	for (int i=1; i<=length; i++)
	{
		scanf("%d",&((*st)->elem[i].key));
	}
}

//顺序查找函数，其中key为要查找的元素
int Search_seq(SSTable *str,keyType key)
{
	//str->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置，起监视哨的作用
	int len = str->length;
	//从最后一个数据元素依次遍历，一直遍历到数组下标为0
	for(int i=1; i<len+1; i++)   //创建数据从数组下标为1开始，查询也从1开始
	{
		if(str->elem[i].key == key)
		{
			return i;
		}
	}
	//如果 i=0，说明查找失败；查找成功返回要查找元素key的位置i
	return 0;
}

int main()
{
	SSTable *str;
	int num;
	printf("请输入创建数据元素的个数：\n");
	scanf("%d",&num);
	Create(&str, num);
	getchar();
	printf("请输入要查找的数据：\n");
	int key;
	scanf("%d",&key);
	int location=Search_seq(str, key);
	if (location==0) {
		printf("查找失败");
	}else{
		printf("要查找的%d的顺序为：%d",key,location);
	}
	return 0;
}

运行结果：

查找成功
查找失败

2 二分查找（折半查找）

算法思路：

  1. 确定查找范围low=0，high=N-1，计算中项mid=（low+high）/2。

  2. 若mid==x或low>=high,则结束查找；否则，向下继续。

  3. 若amid<x,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给low，并重新计算mid，转去执行步骤2；若mid>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给higt，并重新计算mid，转去执行步骤2。

说明：

  • 查找元素必须是有序的，如果是无序的则要先进行排序操作。

  • 在做查找的过程中，如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。

折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

                         ——《大话数据结构》

代码：

#include <stdio.h>
#include <stdlib.h>
#define keyType int
typedef struct
{
	keyType key;//查找表中每个数据元素的值
}ElemType;

typedef struct
{
	ElemType *elem;//存放查找表中数据元素的数组
	int length;//记录查找表中数据的总数量
}SSTable;

//创建查询数据
void Create(SSTable **st,int length)
{
	(*st)=(SSTable*)malloc(sizeof(SSTable));
	(*st)->length=length;
	(*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
	printf("输入表中的数据元素：\n");
	//根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据
	for (int i=1; i<=length; i++)
	{
		scanf("%d",&((*st)->elem[i].key));
	}
}

//折半查找函数 key为要查找的元素
int Search_Bin(SSTable *str,keyType key)
{
	int low=1;//初始状态 low 指针指向第一个关键字
	int high=str->length;//high 指向最后一个关键字
	int mid;
	while (low<=high)
	{
		mid=(low+high)/2;//int 本身为整形，所以，mid 每次为取整的整数
		if(str->elem[mid].key==key)//如果 mid 指向的同要查找的相等，返回 mid 所指向的位置
		{
			return mid;
		}
        else if(str->elem[mid].key>key)//如果mid指向的关键字较大，则更新 high 指针的位置
		{
			high=mid-1;
		}
		//反之，则更新 low 指针的位置
		else
		{
			low=mid+1;
		}
	}
	return 0;
}

int main()
{
	SSTable *str;
	int num;
	printf("请输入创建数据元素的个数：\n");
	scanf("%d",&num);
	Create(&str, num);
	getchar();
	printf("请输入要查找的数据：\n");
	int key;
	scanf("%d",&key);
	int location=Search_Bin(str, key);
	if (location==0) {
		printf("没有查找到");
	}else{
		printf("要查找的%d的顺序为：%d",key,location);
	}
	return 0;
}

运行结果：

查找成功
没有查找到

3 插值查找

插值查找基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找

算法思路：

  1. 确定查找范围low=0，high=N-1，计算中项mid=low+(key-a[low])/(a[high]-a[low])*(high-low)。

  2. 若mid==x或low>=high,则结束查找；否则，向下继续。

  3. 若amid<x,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给low，并重新计算mid，转去执行步骤2；若mid>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给higt，并重新计算mid，转去执行步骤2。

说明：

  • 插值查找是基于折半查找进行了优化的查找方法。
  • 当表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能要比折半查找要好得多。

代码：

#include<stdio.h>

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);
       
       // 没有找到
       if(array[mid] == data)
       {
	   index = mid;
           break;
        }
	else
	{
	   if(array[mid] < data)
           {
               low = mid + 1;
           }
           else
	   {
	       high = mid - 1;
	    }
	 }
     }

     printf("比较次数: %d\n", --comparisons);
     return index;
}

int main()
{
    int location = InsertionSearch(27);  //测试代，查27，可以找到
    if(location != -1)
    {
	printf("查找元素顺序为: %d\n" ,(location+1));
     }
     else
     {
         printf("没有查找到");
     }
     return 0;
}

运行结果：

运行结果

4 斐波那契查找

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1；开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1).

算法思路：

  1. 相等，mid位置的元素即为所求

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

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

说明：

low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。

代码：

#include "stdafx.h"
#include <memory>
#include  <iostream>
using namespace std;

const int max_size=20;//斐波那契数组的长度

/*构造一个斐波那契数组*/
void Fibonacci(int * F)
{
    F[0]=0;
    F[1]=1;
    for(int i=2;i<max_size;++i)
        F[i]=F[i-1]+F[i-2];
}

/*定义斐波那契查找法*/
int FibonacciSearch(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
{
  int low=0;
  int high=n-1;
  
  int F[max_size];
  Fibonacci(F);//构造一个斐波那契数组F

  int k=0;
  while(n>F[k]-1)//计算n位于斐波那契数列的位置
      ++k;

  int  * temp;//将数组a扩展到F[k]-1的长度
  temp=new int [F[k]-1];
  memcpy(temp,a,n*sizeof(int));

  for(int i=n;i<F[k]-1;++i)
     temp[i]=a[n-1];
  
  while(low<=high)
  {
    int mid=low+F[k-1]-1;
    if(key<temp[mid])
    {
      high=mid-1;
      k-=1;
    }
    else if(key>temp[mid])
    {
     low=mid+1;
     k-=2;
    }
    else
    {
       if(mid<n)
           return mid; //若相等则说明mid即为查找到的位置
       else
           return n-1; //若mid>=n则说明是扩展的数值,返回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<<"没有找到"<<key;
	}
	else
	{
       cout<<key<<" 的位置是:"<<index;
	}
    return 0;
}

运行结果：

47的位置为5

5 哈希查找

哈希表：

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。

"直接定址"与"解决冲突"是哈希表的两大特点。

哈希函数：

规则：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。

算法思路：

如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

  1. 用给定的哈希函数构造哈希表；
  2. 根据选择的冲突处理方法(常见方法：拉链法和线性探测法)解决地址冲突；
  3. 在哈希表的基础上执行哈希查找；

代码：

#include<stdio.h>
#include<stdlib.h>

#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;

// 哈希表每次重建增长后的大小
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;
}

// 哈希函数：除留余数法
int Hash(KeyType key, int m)
{
	return (3 * key) % m;
}

// 处理哈希冲突：线性探测
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");
}

// 函数声明：插入哈希表
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++]);
	//把所有元素，按照新哈希函数放到新表中
	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))
	{ //没有相同key
		if (c*1.0 / H.size < 0.5)
		{ //冲突次数未达到上线
			//插入代码
			H.rcd[p].key = key;
			H.tag[p] = 1;
			H.count++;
			return SUCCESS;
		}
		else recreateHash(H); //重构哈希表
	}
	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("删除成功，此时哈希表为：\n");
		printHash(H);
	}

	//查询哈希表
	printf("查询哈希表中key为67的元素\n");
	if (SUCCESS == SearchHash(H, 67, p, c)) printf("查询成功\n");

	//再次插入，测试哈希表的重建
	printf("再次插入，测试哈希表的重建：\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 二叉树查找

二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

算法思路：

  1. 若b是空树，则搜索失败：
  2. 若x等于b的根节点的数据域之值，则查找成功：
  3. 若x小于b的根节点的数据域之值，则搜索左子树：
  4. 查找右子树。

代码：

递归和非递归

//非递归查找算法
BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p)
{
    //查找函数返回指向关键字值为key的结点指针，不存在则返回NULL
    p=NULL;
    while(T!=NULL&&key!=T->data)
    {
        p=T;                          //指向被查找结点的双亲
        if(key<T->data)
            T=T->lchild;              //查找左子树
        else
            T=T->rchild;              //查找右子树
    }
    return T;
}

//递归算法
Status Search_BST(BiTree T, int key, BiTree f, BiTree *p)
{
    //查找BST中是否存在key，f指向T双亲，其初始值为NULL
    //若查找成功，指针p指向数据元素结点，返回true；
    //若失败，p指向查找路径上访问的最后一个结点并返回false
    if(!T)
    {
        *p=f;
        return false;
    }
    else if(key==T->data)
    {                      //查找成功
        *p=T;
        return true;
    }
    else if(key<T->data)
        return Search_BST(T->lchild,key,T,p);   //递归查找左子树
    else
        return Search_BST(T->rchild,key,T,p);   //递归查找右子树
    
}

7 2-3树

2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：

  1. 要么为空，要么：

  2. 对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。

  3. 对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。

算法思路:

要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中的任何一个相等，查找命中。否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。

2-3 树中查找键为H的节点
2-3 树中查找键为B的节点

代码：

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 红黑树

2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgn，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。

理解红黑树一句话就够了：红黑树就是用红链接表示3-结点的2-3树。

现在我们对2-3树进行改造，改造成一个二叉树。怎么改造呢？对于2节点，保持不变；对于3节点，我们首先将3节点中左侧的元素标记为红色，然后我们将其改造成图3的形式；

再将3节点的位于中间的子节点的父节点设置为父节点中那个红色的节点，如图4的所示；最后我们将图4的形式改为二叉树的样子，如图5所示。图5是不是很熟悉，没错，这就是我们常常提到的大名鼎鼎的红黑树了。如下图所示。

2-3树转红黑树

为什么使用红黑树：

  • 红黑树是一种平衡树，他复杂的定义和规则都是为了保证树的平衡性。如果树不保证他的平衡性就是下图：很显然这就变成一个链表了。
  • 保证平衡性的最大的目的就是降低树的高度，因为树的查找性能取决于树的高度。所以树的高度越低搜索的效率越高！
  • 这也是为什么存在二叉树、搜索二叉树等，各类树的目的。

红黑树性质：

  • 每个节点要么是黑色，要么是红色。
  • 根节点是黑色。
  • 每个叶子节点（NIL）是黑色。
  • 每个红色结点的两个子结点一定都是黑色。
  • 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

算法思路：

红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。

代码：

#define BLACK 1
#define RED 0
#include <iostream>

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 << "---【红黑树】---" << endl;
	// 创建红黑树
	bst tree;

	// 插入元素
	tree.insert(2);
	tree.insert(9);
	tree.insert(-10);
	tree.insert(0);
	tree.insert(33);
	tree.insert(-19);

	// 顺序打印红黑树
	cout << "插入元素后的红黑树：" << endl;
	tree.inorder();

	// 删除元素
	tree.delete_value(2);

	// 顺序打印红黑树
	cout << "删除元素 2 后的红黑树：" << endl;
	tree.inorder();

	// 析构
	tree.~bst();

	getchar();
	return 0;
}

9 B树/B+树

在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。

                             ——维基百科

B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。

  • 定义任意非叶子结点最多只有M个儿子；且M>2；
  • 根结点的儿子数为[2, M]；
  • 除根结点以外的非叶子结点的儿子数为[M/2, M]；
  • 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
  • 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  • 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的 子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  • 所有叶子结点位于同一层；

如：（M=3）

算法思路：

从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

  • 关键字集合分布在整颗树中；
  • 任何一个关键字出现且只出现在一个结点中；
  • 搜索有可能在非叶子结点结束；
  • 其搜索性能等价于在关键字全集内做一次二分查找；
  • 自动层次控制；

代码：

BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)
{
    int i = 0;
    while (i < tree->keynum && key > tree->key[i])
    {
        ++i;
    }
   
    // 查找关键字
    if (i < tree->keynum && tree->key[i] == key)
    {
        *pos = i;
        return tree;
    }
   
    // tree 为叶子节点，找不到 key，查找失败返回
    if (tree->isLeaf)
    {
        return NULL;
    }
   
    // 节点内查找失败，但 tree->key[i - 1]< key < tree->key[i]，
    // 下一个查找的结点应为 child[i]
   
    // 从磁盘读取第 i 个孩子的数据
    disk_read(&tree->child[i]);
   
    // 递归地继续查找于树 tree->child[i]
    return BTree_recursive_search(tree->child[i], key, pos);
}

B+树：

B+树是B树的变体，也是一种多路搜索树：

其定义基本与B-树同，除了：

  • 非叶子结点的子树指针与关键字个数相同；
  • 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树, B树是开区间
  • 为所有叶子结点增加一个链指针;
  • 所有关键字都在叶子结点出现；

如:（M=3）

1

算法思路：

B+的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在 非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

  • 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
  • 不可能在非叶子结点命中；
  • 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
  • 更适合文件索引系统；

参考资料

  1. https://www.sohu.com/a/296278527_478315
  2. https://www.cnblogs.com/exzlc/p/12203744.html
  3. 部分配图来源于网络

最近原创推荐

如何定义一个只能在(堆/栈)上生成对象的类

十大经典排序算法(动态演示+代码)

C语言与C++面试知识总结
数据结构之堆栈

一文轻松理解内存对齐

一文读懂C语言与C++动态内存

面试中常见的C语言与C++区别的问题

数据结构之线性表


免责声明：本文内容由21ic获得授权后发布，版权归原作者所有，本平台仅提供信息存储服务。文章仅代表作者个人观点，不代表本平台立场，如有问题，请联系我们，谢谢！

本站声明： 本文章由作者或相关机构授权发布，目的在于传递更多信息，并不代表本站赞同其观点，本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者，如若文章内容侵犯您的权益，请及时联系本站删除。
关闭
关闭