时间、空间复杂度比较[td]

查找算法	平均时间复杂度	空间复杂度	查找条件
顺序查找	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)	% Y9 S* R. q  \+ @+ m8 \# _	- U" q2 J& \/ ?/ V: }' l# P
2-3树	O(log2n - log3n)	, e4 L/ ~2 ?  D8 o$ y$ x
B树/B+树	O(log2n)

1 顺序查找

算法思路：

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

代码：

#include <stdio.h>
#include <stdlib.h>
#define keyType int
//2020.05.24
typedef struct
4 X: n' A2 c: e  F6 M) P{
4 P6 T# o) P1 o7 y7 @1 K        keyType key;//查找表中每个数据元素的值
}ElemType;
3 C, g1 B' P. Q9 u$ `1 W$ _4 O
typedef struct
{
! J5 a5 L! X) S$ B# U/ o        ElemType *elem;//存放查找表中数据元素的数组
) f5 P# |4 l% n5 m% _        int length;//记录查找表中数据的总数量
}SSTable;

; P1 l; j  w8 _  M6 z& W/ E+ H//创建查询数据
void Create(SSTable **st,int length)
{
- j+ H1 |+ s1 ]2 P+ `' \: X* y2 n+ e        (*st)=(SSTable*)malloc(sizeof(SSTable));
+ o( w' }% O9 Z9 V  [# t        (*st)->length=length;
3 }# X4 b* f% P/ H        (*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
        printf("输入表中的数据元素：\n");
) Y, w% t( N4 X) }+ k* Z        //根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据
        for (int i=1; i<=length; i++)
- Y  {. D: t, e" |; ]/ J        {
3 ]$ f+ W3 y1 K# j1 E0 L                scanf("%d",&((*st)->elem.key));
6 a$ W% V2 ?$ e3 X2 T        }
}
! i( e5 {+ @% X% s7 W
* N5 C  Q& L6 G- D7 `//顺序查找函数，其中key为要查找的元素
int Search_seq(SSTable *str,keyType key)
{
6 f. w3 i9 R: N! C) _        //str->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置，起监视哨的作用
* M7 e, B! g2 P; W8 b) K        int len = str->length;
. s, K+ B! B3 h% {; C4 }8 ]        //从最后一个数据元素依次遍历，一直遍历到数组下标为0
% ^2 K1 w( l, I5 W6 K: z* M        for(int i=1; i<len+1; i++)   //创建数据从数组下标为1开始，查询也从1开始
* e, T5 n, i$ K# g8 @        {
- g  e/ |- S7 ^' e2 y6 |                if(str->elem.key == key)
                {
                        return i;
                }
, G/ D- k2 |4 W! w% Z9 a" {        }
% H( o. @7 U" H        //如果 i=0，说明查找失败；查找成功返回要查找元素key的位置i
        return 0;
: i6 U' [7 u' ^* Y) U  I7 W1 D}
# Y9 b6 Q5 y" v7 U" q+ r* Z
int main()
{
1 J$ B/ F7 F( c, r4 Q1 @% `. `        SSTable *str;
        int num;
; U+ ]) R& |$ k( \! W: \        printf("请输入创建数据元素的个数：\n");
% Y% K* ~! m4 x! d& G% S/ N5 h        scanf("%d",&num);
/ W) ^' P; O/ r: X' v        Create(&str, num);
2 ?7 ]1 m! s0 Q5 J& J- H$ Q        getchar();
        printf("请输入要查找的数据：\n");
0 @1 x+ w2 r' o- m# X+ H        int key;
        scanf("%d",&key);
        int location=Search_seq(str, key);
        if (location==0) {
2 b$ b" j/ m) x                printf("查找失败");
: s; z; }& f9 T; s3 X: B        }else{
7 e3 D* a3 x% T                printf("要查找的%d的顺序为：%d",key,location);
        }
4 ~1 R( J5 B" {* `- e        return 0;
4 [3 T6 I( Y6 \2 D$ L8 u3 ]" o+ f}

运行结果：

查找成功 查找失败
- {3 Z$ D& R2 M* G9 p2 二分查找（折半查找）

算法思路：

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

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

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

  
  

说明：

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

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

  
  2 @, d+ H# ^* Q

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

                         ——《大话数据结构》
! F) p2 S3 ^- z

代码：

#include <stdio.h>
/ _9 T, {* v' d! z#include <stdlib.h>
#define keyType int
typedef struct
{
; _% m# W8 ]. d3 Z  J" I7 v3 D        keyType key;//查找表中每个数据元素的值
}ElemType;

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

  t9 @( D! T! Y//创建查询数据
void Create(SSTable **st,int length)
{
8 z( h" d- Q; {7 u6 a$ a        (*st)=(SSTable*)malloc(sizeof(SSTable));
        (*st)->length=length;
        (*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
. r* O: F2 X# U3 ~, r        printf("输入表中的数据元素：\n");
        //根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据
        for (int i=1; i<=length; i++)
7 D; w0 i. R+ c# y        {
                scanf("%d",&((*st)->elem.key));
        }
8 f( i! R' V9 S9 n}
$ }3 ~' J$ I  `, i
//折半查找函数 key为要查找的元素
int Search_Bin(SSTable *str,keyType key)
{
        int low=1;//初始状态 low 指针指向第一个关键字
8 I  p, U$ h$ M- b. \: X  N, B        int high=str->length;//high 指向最后一个关键字
        int mid;
% j: {2 t( Z) @# T1 D0 }& b$ a3 @        while (low<=high)
# Q8 ?- F3 B, c7 K9 y. z( ~        {
                mid=(low+high)/2;//int 本身为整形，所以，mid 每次为取整的整数
9 V8 b, j9 _) W+ @" y9 ?/ ]6 H' O' ]                if(str->elem[mid].key==key)//如果 mid 指向的同要查找的相等，返回 mid 所指向的位置
                {
                        return mid;
                }
- \" y$ v) C) T% P0 d1 [- z        else if(str->elem[mid].key>key)//如果mid指向的关键字较大，则更新 high 指针的位置
                {
                        high=mid-1;
! J7 F" w' B/ v                }
0 V6 h- `# G' [) N( q; M                //反之，则更新 low 指针的位置
                else
                {
, H# t! d& o' ^0 x                        low=mid+1;
/ k) u. H, o8 E6 R  ^7 A                }
! T) u, Q% {# b8 b) }! u5 v        }
        return 0;
}
: F8 t% `5 a% C
int main()
{
        SSTable *str;
9 Y1 f  C' N; |        int num;
: y) ]' i1 z5 u! q2 o4 v7 c        printf("请输入创建数据元素的个数：\n");
        scanf("%d",&num);
        Create(&str, num);
        getchar();
        printf("请输入要查找的数据：\n");
        int key;
3 O- u8 `4 a+ ^( J        scanf("%d",&key);
' t# f7 |! H* T6 e: S        int location=Search_Bin(str, key);
        if (location==0) {
/ {; u6 \! P0 D6 I3 \6 a3 u                printf("没有查找到");
        }else{
                printf("要查找的%d的顺序为：%d",key,location);
$ v7 c$ v. }2 N% Q/ t/ `        }
        return 0;
}
8 k2 S; `% V9 s4 O' a8 J% c

运行结果：

查找成功 没有查找到
# c9 t. A1 z0 b& Z! b3 插值查找
+ V* {% v, S0 {" f

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

算法思路：

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

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

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

  
  " s( w& Y8 r" F% @) K4 ]

说明：

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

代码：

#include<stdio.h>

int array[10] = { 1, 4, 9, 16, 27, 31, 33, 35, 45, 64 };

int InsertionSearch(int data)
{
    int low = 0;
$ I* c0 `+ a5 C7 U7 Q; r! e3 L    int high = 10 - 1;
    int mid = -1;
6 @4 S" r$ d4 M; R* M+ r    int comparisons = 1;
3 X) x3 _' a1 A) Z- j$ M9 [% W    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]);
$ K% f' @, t' _' I3 }
       comparisons++;
       mid = low + (((double)(high - low) / (array[high] - array[low])) * (data - array[low]));
  @% w4 q5 R* e  L: e, i       printf("mid = %d\n",mid);
      
       // 没有找到
9 R$ h) h. J5 {. M' q* A, P       if(array[mid] == data)
9 N' @* d0 F0 e3 [! K! H9 _0 `9 Z9 {       {
) a( ^% @& s* i' {' j. ~3 D- A; H           index = mid;
0 t  [6 H- p( g0 j% F/ ^           break;
6 P& |* C1 L3 H# g0 G: B  A8 [        }
        else
, g( ~- r8 Y5 t' @9 U5 F        {
- c0 N% \$ M0 X5 b: G           if(array[mid] < data)
5 ]! T1 p- W; ?5 ?           {
               low = mid + 1;
           }
: C( ~0 y! b5 H$ d+ ^" i           else
  Y6 y" X5 y3 ]0 ~: S( d           {
& E( x! v# f7 }/ H9 l! @; T               high = mid - 1;
6 Q' B4 G; `2 N$ B* _+ c* G            }
         }
     }

1 s( ]9 N6 m8 Y4 Y     printf("比较次数: %d\n", --comparisons);
     return index;
: T7 K0 v! F9 l3 d7 l}

int main()
{
    int location = InsertionSearch(27);  //测试代，查27，可以找到
% K, S# P+ I/ A    if(location != -1)
! J) m8 p, _/ @5 U! o    {
        printf("查找元素顺序为: %d\n" ,(location+1));
     }
( Z5 Y: L9 H* P: Z  r     else
     {
         printf("没有查找到");
7 `$ N% F0 D: A5 A% P7 V     }
  [! e; w; w9 ^" E* u, @     return 0;
}

运行结果：

运行结果
  T0 l7 s  |7 _4 斐波那契查找

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

算法思路：

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

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

• 小于，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"
; W7 U, {) O/ p& S9 R" ]#include <memory>
#include  <iostream>
' _' I) C" f' I, vusing namespace std;
3 i! g$ p# h; o4 r9 a( ?; A) S* x2 i# u9 b
const int max_size=20;//斐波那契数组的长度
( ?/ ?9 q; a. x2 d: N6 W7 q) K  R
/*构造一个斐波那契数组*/
void Fibonacci(int * F)
* s8 O) i, X  Q: p6 W{
" o; X8 V/ r( j9 X$ v. ~+ V1 _    F[0]=0;
* K- o4 A3 i% [) b4 d    F[1]=1;
    for(int i=2;i<max_size;++i)
        F=F[i-1]+F[i-2];
8 X) ?# D, r% y' S8 }9 E}

* u, W9 p$ G/ B5 h3 y/*定义斐波那契查找法*/
int FibonacciSearch(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
{
  int low=0;
  int high=n-1;
7 n/ p: H9 P. ~6 `! n8 t  
! t" r( z3 Q# R, b% p  int F[max_size];
# S$ t% ?* V8 d3 _. z8 Y4 N  Fibonacci(F);//构造一个斐波那契数组F

& i: j# ~1 D( J7 ~  int k=0;
  while(n>F[k]-1)//计算n位于斐波那契数列的位置
      ++k;

9 {5 |& Q& [+ |' j+ a( Z( P. t  int  * temp;//将数组a扩展到F[k]-1的长度
4 g4 J7 c9 n7 ?0 V! f: p+ ?. k  temp=new int [F[k]-1];
  memcpy(temp,a,n*sizeof(int));

# L0 g# X3 ^: b! Z0 U  for(int i=n;i<F[k]-1;++i)
     temp=a[n-1];
  
  while(low<=high)
  g' Y) h  R, }3 Z9 [  {
3 w$ _% r" {3 `+ B9 U- M. C* R    int mid=low+F[k-1]-1;
" r4 S# \7 ~7 L! q+ w9 t1 m' o- t    if(key<temp[mid])
    {
/ e2 H; m- f+ {6 F2 s  ]      high=mid-1;
      k-=1;
    }
6 \7 ?  s! x" L2 L- S! N5 G    else if(key>temp[mid])
3 t* v0 [2 j. |! P8 l    {
7 o0 Q  B6 W- e8 e; b     low=mid+1;
     k-=2;
    }
& K! t" G9 }$ T/ Y4 {9 Y    else
    {
       if(mid<n)
+ ^, z4 W& Q) R7 I# j           return mid; //若相等则说明mid即为查找到的位置
       else
           return n-1; //若mid>=n则说明是扩展的数值,返回n-1
  @7 }4 G) q! b% c* [    }
' W5 Z% A2 p$ b7 n  }
  delete [] temp;
  return 0;
}

int main()
{
    int a[] = {0,1,4,35,47,53,62,78,88,99};
6 c/ W  T% ~& d: f! H( B6 X' j    int key=47;
( U3 g" K7 [3 t    int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
        if(index == 0)
        {
           cout<<"没有找到"<<key;
        }
; v  x. |, n2 V7 C4 ~, W        else
        {
& w* q1 A# o+ _" L- v# ~* \6 p  ~       cout<<key<<" 的位置是:"<<index;
        }
    return 0;
}
& `4 Q3 {. ^6 S( B. A

运行结果：

47的位置为5
+ g7 {2 ~. F! h; j5 哈希查找

哈希表：

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

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

哈希函数：

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

算法思路：

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

• 用给定的哈希函数构造哈希表；
• 根据选择的冲突处理方法(常见方法：拉链法和线性探测法)解决地址冲突；
• 在哈希表的基础上执行哈希查找；
  * H) W7 [& G; n3 {- N! l, T

代码：

#include<stdio.h>
% z  Z# S3 A  V6 \' J/ y8 h: W1 j$ e. }: d#include<stdlib.h>
+ ]. z1 v4 U3 h4 U7 B
#define SUCCESS 1
#define UNSUCCESS 0
#define OVERFLOW -1
#define OK 1
#define ERROR -1
' c0 Y' i2 k( W  }; R' \, k#define MAXNUM 9999                // 用于初始化哈希表的记录 key

typedef int Status;
typedef int KeyType;

# }: Q2 I- l- y2 I) L9 V// 哈希表中的记录类型
" b: i' z. q  Mtypedef struct
: {/ C  O# Q1 R& u' a* j{
1 L1 T9 `/ @0 z8 B- F        KeyType key;
9 Z& F+ L$ b6 g, z5 a1 \}RcdType;

" K- r" \0 q1 _+ F8 n// 哈希表类型
typedef struct
8 O0 W: Q- X9 ?$ e5 Y" J{
        RcdType *rcd;
* e1 w+ @! m% H( b5 s        int size;
        int count;
- U, Q% v: j# x: l1 i. n& n        int *tag;
}HashTable;

// 哈希表每次重建增长后的大小
. P, ~, }" R3 Q6 h; ], z* Yint hashsize[] = { 11, 31, 61, 127, 251, 503 };
int index = 0;

// 初始哈希表
0 L! s2 G' u! A% ]5 HStatus InitHashTable(HashTable &H, int size)
{
5 h" l/ K$ [& `2 p( j! k, ?        int i;
        H.rcd = (RcdType *)malloc(sizeof(RcdType)*size);
        H.tag = (int *)malloc(sizeof(int)*size);
$ }& Z  }; ^( ^8 u7 v4 u        if (NULL == H.rcd || NULL == H.tag) return OVERFLOW;
& l- W* y0 @0 e8 K4 G9 k4 b& o) D        KeyType maxNum = MAXNUM;
+ ^  O2 b) r: o& V& K        for (i = 0; i < size; i++)
        {
                H.tag = 0;
                H.rcd.key = maxNum;
        }
# D  [' H$ ~* @, U5 j* w        H.size = size;
1 _& F. v" A8 V1 X0 z$ b. I        H.count = 0;
3 ~2 S; }* I: z) J        return OK;
. C9 X6 s' s$ O}
/ O4 `, F1 k$ d7 R4 T2 Q; q; w
, L& i$ Y/ `) n// 哈希函数：除留余数法
7 i5 G/ ?; h, b6 s& F/ sint Hash(KeyType key, int m)
1 V; w  H6 g: ~  {{
1 J; u6 P  M9 Z! U/ e* R2 ~6 K- c  Q  H        return (3 * key) % m;
9 z8 q& g3 F" O9 ~3 D7 v) H}
; ?6 u( l3 o, x; J% c! M( ~
0 q& D- ~; b- }( j) e; U# y3 G2 }" g1 @// 处理哈希冲突：线性探测
void collision(int &p, int m)
7 V& ]' c; e. y( i{
8 }4 d$ y4 P$ C        p = (p + 1) % m;
}

, Q; j8 `4 h; F// 在哈希表中查询
8 a, {  V  c" C6 Y! A& @Status SearchHash(HashTable H, KeyType key, int &p, int &c)
9 O7 j7 I( b; k: v3 Y{
  V  k7 t7 P6 N( C( A% e" S' C        p = Hash(key, H.size);
        int h = p;
  S8 ~8 p! y1 Y* b; w4 r0 }* T        c = 0;
4 R& C, S! a$ V& Q        while ((1 == H.tag[p] && H.rcd[p].key != key) || -1 == H.tag[p])
9 r" E. ^  t& L! s3 t& n        {
2 D8 L) h: ]0 s! A! w4 {% L* [0 O                collision(p, H.size);  c++;
        }
! B" C: x" {1 U* a
        if (1 == H.tag[p] && key == H.rcd[p].key) return SUCCESS;
1 e/ R0 }; t+ C, p2 v        else return UNSUCCESS;
5 c. C+ E5 k7 V1 `# S* s+ r% b}
" a. U' B2 [9 D. p- C
//打印哈希表
" k4 M0 z; s0 ~void printHash(HashTable H)
7 }1 w/ L! i% ?1 W1 o0 ?{
) |5 q* Y- z2 u1 A2 S, C- \+ Q        int  i;
# Q% I  Y6 g3 ]# A7 @7 ?3 i* N        printf("key : ");
        for (i = 0; i < H.size; i++)
                printf("%3d ", H.rcd.key);
- h$ w( K; I6 N/ f        printf("\n");
- M/ h7 m" {# Q( @& H3 f0 |        printf("tag : ");
        for (i = 0; i < H.size; i++)
" d- x$ @( ]2 l5 I+ h" f                printf("%3d ", H.tag);
( ^  O8 t2 N5 i  W9 N) G2 }/ d        printf("\n\n");
6 w- W+ @% y, g1 u! _  C4 D}
- z2 m  |3 [) `" P8 D$ I
6 X/ T* {! e3 ~- X' v// 函数声明：插入哈希表
( M; R% b9 \7 h/ Q. z. u8 f* x' gStatus InsertHash(HashTable &H, KeyType key);

// 重建哈希表
# a5 }0 j* F/ GStatus recreateHash(HashTable &H)
  Q3 [) |- _# u. \; ^/ q  E# b  O{
. b* i# N4 c1 z( o7 B& f* E- b        RcdType *orcd;
        int *otag, osize, i;
4 S# h7 Y# p" p, A6 V        orcd = H.rcd;
% ^* K5 r; K( [4 g1 A7 G5 C* M( `' ~        otag = H.tag;
; L. u# T: ?) e2 Q$ Z6 Z        osize = H.size;

        InitHashTable(H, hashsize[index++]);
! T+ h0 j9 L+ N& Z' R        //把所有元素，按照新哈希函数放到新表中
0 _# A& ?# k% t( Z' b8 J        for (i = 0; i < osize; i++)
- A% g; P7 u  ^1 Q        {
- ^( N: e# @4 _8 H                if (1 == otag)
# T  ]: @; \/ l* t# l, @                {
                        InsertHash(H, orcd.key);
9 i4 _+ b7 j1 X                }
        }
        return OK;
& Y& y  n8 u, a! k3 P}
! ]0 P: L! T$ R* ]; _) S* y
// 插入哈希表
8 R8 s5 X4 p* @Status InsertHash(HashTable &H, KeyType key)
' g8 t3 @8 @' b{
& l8 Q/ z1 `( \7 c4 A, q) M' U2 ~        int p, c;
        if (UNSUCCESS == SearchHash(H, key, p, c))
7 r) Z! H' D( X& x        { //没有相同key
' X" `) L/ g! N* A0 y) R9 `: K                if (c*1.0 / H.size < 0.5)
; ?1 U; C9 {3 m7 c- |* ]                { //冲突次数未达到上线
                        //插入代码
                        H.rcd[p].key = key;
0 p0 g  Q# k' F% f; H5 Q                        H.tag[p] = 1;
                        H.count++;
                        return SUCCESS;
: @5 ?2 f& L' b6 L+ o                }
( |2 {- w0 {1 |, h" x                else recreateHash(H); //重构哈希表
        }
" F; ]6 M! A+ V& ], ?1 q        return UNSUCCESS;
& H$ P1 Z/ f! w' v3 R}
, S) g+ a3 \  U# V2 e6 d
// 删除哈希表
Status DeleteHash(HashTable &H, KeyType key)
{
( G& i0 w% X. n+ q1 M        int p, c;
( y9 b! ?; z! S6 S4 F" H' h: S        if (SUCCESS == SearchHash(H, key, p, c))
        {
* F) a4 I2 k4 h3 \                //删除代码
& q5 @2 f  R! A! b+ b                H.tag[p] = -1;
                H.count--;
                return SUCCESS;
        }
# @' }# G0 W, ?* p        else return UNSUCCESS;
}
# C: J- k$ F0 o  ]* S/ o
: D6 O" r& t. Aint main()
6 D9 K0 S% k; a4 y% j: Q{
* C9 a3 {9 k% U' K        printf("-----哈希表-----\n");
) u  ]% _3 C5 }5 D! B3 t2 M        HashTable H;
' Y5 Q, \5 p% X  T; B        int i;
        int size = 11;
        KeyType array[8] = { 22, 41, 53, 46, 30, 13, 12, 67 };
- j5 t" x0 E# t( w. M! q        KeyType key;
' M! H7 Q$ m2 U' V
        //初始化哈希表
. A9 U' H' `; h8 }& D1 T5 ?        printf("初始化哈希表\n");
        if (SUCCESS == InitHashTable(H, hashsize[index++])) printf("初始化成功\n");
7 i2 I8 g2 F. S9 Y$ L5 M4 s
8 c) s0 U5 D% u8 }3 ^6 K        //插入哈希表
        printf("插入哈希表\n");
        for (i = 0; i <= 7; i++)
        {
                key = array;
                InsertHash(H, key);
! Y3 _3 O& U/ O3 M" I2 |                printHash(H);
        }

        //删除哈希表
        printf("删除哈希表中key为12的元素\n");
        int p, c;
1 k6 r, g; @' ]- d6 V$ W/ q        if (SUCCESS == DeleteHash(H, 12))
0 {  l9 G! z2 O; z4 n  Y: ]0 X' {        {
5 r9 g( r5 i- ~. ]; v9 \                printf("删除成功，此时哈希表为：\n");
                printHash(H);
        }

) m, D* I7 L: I        //查询哈希表
% D1 t1 p. S- d/ g3 c        printf("查询哈希表中key为67的元素\n");
& ]# ~+ _: q2 K5 c: ?        if (SUCCESS == SearchHash(H, 67, p, c)) printf("查询成功\n");

        //再次插入，测试哈希表的重建
, D7 K! u$ |9 \& U8 c        printf("再次插入，测试哈希表的重建：\n");
        KeyType array1[8] = { 27, 47, 57, 47, 37, 17, 93, 67 };
5 M" ?- _0 Y/ B        for (i = 0; i <= 7; i++)
        {
% v, g: K3 G1 j+ n! C6 j8 _( {' ]                key = array1;
+ h2 s& ]1 a$ ?- u                InsertHash(H, key);
                printHash(H);
        }
4 P; o0 D4 W' s6 a
& z) b% _$ A, Y; b! n) \        getchar();
        return 0;
$ H6 h# a5 i6 q  \! N8 I8 V}
6 二叉树查找

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

算法思路：

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

代码：

递归和非递归

//非递归查找算法
% t& a7 p% O8 y4 w* g) O( yBSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p)
# m! m% Q0 I" u6 ?+ ^$ L$ K' F0 U{
! q3 F+ R7 k% p3 R+ H5 J4 {    //查找函数返回指向关键字值为key的结点指针，不存在则返回NULL
1 m! a/ x! S* u7 i    p=NULL;
    while(T!=NULL&&key!=T->data)
& {4 V. f  d/ ~# W    {
        p=T;                          //指向被查找结点的双亲
4 q  x& s1 W& A1 X/ u  P4 S        if(key<T->data)
            T=T->lchild;              //查找左子树
: B3 {8 _+ u/ W        else
            T=T->rchild;              //查找右子树
) \! b/ \, C; X5 M* \; j" P; D    }
6 C6 ?" E$ f( a1 L" s" u5 m4 E    return T;
; V2 M, w9 Q9 f+ @}

//递归算法
* Q9 ]) }2 B  Q% n8 h! v% y/ [Status Search_BST(BiTree T, int key, BiTree f, BiTree *p)
4 }! y/ e' c% T, s{
; s8 ~$ B9 h9 n$ k% I7 v    //查找BST中是否存在key，f指向T双亲，其初始值为NULL
+ [+ g6 K8 n3 }    //若查找成功，指针p指向数据元素结点，返回true；
' e2 v. C; u( d* H8 U  p    //若失败，p指向查找路径上访问的最后一个结点并返回false
    if(!T)
    {
0 C! y7 }* _) J. G1 N+ E        *p=f;
        return false;
$ n4 S( n6 }! f( ]: O  [# E    }
    else if(key==T->data)
+ y+ \7 k! k  w( x8 n7 [! K    {                      //查找成功
; }6 G; w$ D2 k; ^! G3 d% B* }        *p=T;
        return true;
) N/ N1 Z- h+ @' I' p    }
" x/ v4 A2 M4 ~# j' q7 B$ R    else if(key<T->data)
        return Search_BST(T->lchild,key,T,p);   //递归查找左子树
    else
, \+ e1 M0 ]& I        return Search_BST(T->rchild,key,T,p);   //递归查找右子树
$ W$ A" \5 Z$ N$ G2 w1 o8 I   
}

7 2-3树

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

• 要么为空，要么：

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

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

  
  4 T2 T) A! d# g" C' D$ _

算法思路:

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

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

代码：

two_three *search23(two_three *t, element x)
{
: D" }' W, n( P) t  t9 Z7 R6 M  o+ O9 G    while(t)
& L$ r  D6 D5 [    {
! W' u- L  ]! `  @& O$ A        if (x < t->data_l)
        {
            t = t->left_child;
3 R# m% p6 B* @* t: w9 m# |        }
        else if (x > t->data_l && x < t->data_r)
        {
, O5 R" W8 v9 b% M" F+ u, B% q$ _            t = t->middle_child;
' x5 J- ]9 R+ m, \        }
" ^. S3 o/ n7 e8 U7 J' f        else if (x > t->data_r)
9 A  z6 _$ S2 |) L& z& n! z+ I        {
0 q3 C1 Z9 R, u: W& _            t = t->right_child;
        }
        else
        {
            return t;
1 Z% g- S3 c" M, U& z        }
# N- Z  Z. J" k+ A$ P' {    }
" b8 R- H8 T. h. Z- K# b    return NULL;
4 X6 a) x7 E6 v, {}
9 i+ H+ O1 _4 g8 红黑树

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

为什么使用红黑树：

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

红黑树性质：

• 每个节点要么是黑色，要么是红色。
• 根节点是黑色。
• 每个叶子节点（NIL）是黑色。
• 每个红色结点的两个子结点一定都是黑色。
• 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
  ( K/ a9 O! ^; e# [

算法思路：

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

代码：

#define BLACK 1
5 {5 a8 B5 S" n. c6 [0 I# V1 r  S#define RED 0
: l; q8 l) Z( L0 R* V& [0 ]2 @#include <iostream>

using namespace std;

class bst
2 v" m" n8 q7 @( b9 r' H" C{
0 [. B( z( j( n5 u# \2 e% Mprivate:

        struct Node
$ d% k3 n+ ?3 J        {
7 B3 ]$ |3 K, P& S                int value;
                bool color;
                Node *leftTree, *rightTree, *parent;

                Node() : value(0), color(RED), leftTree(NULL), rightTree(NULL), parent(NULL) { }

                Node* grandparent()
. `" S" n: n, J                {
' z5 R/ r* _! a2 t/ h+ c. |  X                        if (parent == NULL)
                        {
                                return NULL;
                        }
$ m6 @' c0 c( y8 c  I% w                        return parent->parent;
                }
4 t6 Y/ S7 V+ ?
                Node* uncle()
                {
                        if (grandparent() == NULL)
) D/ j+ q* S6 _+ O4 ?                        {
2 r$ c  J" g3 G  H- B                                return NULL;
                        }
                        if (parent == grandparent()->rightTree)
                                return grandparent()->leftTree;
& R! E% g3 e3 s8 G                        else
+ g3 U' M) \/ k) q5 z* [1 Y. d& H                                return grandparent()->rightTree;
7 X$ }2 b& |' f9 X7 q  s7 j1 t- v                }

9 c1 i8 e8 e4 F  o( M% l                Node* sibling()
5 ?7 ~% @& O% P8 R2 _$ T0 j                {
1 ~; a; S4 @7 y; d" H9 Y, {                        if (parent->leftTree == this)
                                return parent->rightTree;
3 J5 h2 R5 j7 Y- a6 t8 q3 X$ f9 m% w                        else
                                return parent->leftTree;
) l* @1 p0 g# e0 _                }
8 l+ J( g1 `( d) `. K) r        };

7 g# q1 ]. r- \( b+ o        void rotate_right(Node *p)
        {
                Node *gp = p->grandparent();
2 Q& Y( B3 M. R, u: h                Node *fa = p->parent;
                Node *y = p->rightTree;
8 p5 A6 X; I' e& P1 }1 a
                fa->leftTree = y;

                if (y != NIL)
9 a9 `4 H/ L5 E  R! m: f                        y->parent = fa;
; j/ i9 R+ k5 [5 m$ M# Y                p->rightTree = fa;
                fa->parent = p;

                if (root == fa)
6 |* K5 C+ _2 Q& Q7 o2 w4 n                        root = p;
                p->parent = gp;

4 L$ U: f" d8 Z* R% P                if (gp != NULL)
1 d' ^2 b, O$ x5 V  R                {
9 {$ p: m# o3 Z7 ~$ l3 L$ h& a, l                        if (gp->leftTree == fa)
                                gp->leftTree = p;
                        else
3 Y6 b( V1 k0 G' g                                gp->rightTree = p;
, @9 |: U6 B: N                }

        }

6 m! w3 Z* V6 Q7 Z, [' l        void rotate_left(Node *p)
' ^. b/ U$ }3 D8 r3 M& A        {
; b! |3 H; v8 \2 `                if (p->parent == NULL)
                {
                        root = p;
6 G0 |/ Z' E$ J1 A: C                        return;
7 }8 }# A% B2 m5 I( l3 G+ [                }
9 @2 o" t1 U% Q+ }% j. k                Node *gp = p->grandparent();
4 O6 u6 d* }7 I/ F# o. y9 a$ f3 A                Node *fa = p->parent;
                Node *y = p->leftTree;
; t+ g  I' Z1 V4 J2 ~" j
5 ?) x8 j; r5 O) d. f. |                fa->rightTree = y;
, L. }* H. p* u% v: i4 V
! U. J; m" _: I; c! [$ r                if (y != NIL)
                        y->parent = fa;
1 Y) P2 [5 M# c& h9 n+ Y                p->leftTree = fa;
                fa->parent = p;

* \9 \1 y) v5 T) @2 z* e8 d8 m                if (root == fa)
$ a7 K# H% _5 Y- O3 }                        root = p;
! p2 W' u/ A1 x. l; M& r" K                p->parent = gp;

  d/ R/ m$ G/ b# W; i                if (gp != NULL)
                {
  `8 k: g+ |( O9 J, h8 ^                        if (gp->leftTree == fa)
                                gp->leftTree = p;
                        else
                                gp->rightTree = p;
- ~0 B% m3 I: Q; n& }* g                }
        }
; O* Z/ x/ e  z6 b5 \2 [1 L
        void inorder(Node *p)
        {
) Q: D7 t7 e/ v4 o                if (p == NIL)
                        return;
4 p. A  d7 L7 Y6 w
6 R; }, E) C: i! r1 h                if (p->leftTree)
                        inorder(p->leftTree);

                cout << p->value << " ";

' I/ c3 u$ V, f5 o9 \2 w1 ~; t                if (p->rightTree)
                        inorder(p->rightTree);
        }

        string outputColor(bool color)
# P4 O6 I& d. R3 |( J        {
                return color ? "BLACK" : "RED";
        }
" w9 ~% r! `; S/ H$ l
        Node* getSmallestChild(Node *p)
        {
- o5 P( k7 S* \8 P( ?5 y' J6 \                if (p->leftTree == NIL)
                        return p;
' ^9 o6 v/ Z$ ?& L6 g; Y  R% o                return getSmallestChild(p->leftTree);
        }
9 M: R# v' l: w. m2 q! D
        bool delete_child(Node *p, int data)
        {
& Z& w9 w" [( x, w                if (p->value > data)
$ m8 i1 C9 J- A# W  M" E* w; D/ b                {
/ _; N3 q* y/ u; ?' _5 |3 C9 [                        if (p->leftTree == NIL)
4 g# l' E! P' S                        {
                                return false;
4 N" \2 k# K9 z: [* W                        }
) ~; L0 M# E; E3 \# }2 |; r                        return delete_child(p->leftTree, data);
# Q) Z3 q8 [7 T  M% V" }5 I                }
                else if (p->value < data)
/ n0 D" I* {' {! g) l% e                {
                        if (p->rightTree == NIL)
: q  V5 ]5 L% @. W9 E6 Q3 }                        {
8 h& i1 W2 U& P! z. p                                return false;
                        }
                        return delete_child(p->rightTree, data);
                }
                else if (p->value == data)
) q1 t" \4 b! o/ H                {
( y! H$ W" G+ X0 ?4 c8 u                        if (p->rightTree == NIL)
' ]' @3 l7 G7 M( P! |- i2 }                        {
                                delete_one_child(p);
                                return true;
                        }
& f) Q  n9 O/ g( `1 ?                        Node *smallest = getSmallestChild(p->rightTree);
                        swap(p->value, smallest->value);
" P! w* I7 A: a5 x% l                        delete_one_child(smallest);

5 Q6 K- p0 Y+ ~& {9 e; \                        return true;
                }
: e) x. Y- Y+ v0 Z" ~( a                else
/ x/ ^" ]) |: ^* C                {
                        return false;
                }
        }

        void delete_one_child(Node *p)
- N! n3 k! T6 p, V% Y: X        {
                Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
                if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL)
8 Z! u- J. m$ Q6 F1 F$ F                {
; z3 `" J# m) }( V  z                        p = NULL;
6 q. Y: N& E0 M9 r                        root = p;
" p6 o5 \' Q" C5 w1 I                        return;
" s0 z1 K# @( O* b5 Y                }

                if (p->parent == NULL)
                {
                        delete  p;
                        child->parent = NULL;
                        root = child;
# C4 \" G* s; t+ Q; z0 i, R- ~/ O                        root->color = BLACK;
                        return;
. d& C' t4 d6 s5 l+ H/ E1 l                }

                if (p->parent->leftTree == p)
                {
                        p->parent->leftTree = child;
) g! B4 a8 Z$ r) Q                }
                else
% G4 s, f6 i; ]                {
                        p->parent->rightTree = child;
                }
                child->parent = p->parent;

                if (p->color == BLACK)
; Z8 g1 |4 x7 @6 x                {
                        if (child->color == RED)
, f/ N; ]9 R0 n. b- \4 o4 b                        {
                                child->color = BLACK;
) U( y/ z! `6 T1 c" u                        }
& x# x, P  P  X& g# W0 A% d                        else
                                delete_case(child);
. Q; \  ~1 p# |* K( |6 {0 @3 b4 q                }

& x7 G# {! o. N+ q0 N5 X                delete p;
, T! ^2 u2 X% m& y  c1 m        }

/ ?* k2 Q& b% _# B0 Z9 b' `; Q        void delete_case(Node *p)
        {
- }5 W3 D' k! }2 t                if (p->parent == NULL)
1 b# C1 L" N7 O$ i  u8 Q) p  q                {
$ i, v) i& i, \5 D/ s                        p->color = BLACK;
) ^6 T4 I5 B5 F$ k# E* _/ ^                        return;
                }
                if (p->sibling()->color == RED)
                {
0 y- E! o) w) k* _+ a7 Y- `                        p->parent->color = RED;
                        p->sibling()->color = BLACK;
                        if (p == p->parent->leftTree)
# k6 u0 C. N3 x4 a                                rotate_left(p->sibling());
                        else
) V. C/ m, p9 U                                rotate_right(p->sibling());
" O  F5 U0 T: T9 Y' m+ n5 M! y* z1 D                }
2 Q% \/ P0 {# ~, r0 M. r- r                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
, b3 v7 x$ _, b! i+ C' k# o8 C4 V7 K- S                        && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK)
' M( `) [1 c( {( B/ x                {
& V$ K6 N1 s8 D" Y' E3 C                        p->sibling()->color = RED;
                        p->parent->color = BLACK;
. f9 m4 d/ i# u. A                }
( K- k; n8 H& d                else
4 A0 X6 D2 @- }                {
                        if (p->sibling()->color == BLACK)
                        {
                                if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED
7 Q( ?* L5 b! T  q& y& K2 I; ?" M                                        && p->sibling()->rightTree->color == BLACK)
7 R: @( ]* K* p                                {
- ?# s. f8 j/ o. H- z" e; c/ n                                        p->sibling()->color = RED;
                                        p->sibling()->leftTree->color = BLACK;
4 _' d7 H- F3 L                                        rotate_right(p->sibling()->leftTree);
                                }
                                else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
( `. ], @& w6 l9 u$ G0 R                                        && p->sibling()->rightTree->color == RED)
$ {! ~. W8 W+ O- D2 [                                {
. P7 D& h. x6 y- K: t. p                                        p->sibling()->color = RED;
" e8 \5 z5 r/ w  n3 m  [                                        p->sibling()->rightTree->color = BLACK;
( O, C* c5 u( Q$ J0 x3 Z                                        rotate_left(p->sibling()->rightTree);
                                }
                        }
                        p->sibling()->color = p->parent->color;
7 y* t8 v& L( w( W                        p->parent->color = BLACK;
: q4 {; ?* {/ A& n; n                        if (p == p->parent->leftTree)
! w! Y. m4 [0 [2 Y                        {
                                p->sibling()->rightTree->color = BLACK;
                                rotate_left(p->sibling());
                        }
, s' G. D9 U3 V1 G9 Z                        else
                        {
# t( l; T, K6 N# W4 h                                p->sibling()->leftTree->color = BLACK;
/ g8 ~0 S1 @, w9 L$ L( H" @7 M                                rotate_right(p->sibling());
3 ]* ?& I1 B0 k0 z$ Z0 ]# @- ~                        }
; v# n! J. ], f9 H' ~/ m8 J" Z. t0 O* e                }
. H7 P3 g, u: ^: c2 b) b        }

! Z8 b" a8 q! Y& @' R5 C        void insert(Node *p, int data)
        {
6 A  |8 j8 q' I                if (p->value >= data)
                {
                        if (p->leftTree != NIL)
; ?5 [7 B/ B+ m+ `                                insert(p->leftTree, data);
                        else
# e+ q8 F) y9 i, {( T" Q; t                        {
) [8 B) A! b/ i7 ^                                Node *tmp = new Node();
                                tmp->value = data;
                                tmp->leftTree = tmp->rightTree = NIL;
                                tmp->parent = p;
                                p->leftTree = tmp;
. F% z6 X; R" R9 J: j; S                                insert_case(tmp);
                        }
0 ?, h, P3 x1 M/ t                }
& Y2 S0 ]% |) X& i& t5 F                else
3 O& [" P) M# G0 K& J5 \6 V                {
                        if (p->rightTree != NIL)
/ t/ m) H4 P6 K                                insert(p->rightTree, data);
' I1 }1 y. t- u% p9 ?, r" X                        else
  V, u' O; S- O% f! _                        {
0 q5 [5 U7 l1 ]6 L( [& X7 G) }                                Node *tmp = new Node();
( d6 n4 r1 ^# f2 u: s                                tmp->value = data;
                                tmp->leftTree = tmp->rightTree = NIL;
: d/ X5 Q0 w, Q7 x7 @, M                                tmp->parent = p;
; G8 S; T* u/ c! f$ m                                p->rightTree = tmp;
5 l5 i3 x  l$ G4 l  J, o0 `7 G                                insert_case(tmp);
3 \2 B2 R) O, x1 R                        }
; K, d& `) v0 K- k                }
        }

! |% a/ F' ^4 t1 H( V. K$ X        void insert_case(Node *p)
        {
                if (p->parent == NULL)
% W9 k% I9 y2 V* M                {
* L* U: U" N8 C  Q2 o3 C# }                        root = p;
                        p->color = BLACK;
                        return;
                }
                if (p->parent->color == RED)
" c$ p8 g2 G; p; G- k                {
. B" q+ d/ `+ `; P8 k                        if (p->uncle()->color == RED)
: j9 ~4 X- N6 C                        {
                                p->parent->color = p->uncle()->color = BLACK;
2 C$ m5 v2 @& c+ I* b* L                                p->grandparent()->color = RED;
                                insert_case(p->grandparent());
9 [  J, v3 r& W5 ^) a8 Y                        }
                        else
. I+ [+ ]+ }& w% E/ v7 L3 `                        {
                                if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent)
                                {
                                        rotate_left(p);
& D: _$ _/ ?; r+ Y                                        rotate_right(p);
* W8 a: L: y" P$ H! Z( u                                        p->color = BLACK;
: C! j; `( v( _* z                                        p->leftTree->color = p->rightTree->color = RED;
                                }
! w$ \  d" d8 |  I' ?% w                                else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent)
                                {
                                        rotate_right(p);
                                        rotate_left(p);
9 l0 Z- m% {* p4 l0 j# V                                        p->color = BLACK;
0 d9 ]8 {7 S# M. y; C; d% u. z                                        p->leftTree->color = p->rightTree->color = RED;
                                }
5 J. ?; Z: M2 B* u3 F! M8 \! l                                else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent)
; K3 D. h, M  u9 k+ B# f                                {
                                        p->parent->color = BLACK;
% o( k5 f2 g2 }+ r2 y9 X! E4 K# S. V                                        p->grandparent()->color = RED;
                                        rotate_right(p->parent);
2 R* x! R1 ?, f: a- t4 n. m                                }
% A2 i7 Q9 ?- L2 x1 H; y% d1 i                                else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent)
6 F; f! S! P0 b' p3 p5 Z# \+ V9 c                                {
                                        p->parent->color = BLACK;
. |% T/ i/ v- X                                        p->grandparent()->color = RED;
                                        rotate_left(p->parent);
                                }
                        }
. [- W$ b2 L6 f' L# P6 R  t. c7 |                }
0 ~& w! Z3 f, a8 O. ?- K        }
/ _2 b6 M6 V' y5 J
) O8 f# K3 y  D6 V7 Y6 V        void DeleteTree(Node *p)
        {
                if (!p || p == NIL)
, v. h9 A& N' K. g3 q) ^' \                {
                        return;
  s/ W4 U# {3 S+ B7 c1 f                }
: j+ f( q/ ^+ l3 y6 K- ?$ a' U% I6 _                DeleteTree(p->leftTree);
* H7 g" k( v' H% N$ b  i8 C5 g5 r8 E0 s                DeleteTree(p->rightTree);
                delete p;
# Q3 g) \: R! l2 O: z  {! ^+ Q        }
; l% ^( Q; v, S2 ?  Kpublic:
( E4 j0 r6 N" I- ~, G
        bst()
        {
  Q* B4 L; U; l7 B2 m- s                NIL = new Node();
                NIL->color = BLACK;
                root = NULL;
        }

* w. l6 i* U) D+ V; X6 F        ~bst()
8 ~5 G9 a# K: k7 Y3 ^9 S; a        {
                if (root)
                        DeleteTree(root);
                delete NIL;
        }
, x; O5 T! T6 R3 N
        void inorder()
        {
" `8 c4 s  @2 U1 U5 h5 R3 f                if (root == NULL)
                        return;
                inorder(root);
                cout << endl;
8 {5 [8 y$ F  b, U+ P# P5 x        }

        void insert(int x)
        {
                if (root == NULL)
                {
                        root = new Node();
                        root->color = BLACK;
! O6 \5 J/ f% v3 _3 ~7 G                        root->leftTree = root->rightTree = NIL;
                        root->value = x;
/ i& {' t. R2 o                }
( y, D3 g# v5 o% J0 E& j, }5 d                else
6 G  k. v) B  F4 _4 p* t" w                {
0 p) c# o: W' Q# w5 m                        insert(root, x);
% |+ y, W" D/ R$ h7 J' K% I                }
" ~, \$ k4 C0 \7 ]        }
/ p. O3 I) _( E+ ~8 [7 L" }- r
5 J4 N6 |0 a' I- _        bool delete_value(int data)
' T: I% K- Z8 H        {
7 ~0 D9 S9 C, F. J0 ?  \( \1 `! G/ A                return delete_child(root, data);
3 G3 y3 ^: W) X  D9 q6 X        }
private:
        Node *root, *NIL;
, U" y8 x0 t3 ?2 M2 j3 z" ?};
2 |: c3 d& Q* |* n( w& C0 C
int main()
{
        cout << "---【红黑树】---" << endl;
' O' c" E' p& T        // 创建红黑树
" G1 k5 k8 C" H! S" f. a6 |! ^        bst tree;
! r3 E5 i2 j& |7 W" K" G! P
        // 插入元素
. _9 Q4 u% i9 T: U+ ]1 D        tree.insert(2);
  G$ H- z9 B2 i        tree.insert(9);
8 w* {1 y, p7 j) {' @; ]        tree.insert(-10);
0 ]- h) Y( X* w+ a- N# c        tree.insert(0);
        tree.insert(33);
- f# e/ ]" `! ]* s" c' E        tree.insert(-19);

        // 顺序打印红黑树
4 s+ T2 V: I/ t  _0 T2 y        cout << "插入元素后的红黑树：" << endl;
" Q( a5 ^, M/ n) K        tree.inorder();

5 |; N, C( @* k3 r7 x( g        // 删除元素
        tree.delete_value(2);
# o7 f& H9 n- W2 J5 I
        // 顺序打印红黑树
9 m0 W3 M/ |. ^        cout << "删除元素 2 后的红黑树：" << endl;
; j. X9 e/ y5 m/ t  J- l1 m4 |! k( l        tree.inorder();
7 K* k7 H3 r( a: u+ k
        // 析构
1 f; N4 K% p5 d4 u) @        tree.~bst();

        getchar();
2 d6 Q+ {: M" g# P, ]        return 0;
2 V4 v; u) K" |' X% ~2 T}
9 B树/B+树

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

                             ——维基百科
% Z7 r4 f0 d9 y  e; F9 j& H

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 < K[i+1]；
• 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的 子树，P[M]指向关键字大于K[M-1]的子树，其它P指向关键字属于(K[i-1], K)的子树；
• 所有叶子结点位于同一层；
  
  ) h( ?& ]- y$ `/ T# B. ]% R

如：（M=3）

算法思路：

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

• 关键字集合分布在整颗树中；
• 任何一个关键字出现且只出现在一个结点中；
• 搜索有可能在非叶子结点结束；
• 其搜索性能等价于在关键字全集内做一次二分查找；
• 自动层次控制；
  % C: Z* g/ R# b0 \' n
  

代码：

BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)
+ j* Y7 x6 g) a5 S' l9 |3 |{
    int i = 0;
& v4 `% U; J% V' C4 I% f( U    while (i < tree->keynum && key > tree->key)
, C9 S& ^( ?: }4 J- G0 B  o    {
        ++i;
3 l+ l9 ]. O* X3 b8 |' x" _) |  B    }
   
+ s- h1 A  E! h    // 查找关键字
    if (i < tree->keynum && tree->key == key)
& A: s; o+ G* @6 M! n7 j    {
) ^: ?- U* A8 [: G" g  P. a1 b" E        *pos = i;
        return tree;
* G7 A* n3 r5 C5 e1 X+ z    }
   
    // tree 为叶子节点，找不到 key，查找失败返回
' b, g7 @6 [+ `- Y6 p  S    if (tree->isLeaf)
8 N; s: @3 L9 W5 i) P! I    {
. ^  F3 s; J8 V  ]+ Z. n* M        return NULL;
4 ~3 H0 B" @- b" L$ u7 s    }
   
  F# W* w6 l5 S3 b4 F# c' Y    // 节点内查找失败，但 tree->key[i - 1]< key < tree->key，
$ L! w( I1 K- W+ v2 ~9 ~6 Y    // 下一个查找的结点应为 child
: a0 K% O1 H7 j   
0 [' b+ s7 ^0 d& z    // 从磁盘读取第 i 个孩子的数据
6 r5 v4 g" V6 G3 [4 O    disk_read(&tree->child);
8 Z$ T6 X) [5 K   
    // 递归地继续查找于树 tree->child
    return BTree_recursive_search(tree->child, key, pos);
}
& @* z9 x/ g( Y( X( b

B+树：

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

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

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

如:（M=3）

1

算法思路：

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

• 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
• 不可能在非叶子结点命中；
• 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
• 更适合文件索引系统；
  , r, P1 v* \8 |/ Z5 c/ m% H) |

很强大