C语言编程的九种查找算法

[复制链接]

gaosmile 发布时间：2020-5-29 11:41

技术帖
文章封面:	-
文章简介:	-

时间、空间复杂度比较

查找算法	平均时间复杂度	空间复杂度	查找条件
顺序查找	O(n)	O(1)	无序或有序
二分查找（折半查找）	O(log2n)	O(1)	有序
插值查找	O(log2(log2n))	O(1)	有序
斐波那契查找	O(log2n)	O(1)	有序
哈希查找	O(1)	O(n)	无序或有序
二叉查找树（二叉搜索树查找）	O(log2n)	/ R9 g8 ?! Z% _1 T	$ z M% a# a g+ p( c" y7 }
红黑树	O(log2n)	, ~7 ~. h) C+ ?	4 I5 b4 v# B3 Y3 \. F
2-3树	O(log2n - log3n)	: {3 R* R: B* f	; D/ q! q& I! O( b3 J1 J4 T" ~
B树/B+树	O(log2n)	8 \, r5 d' O E# d+ K6 W	+ x; }3 W8 l d- B

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.key));
, Z6 |# N$ D, L% q       }3 |- u$ ]  w9 ~' ~$ _) C! V* l9 Q
}
1 S) F+ x6 @* i9 s  |5 f  U1 m& S2 a9 A  T/ N
//顺序查找函数，其中key为要查找的元素" O- u* A- o4 s5 E# ]! Q
int Search_seq(SSTable *str,keyType key)
- z2 h; y! i9 r  u' |6 r0 t3 J6 d- X{
+ x" O. S. U# [% ~( h       //str->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置，起监视哨的作用) G! k- Q: S. d8 F  v
      int len = str->length;. d1 e* {- I( X1 @( C% i
      //从最后一个数据元素依次遍历，一直遍历到数组下标为0% ^/ I3 V4 o  r. V. T8 J
      for(int i=1; i<len+1; i++) //创建数据从数组下标为1开始，查询也从1开始6 C0 \! [+ H5 y! _) s2 j
      {( p( u5 Z% \# V; b- _, p1 V( L
            if(str->elem.key == key), ?. H$ k7 G6 S  |; j
            {
- \) l# M+ ~9 g! ?                      return i;
& t; i% X9 k  [, @# C: D: w             }8 ^0 \7 }( N* i! \. g( A0 D0 Q" t, \
      }
! Z8 F5 F7 C6 y/ w# a3 k  w% v, V       //如果 i=0，说明查找失败；查找成功返回要查找元素key的位置i
$ o; m! c6 s; d& h1 Y" F/ Q& r! S# V( c       return 0;
2 J; }- |( V0 B0 D, z8 P, B}
( v. K3 f3 O! {* [+ t
( u# t" s2 g" B: D& [, R/ Aint main()
$ C, z! [& m/ Z- Z6 y6 g( E{
! Y" s& Q* @- D( r       SSTable *str;
5 U3 {( f9 B2 @0 b+ d       int num;- F% T1 n3 J0 K  o, f
      printf("请输入创建数据元素的个数：\n");1 B: F4 z1 r5 }6 N6 M
      scanf("%d",&num);3 o$ v% x, k8 J" z
      Create(&str, num);0 p; a4 D  ]* p2 L
      getchar();) W3 \# p$ c) E1 p0 \
      printf("请输入要查找的数据：\n");
2 D: \1 _( g! K. F8 r% k       int key;$ E* E) M, R9 ~' ^
      scanf("%d",&key);" T$ n4 r% ^& H/ T, }% Z  U/ S
      int location=Search_seq(str, key);8 O5 w0 X( ^; ~9 C- F; G
      if (location==0) {
, h' M' W6 K! _             printf("查找失败");& D3 E6 L4 Z  r) d3 y9 b5 R
      }else{
6 i' m4 C/ G3 R& Y             printf("要查找的%d的顺序为：%d",key,location);
" a0 e3 n' g! N- b; v7 }       }
, Z5 S7 F4 V- t3 j. M" ~) x& L       return 0;: t3 `1 {+ r- t
}
9 e* c5 i! o# m! G' r3 h2 j/ s
运行结果：

7 _2 D$ s) w. |8 Y# V4 j查找成功  [1 ?! S% z( w5 T  g

0 S7 d: @& v3 s$ _* H" ?$ T6 k% W0 K查找失败& @% w% F) ?- ^3 a8 V5 z) k
6 j: k  K# |8 H  S: W! C/ i
6 e3 e. ?7 S* w/ C% u( F
2 二分查找（折半查找）, o  [5 L9 Y6 O% g; f

算法思路：
确定查找范围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。
9 V: Y9 G0 O& q% X

说明：
查找元素必须是有序的，如果是无序的则要先进行排序操作。
在做查找的过程中，如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。
- {3 ]! E  W- e0 T; P5 P: G% O; E

折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。
                     ——《大话数据结构》
3 K( x5 w( q$ Q' L
代码：
#include <stdio.h>& y* P% W( @: c' ]& P3 H
#include <stdlib.h>
3 M( s" S5 ~9 ^5 D- X#define keyType int
: l0 A% Z7 I4 z- g( ]/ x& rtypedef struct3 W1 h# C  w" L+ x" w6 D
{* u) u% ]4 n" {0 f  Y& o
      keyType key;//查找表中每个数据元素的值$ ^9 R$ R/ o& K- i% n5 A
}ElemType;
# z+ B  R# P5 O% B7 L1 e" S  L
4 y' y: [( @7 Y, W! o% g4 qtypedef struct
1 Q2 B$ f+ t7 f: d8 D{
2 @1 d! P% B; \' e9 {) n       ElemType *elem;//存放查找表中数据元素的数组, O8 Q! F2 V: m5 n; r2 T
      int length;//记录查找表中数据的总数量; e  Y* f. K0 l+ k$ N5 Y
}SSTable;4 Z) p0 |7 G7 O, E/ m  o

& i  l& @# M- }//创建查询数据; f' ^/ W' a9 R" C- f4 r- m
void Create(SSTable **st,int length)
6 r% b. y( G+ i{
1 P/ Q! C% g2 q! E       (*st)=(SSTable*)malloc(sizeof(SSTable));* {$ q( p! f% j% b9 k
      (*st)->length=length;0 h( H: ?! b; H. b* |3 I
      (*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));! ]! ?- |7 f. q- x' f7 W6 ^9 x
      printf("输入表中的数据元素：\n");- I1 `+ l4 s  A/ b1 x& W
      //根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据
& |/ d* s9 _/ d" ?3 J3 w; G       for (int i=1; i<=length; i++)- z# r5 [+ N' t) h( B2 x! H6 [5 e
      {! T; P# N% l3 v9 L
            scanf("%d",&((*st)->elem.key));
: y: t# z; t; l; m5 V- _+ E0 P9 }       }
/ x; a% \5 ]4 y8 w% u8 X}# r9 ?' I$ F  I

; J3 i9 s' i/ B& x: A! ], K1 C//折半查找函数 key为要查找的元素
$ T( S7 L# Q! {- Y# fint Search_Bin(SSTable *str,keyType key)
* u. ~% @2 B) e  O5 v{+ s' H9 }3 I5 u( I9 C$ Q/ j2 G$ ^4 b
      int low=1;//初始状态 low 指针指向第一个关键字2 ~6 h1 R+ N6 m) ]' w  @6 }. N
      int high=str->length;//high 指向最后一个关键字4 R/ o0 ~3 t/ r: r
      int mid;
6 E4 Y  i: Y, B7 `$ ]0 C2 G       while (low<=high)$ ?  Z" ~. L" ~5 W1 d
      {
, m' f( y& y" P  z* z, D# x/ H             mid=(low+high)/2;//int 本身为整形，所以，mid 每次为取整的整数
% m  F' o, F# c; I: v$ B; {, M             if(str->elem[mid].key==key)//如果 mid 指向的同要查找的相等，返回 mid 所指向的位置( z& }$ _: r9 u& P  n: H
            {) [0 f" E% ^) y* }
                     return mid;
- Q8 S. a: i& `# v" o             }
8 h+ A/ U# N7 L; N% E* _9 |: e( N       else if(str->elem[mid].key>key)//如果mid指向的关键字较大，则更新 high 指针的位置
8 Q% {- l& B6 {9 }- x# w             {
) c. H8 t% f' z' q8 f+ c3 u                      high=mid-1;' j! \) l* x& b/ o5 M& C/ m3 b' F
            }8 e) S% O& ^, v
            //反之，则更新 low 指针的位置
0 p8 q9 f( l2 W! U) `( l             else
            {: |2 @: z# E0 @& T; y  E, I9 ?% V
                     low=mid+1;
4 Y. p& T# l; S* }4 C             }5 ?2 k" K  a3 }
      }
6 }) V9 Q& |2 l4 J: [. O       return 0;
  ~. W( [2 X8 ^* w4 R}
' e" M; x# T8 i6 O. c" w
. L/ ^" Z+ F. b7 n1 k& }7 Rint main()5 X- v) `. U1 X
{
; @6 F" X$ o1 I+ n       SSTable *str;
) b5 |5 H- e& K4 S9 O       int num;
7 D0 P# _/ }; q5 x+ u2 o9 j       printf("请输入创建数据元素的个数：\n");
2 g  Q' w! K$ ?       scanf("%d",&num);: G" ?$ e8 ~) P3 T1 _7 {2 h+ n  [, u
      Create(&str, num);
; F) G3 W. o# c; |       getchar();
, `+ T' F/ R' n0 d+ U6 _# g       printf("请输入要查找的数据：\n");
, b! H  G- z# v7 ~* I       int key;
: V. Q, W' r2 d2 G! j       scanf("%d",&key);
# U  Y! F$ y- @7 o) @- \       int location=Search_Bin(str, key);. I! k% E! Q  l+ V+ v
      if (location==0) {) S: w) I; U) [, Z" }$ ^; _
            printf("没有查找到");, e, \9 i- k/ g' ~* f4 K
      }else{
( c: O: n/ @" l4 t             printf("要查找的%d的顺序为：%d",key,location);
% |! ~8 d4 D" d  T6 w       }' \# P0 f+ E- R% z7 W2 u0 ~+ p
      return 0;
7 G3 P' q( M1 O6 S2 q. i( k}3 n- h3 h4 c4 L

运行结果：
) n: K% K- _# U* Y+ X& L+ D
查找成功
$ V6 ^; @6 [+ ^* M- N
5 l9 ~: @  z4 I' z" A没有查找到; E& E& a- g0 A- o. d& S2 t

- R* h. y1 c/ O! \
" M' A  m0 `) m- }4 J& s3 插值查找
  H2 e1 z. w- W' ~
插值查找基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找
算法思路：
确定查找范围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。
; }+ T; |8 b1 a& k5 }. S& i% x

说明：
插值查找是基于折半查找进行了优化的查找方法。
当表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能要比折半查找要好得多。
: [% i! O' G) E
代码：
#include<stdio.h>
: A4 ~' i+ g  H- a
  ~, @# Z8 U) Q9 c1 tint array[10] = { 1, 4, 9, 16, 27, 31, 33, 35, 45, 64 };1 z) K6 |8 h8 R0 [& ?
8 }9 u( l9 i4 k- Z+ k
int InsertionSearch(int data), \- K# p$ _5 P) r
{
, @) \; j+ x2 v+ L' l int low = 0;! Q  s+ K' U8 V  z7 K  W  e0 _
int high = 10 - 1;
! t# Z; F# U$ S# V int mid = -1;6 p; s6 |7 }/ \, {' T7 w
int comparisons = 1;8 ]' j( @; V: I* j4 V9 P+ J
int index = -1;
6 m  d  `" g9 }* ~
& g, Z0 h9 A! F6 @7 f/ C* g while(low <= high)
; F' V9 _& _% C; ~9 u {8 @, j$ y- E& f; Y  y" @
   printf("比较 %d 次\n" , comparisons );3 h1 U! B$ D# q
   printf("low : %d, list[%d] = %d\n", low, low, array[low]);9 |, D/ Y- m& j. q
   printf("high : %d, list[%d] = %d\n", high, high, array[high]);3 c5 S7 e" R$ y9 s+ ~: H4 N  t; }

8 y! y/ j9 |9 r* T# a/ v    comparisons++;
& Z0 E7 B9 ^/ y5 J    mid = low + (((double)(high - low) / (array[high] - array[low])) * (data - array[low]));% j: A7 y( t3 ?; ?' ]
   printf("mid = %d\n",mid);$ }2 |# N( z* ^0 a
   % Y. k4 ]. m/ G* i
   // 没有找到% C2 T3 Q& b$ l9 e3 K! z
   if(array[mid] == data)
# V; R, L: O/ E- _- d    {( l/ k9 t6 F" \' a. U  q5 t8 D
         index = mid;& p* B' ~5 g( J9 z: s/ n/ {( n; A
         break;- g9 B3 b) R& c4 P2 ^
      }
* B9 L6 Z' e; j& M       else+ J% i1 ~) F1 o0 p: J
      {7 {, i& R' p% U% M
         if(array[mid] < data)
0 c- ]1 [+ X! ^, M1 S          {
1 O8 a  }4 A; B+ ]% U  a* z& g             low = mid + 1;
& b; ^  k1 a0 y1 e          }' `+ A5 H4 h  w: i3 X5 ?. h" t! K
         else
; n$ k# P/ N2 n4 g          {+ R7 L% j, r9 C# \
            high = mid - 1;9 T' I6 b! B4 F2 v
         }$ N, z% R$ }, @' x  v% R
      }
$ o/ ~5 i. f; |4 y$ Z    }
# S, N! L9 ?. K$ Q2 f; S0 D7 N
- I2 b7 h" l. A    printf("比较次数: %d\n", --comparisons);& u' Y, [- {! r' [/ O# e
   return index;1 S. S+ m; E2 x$ C- k0 p
}. u$ n+ A% h9 k- ?! Z2 z. L  g

- {1 }( e8 O9 V( l: r" W% e# X; C5 Rint main()5 P2 D/ ?- w. F( |0 v3 j6 Q: y. }
{
1 w: B/ t& A& b# B int location = InsertionSearch(27);  //测试代，查27，可以找到+ N/ x& _, C: t- I. y
if(location != -1)
- h6 O3 Q. Y0 |4 V1 J, { {
- L* }. S  Q* ^* h$ U" M       printf("查找元素顺序为: %d\n" ,(location+1));, a* L  n+ n/ @$ d% _
   }
, R6 b4 K, Q9 N* J3 f! K3 d* ]$ ?    else2 U1 {% B3 u9 i2 v
   {. i* b! h% f9 I' i, t
      printf("没有查找到");
0 [: W1 s* _% f% q. `* G5 J    }
7 o2 i+ X! j0 t    return 0;
5 W/ m) [" P; Y5 u* A) z}* R8 t" W! t3 ]: b5 D2 `

运行结果：
; k. ?; y) V& z5 u. i
运行结果+ Q/ A2 R* K: O- N$ B- t
& M9 A: A' }" q

% {. N( N: e4 }8 B4 斐波那契查找
) G9 b/ d2 E+ s( K( m
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小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。
( J' ^# A% w- H0 J3 @9 p( }

说明：
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"
+ F' [2 V2 U$ n; K* ~' R#include <memory>. s2 T8 L8 N4 B; \1 V
#include  <iostream>" Z! T  _3 `5 A& g% Y! z
using namespace std;' ^, c3 h& Z7 Y9 A- l

0 ^$ A( f9 p' I( p7 `1 C6 J2 Xconst int max_size=20;//斐波那契数组的长度/ V! Z7 y+ i! D2 ]6 I$ \3 O

# p5 f3 r/ W4 o; o) b4 j/*构造一个斐波那契数组*/  _+ I$ C7 A# W1 Q; i- e6 U
void Fibonacci(int * F)
/ P8 `7 F' o2 v: H4 b0 M{
) W- Q* @0 _/ A F[0]=0;
" [0 n* t$ W, A; g4 D. z F[1]=1;. u+ t6 E$ F" B
for(int i=2;i<max_size;++i)! n% [% U* D9 d6 N5 d* X$ _0 J& F
      F=F[i-1]+F[i-2];. O6 y& @. a$ N& ]5 {, r4 x% R
}8 j2 O5 B0 u5 b6 k5 ^0 }$ }# t
+ V( {) w: u% D4 q# ]& b/ q
/*定义斐波那契查找法*/# e0 v+ r4 D3 J' N3 J
int FibonacciSearch(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字0 d6 ?1 I! O! H. F) N1 O
{
* J; f/ |+ a0 a/ f7 w2 b' B& c. _; V  int low=0;
8 W0 q- f# l  j$ L  int high=n-1;" R1 [$ `4 r! q2 N

, [" R) \/ e/ b. T6 f! h4 u  int F[max_size];
" z. b2 |2 U1 A/ z0 {  Fibonacci(F);//构造一个斐波那契数组F. e+ l4 _+ F% I6 l2 r' c0 n* m

1 U% E( \: a8 N5 o  int k=0;2 a, O. c. j1 r$ w2 a
  while(n>F[k]-1)//计算n位于斐波那契数列的位置* ]1 o# Q% Z, B, u
   ++k;
+ v$ }. D0 R$ k9 H
1 G' n) j  A8 I" Y! T! \1 J/ Q  int  * temp;//将数组a扩展到F[k]-1的长度4 m3 G' n! u' p6 b& @
  temp=new int [F[k]-1];
* N( L4 Q4 u2 a4 u. |0 Z: b  memcpy(temp,a,n*sizeof(int));" H- [7 A& d; d4 x# F, m2 n# {" t7 c# Y
, y# e6 Y+ i) s9 f9 |
  for(int i=n;i<F[k]-1;++i)6 [2 B$ Y% b% O. p
   temp=a[n-1];+ v1 g& K( n/ u- v4 l8 r

1 n$ [" Y3 r+ d  J) _6 b4 [  while(low<=high)
* i9 b0 C1 o* z1 `( `# F  {
  Y1 V( s$ a9 j* H) } int mid=low+F[k-1]-1;
; ~' M7 }4 g% J$ a* o$ g0 W if(key<temp[mid])
0 i2 c% ?! F. B9 N1 s {
* l5 Z* p5 c5 z/ B: f( r9 {( t+ j    high=mid-1;
% D7 f$ y- g5 ~4 O9 R    k-=1;. a3 N$ z7 p! O# Z% M" X
}
5 ^+ R" I/ y8 e  m else if(key>temp[mid])4 Z: K; R: W' S) j) ^; e- O
{6 }: w( Z6 @/ ~$ `& t
   low=mid+1;% B: h: I) C1 J- z, K
   k-=2;3 R3 q6 a; Z+ _. n+ h8 t/ d! O
}; T' \0 a" J, g
else
% z/ w1 W* g& z3 v/ f: h {
9 h& e2 R! y( g3 H! l& P    if(mid<n)' V! w- L6 z; h7 f# L
         return mid; //若相等则说明mid即为查找到的位置
7 L' ^- k7 V7 Q; Q5 j0 Z! {    else
( _8 i7 x" v/ `1 P% ^4 Y          return n-1; //若mid>=n则说明是扩展的数值,返回n-1
5 _! r( R' m6 @ }9 U) R/ r* Q: v( N4 q6 p
  }) o8 X, R: Z0 A  g3 d- J
  delete [] temp;0 h3 ^% J6 x! {% [$ e2 D
  return 0;) `9 S7 ]$ F) f; J* B" }% q$ k% z$ j5 z; u
}; ?' A2 l, R( N9 f9 K' M2 V
  `( o3 U( a; M- ~6 s/ J- R
int main()
5 C' l0 c0 O/ }& Z" g0 R{
8 v+ k/ ~8 z! ^ int a[] = {0,1,4,35,47,53,62,78,88,99};
- s4 Z; R0 d6 T$ {7 N int key=47;
. B# k: q* @4 P/ v9 | int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);0 a+ f* E1 Y3 T$ f  p0 N# {
      if(index == 0)$ u3 V, T) {" K& I. g7 H
      {
9 u1 u# k2 `7 W7 D4 @# Q  ^. h$ Z          cout<<"没有找到"<<key;+ j* M; {8 z' ?; O- C" i+ c
      }& Y* Y+ N. a1 R% f
      else5 |9 ?: o2 y" U* q5 R0 m; W( [# f
      {
0 k3 x& O0 N/ d. [    cout<<key<<" 的位置是:"<<index;
4 z' p8 p, J, G5 S% X: y0 t       }; N; r% _) A2 d7 x& z
return 0;
/ s4 \8 ~! H: R}/ J3 P  ?* Y: x6 m6 e

运行结果：
3 y. v- Q. i2 m2 L7 s. x0 J
47的位置为5# {$ k- K2 f5 L) P0 Q6 U

1 n) N" J, Q* ^, Q
$ Q. F% v4 m& G0 {5 哈希查找
8 `4 l4 Y0 h$ Q
哈希表：
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
"直接定址"与"解决冲突"是哈希表的两大特点。
哈希函数：
规则：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。
算法思路：
如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
用给定的哈希函数构造哈希表；
根据选择的冲突处理方法(常见方法：拉链法和线性探测法)解决地址冲突；
在哈希表的基础上执行哈希查找；/ ?9 W( \7 A5 O- n6 x3 k

代码：
#include<stdio.h>" w  B6 S3 M1 J
#include<stdlib.h>
6 B- j* `* l+ g4 P$ }( g# k; e) c5 o, ]7 W/ G" S
#define SUCCESS 1' U' ~! D; _! `! `
#define UNSUCCESS 0& d4 P7 Y% C/ l9 M  ?' E
#define OVERFLOW -1% ?# A% y# i5 k" m8 B
#define OK 1* n  C8 E6 ]4 d' j2 E* ]
#define ERROR -1/ H: H# f' k. C8 m* l, c7 H
#define MAXNUM 9999             // 用于初始化哈希表的记录 key
. u. \$ O  m/ k. j' O4 G! ~
0 ^* m/ D$ e# ]$ U1 Ctypedef int Status;
, A" t; j3 }& O3 S, @9 {" w* Jtypedef int KeyType;
% h. h4 t1 x9 i) R0 A" [4 n
3 r; C- S$ |8 v( u// 哈希表中的记录类型7 |0 T! X% z' f+ F& A. |' l: r
typedef struct
0 t. r$ Y: W) B! L9 r{' B& O4 q: h8 E9 |$ z; N
      KeyType key;
9 D4 J( g( }+ r' w2 L# `. t}RcdType;7 m; A/ r- G0 F9 {4 Z( J

( C: Z" m+ \7 N: \! e0 F  U// 哈希表类型9 l  b2 {: C% |: ?& O1 V" o
typedef struct
# z9 i  a; I8 H5 n{
4 |. m6 h% m( j& g$ h% M. G. J       RcdType *rcd;
6 d! L$ L0 N* m5 G       int size;
8 H  R. m6 R1 C, ?8 M+ F+ q# v       int count;
' L/ A9 Z5 K' u2 C& ~       int *tag;  D& k" W7 D# r) S
}HashTable;
4 x% X& a- j% S. f- O3 z) A/ s% n( [) J# p
// 哈希表每次重建增长后的大小
, Z. l; J- b0 W  Wint hashsize[] = { 11, 31, 61, 127, 251, 503 };
  ?5 k# n* z2 H- H9 z$ cint index = 0;
( U$ }# S3 i1 @2 B: X
7 O5 j; C; ?3 @/ A% }, \* O0 ]// 初始哈希表, s  u$ Q* J$ j9 H) i  w0 _
Status InitHashTable(HashTable &H, int size)1 ]. i4 b# Q3 G$ R( v% L1 B: E
{) ?/ d6 @( A6 I+ L
      int i;) F& S5 s# `  c' z/ O
      H.rcd = (RcdType *)malloc(sizeof(RcdType)*size);% N4 Z! b3 C! `( X4 Y% Q
      H.tag = (int *)malloc(sizeof(int)*size);
& b, N" S% w- T       if (NULL == H.rcd || NULL == H.tag) return OVERFLOW;1 Q. U* L3 H, h% ]2 ^3 {! @
      KeyType maxNum = MAXNUM;: b, H- e, a: r6 n. J
      for (i = 0; i < size; i++)
( }. E) y( {/ b, Q! w  p8 q# f, k# N       {
, G5 z3 s  r3 W. b3 P4 Q             H.tag = 0;
8 G3 @6 Z# o/ j1 z             H.rcd.key = maxNum;
3 ^+ P+ }5 Y* M9 Y       }2 p0 T/ A8 h, P% t3 o2 L; ^& i. E+ }
      H.size = size;
9 X' H4 M' W: ?8 v       H.count = 0;
# G% r$ K7 w. ]7 I       return OK;
% K8 b7 q$ Q1 l3 B) ^}
. p- D9 ^/ @, d! E+ B  f
8 e2 f" ~3 r4 H$ F- ?) H// 哈希函数：除留余数法' q8 {$ B! f% I" C% n( {8 w% G
int Hash(KeyType key, int m)# q4 f% C$ P6 c& R5 W
{
5 `, Q* t5 r1 Q* O       return (3 * key) % m;  s" g$ }6 B! ]* ~. F, D
}! F6 J0 M0 G6 K% a; _

- u0 J/ L4 O+ I( B" n2 ^1 }// 处理哈希冲突：线性探测
( C+ h3 }1 g$ v; vvoid collision(int &p, int m)
4 O# n1 W! j+ W. f, i+ B" a9 {{
8 c: Q! p) r. B+ J- z       p = (p + 1) % m;) N. N; ~! u- Z9 Y5 b
}
) u& {' F, L8 D7 H+ {
# t1 X8 J1 n; Y* M// 在哈希表中查询
2 r, e" d) O: u; @Status SearchHash(HashTable H, KeyType key, int &p, int &c)( y/ f. S3 U# `9 Z
{
) a# M7 W$ m1 c6 ?; c; p- M& r       p = Hash(key, H.size);
) L. j/ r' {7 X% e2 A       int h = p;
% x3 L5 L& ]* Y. y6 H, g. t9 T       c = 0;6 P1 N  c7 |% Y2 I6 p6 s
      while ((1 == H.tag[p] && H.rcd[p].key != key) || -1 == H.tag[p])! y% W$ ]( T7 X; V/ a7 n4 }, k6 V
      {9 s% U0 Y6 o  q5 K
            collision(p, H.size);  c++;0 T3 r9 y: O+ E  m
      }: X+ U: _$ Z2 A7 f7 |- n
5 B) \$ |( A1 R+ \$ Q& E1 w* j
      if (1 == H.tag[p] && key == H.rcd[p].key) return SUCCESS;
) _, s( H  x9 \8 T       else return UNSUCCESS;
  U1 ]+ w3 I" P0 Q}% J( b, j9 b" }8 D/ R0 t8 j7 G
8 f* Q2 E- H! s' A. K
//打印哈希表
  u5 s+ ~1 y. \/ R% yvoid printHash(HashTable H)
$ n+ V1 ^4 i" O9 G7 D0 A+ _& [{9 a7 F9 e' m" z/ I  y/ x/ h8 D
      int  i;
, A+ Y: U! |# b- i       printf("key : ");& e9 l( s6 E& d& {6 f+ m5 H
      for (i = 0; i < H.size; i++)/ Y, x8 ]8 f+ \3 l9 L7 u# H
            printf("%3d ", H.rcd.key);' R3 u8 r, R  a# _1 L" z  \. C2 V
      printf("\n");
- i/ T6 {/ C6 b2 g8 j+ G       printf("tag : ");
! S  t  S  c4 r/ x( Q# U+ E+ W       for (i = 0; i < H.size; i++)5 ^7 V! [; b4 Y! p) H$ U5 S$ t
            printf("%3d ", H.tag);
, F- A: ~7 V, F6 V8 p0 Z2 X       printf("\n\n");4 a6 k% J& X: p
}$ o% w4 k" P7 g+ ~) i, E0 T
1 t1 F: v0 J+ \; ]' J" p  m
// 函数声明：插入哈希表& I, U' D% l, l4 V) F) \7 p
Status InsertHash(HashTable &H, KeyType key);
/ W2 _$ R& E0 i1 l. m, u$ \' ^
1 [  [- |7 g5 Y( a3 B// 重建哈希表
+ f0 U7 E$ z" n# L# A' Q6 I! oStatus recreateHash(HashTable &H)
( T: F$ Q, @0 J( u{
/ R% G) i: _1 c8 ~# e       RcdType *orcd;
+ k; I6 L9 Y$ s. [* J       int *otag, osize, i;3 c) U' A8 \9 H  O" |& Q
      orcd = H.rcd;
  ~/ K6 {/ n, a7 Y4 m       otag = H.tag;* [! |) z# Y  @0 _+ [
      osize = H.size;" O, I0 G, n/ z& x
$ k4 r8 F0 d, N! A/ j' T
      InitHashTable(H, hashsize[index++]);
8 S7 d/ w- X# i; w       //把所有元素，按照新哈希函数放到新表中5 q- N# W2 K) D" _
      for (i = 0; i < osize; i++)
; ?: ^5 D9 S' ]       {  n2 w5 @% x4 V) e
            if (1 == otag)
- M# Z6 h5 \! G' s8 m/ N) I$ B             {0 C& @- }7 i' h: t: o3 K* v. c& b
                     InsertHash(H, orcd.key);
& \& u5 T: U+ J* k, g             }
+ s) \/ V; J0 L9 W8 f       }  ^) Q& @- @) O3 b- ?" n
      return OK;
  \: v0 ^, m% Q3 O! |6 R}
) P- `* N- a- P
2 ^! [! |0 ~2 o/ e5 s) C+ I// 插入哈希表
6 V* |1 k, U1 o) B. m! pStatus InsertHash(HashTable &H, KeyType key)
! }+ k- g0 a4 G) X' O) I& Y{5 ~6 R/ i, D; p0 z
      int p, c;* p0 P9 i6 S! @- h# T9 P" d8 w% u) X
      if (UNSUCCESS == SearchHash(H, key, p, c))5 m% L+ Z+ B4 u6 Z
      { //没有相同key
9 S( X: z* W) P* |1 h             if (c*1.0 / H.size < 0.5)
: `1 d1 c) F/ q; I& n2 J4 v6 ^! C2 G             { //冲突次数未达到上线
" M: @1 g& ~; m, W3 M                      //插入代码8 g) ]+ \+ ]% T6 d
                     H.rcd[p].key = key;
/ [: D: P( _) n/ N: ~; y                      H.tag[p] = 1;# v$ ?  e9 d1 l8 b2 c) k7 N
                     H.count++;
! I$ a0 L- O0 D: v% t5 p  x8 J) b                      return SUCCESS;3 T6 |" ^% I! [
            }) S  d, k+ h$ B: S" w/ G
            else recreateHash(H); //重构哈希表2 d+ Z2 }; R5 X9 M; i' S
      }
3 u! R1 r' B0 z) p# e( d       return UNSUCCESS;8 d6 U! K: j9 N' \
}( g) {8 g  T0 W! Y

# W0 _' h1 \3 M, _- x5 @, d; [// 删除哈希表) f' ]: U: I0 ^0 c8 P5 A+ a' y& j
Status DeleteHash(HashTable &H, KeyType key)
% b- q) Q$ t* O4 y{
- _, \/ d8 y( R* q  j0 S       int p, c;
2 \( C4 n/ @. {: X       if (SUCCESS == SearchHash(H, key, p, c))8 T8 a+ R. b; w4 J, d) T
      {
# Z7 S, z( q6 a4 {2 W, C% n             //删除代码
% b! r' Q* F( E' Z             H.tag[p] = -1;
7 {/ ]8 P8 [' N) Q  O             H.count--;
+ r% R! A: i: L             return SUCCESS;6 u5 R, X4 M* \
      }
5 Y+ G. h. K4 [+ C4 ]- Z: Y& l       else return UNSUCCESS;# i1 a) C" S4 u
}& f# |  v9 v1 W4 g, {' @
$ Z5 {0 e* u$ n- O# D
int main()9 f5 ^7 p5 L" g
{
; R: k( Y# s5 F& z4 `6 B- k- _8 r       printf("-----哈希表-----\n");) S+ f) ~+ \$ u) l7 \
      HashTable H;- }1 h) k. [8 N5 H" U3 |3 @
      int i;
+ F7 l) B/ T: j( E3 r# R  P. t5 w3 n       int size = 11;( t9 b8 l. g+ t& U
      KeyType array[8] = { 22, 41, 53, 46, 30, 13, 12, 67 };* Y: e1 T$ n$ Q' z9 w. F& }% N% M
      KeyType key;
$ c/ s2 `; q6 ]' n+ C# w8 v" F& Q2 j/ q7 p5 h3 \1 D# L
      //初始化哈希表
5 U+ K9 e* d& B8 U2 ~- t       printf("初始化哈希表\n");3 Y4 k" h) L( B9 }4 _2 p& Y% x' u& L
      if (SUCCESS == InitHashTable(H, hashsize[index++])) printf("初始化成功\n");% ~3 M- ]3 N4 s% t* _
2 z6 h5 F- o; i4 S# S: ]# ^4 p
      //插入哈希表
) X9 r/ m$ U+ m! X       printf("插入哈希表\n");% t, }% O# q0 X/ a! f' G" _
      for (i = 0; i <= 7; i++)2 u" y: v4 @, @3 g* h1 P
      {
  j: U3 v, x1 D9 J2 L             key = array;5 A# m8 Q4 I) l( _1 b; g
            InsertHash(H, key);
- f& V3 O: G" w+ t             printHash(H);
) a- N0 k3 |9 X6 ]' Y6 e       }
# f' o3 `( w2 _& S  b% E" P- q: a; W
      //删除哈希表
: I' K+ \: S' d" s- _1 x9 H       printf("删除哈希表中key为12的元素\n");
2 x3 e7 p5 Q9 S+ H       int p, c;1 z2 i$ O) A  y7 K9 Z( o7 g( h& D
      if (SUCCESS == DeleteHash(H, 12))
8 {. v/ c+ P$ a: G* Y       {
# w% m' m8 @5 B             printf("删除成功，此时哈希表为：\n");
( v) h1 {5 K3 @: W/ Y: a             printHash(H);
, z4 K( _, U. U# ^% y       }: p. q; p2 a9 w9 x6 A9 |7 c
1 }$ R8 z1 t! ^+ {
      //查询哈希表, r3 ?7 k* P, \( A! @  l% b
      printf("查询哈希表中key为67的元素\n");+ @* K! k2 ?. o; l0 p$ Q
      if (SUCCESS == SearchHash(H, 67, p, c)) printf("查询成功\n");
5 o4 C' c# X! n+ n" K4 a* R: N1 A+ ?0 l% _9 t5 y& B$ y: {8 m5 \6 C2 \* G' ^
      //再次插入，测试哈希表的重建& D. x3 P% H$ Z; G% t0 @2 |
      printf("再次插入，测试哈希表的重建：\n");/ o4 Z( }7 b7 c( Y1 H9 N
      KeyType array1[8] = { 27, 47, 57, 47, 37, 17, 93, 67 };0 D3 {- j# d: f
      for (i = 0; i <= 7; i++)
% m' j, g% _9 \7 A! i       {: K- u/ u! |; c" x, Q
            key = array1;$ s6 F8 ^3 [' N
            InsertHash(H, key);. {% E( w( P7 [
            printHash(H);- m2 E$ j& _" ]. @" h
      }3 G1 j1 V: N; ?- J! J) [9 `  `, @5 ~
7 S; |: X9 [9 W! U2 d$ Z3 ?
      getchar();
$ n; P( w- }: Y$ q       return 0;
( H3 @( o4 J# |) o$ t- r}4 K0 f# B; {$ _1 W# L1 \4 ?
( R/ @6 q* d1 B1 D! V
6 二叉树查找
二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
算法思路：
若b是空树，则搜索失败：
若x等于b的根节点的数据域之值，则查找成功：
若x小于b的根节点的数据域之值，则搜索左子树：
查找右子树。
7 H; z1 X4 I2 P# A6 Z
代码：
递归和非递归
//非递归查找算法! `' ^# w( k; J8 W  F3 C. X
BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p)
/ w0 \9 q9 ~, ~% L{
. j3 J% C( q. _9 A, L" m# u5 j //查找函数返回指向关键字值为key的结点指针，不存在则返回NULL
, O1 g6 Y: O$ J1 y/ d p=NULL;
6 c- o0 o' l" p9 B) h. v8 G6 B0 l- l while(T!=NULL&&key!=T->data)
# {4 c& n. g/ }$ Q8 ]* p' F {3 K- ]+ ~, \$ x, i, {. H: `  {8 H
      p=T;                         //指向被查找结点的双亲
' ]  z: u1 @8 N" ]       if(key<T->data)! l4 ^; r2 r$ S' _9 n
         T=T->lchild;             //查找左子树0 ]  E: b+ F2 o+ k5 T
      else
/ o$ n1 z' B  v1 i* j' K          T=T->rchild;             //查找右子树* y3 i+ G8 X; w( I7 z# g1 w
}0 o) z3 W" a! L6 M
return T;3 U9 M! G4 i. y* w, H8 T4 G
}$ P  x; Z5 m" x. |& B

5 p' `( a# a+ X+ y% l7 u# n- A1 H//递归算法
. [; b- z9 B/ R1 v# iStatus Search_BST(BiTree T, int key, BiTree f, BiTree *p)7 R& X  q- |2 K) P2 P$ ]3 T6 F5 R
{. T; o; s  d( k' x8 x
//查找BST中是否存在key，f指向T双亲，其初始值为NULL
6 w3 \5 @( J9 @ //若查找成功，指针p指向数据元素结点，返回true；4 b# v! [, \7 G: R# h
//若失败，p指向查找路径上访问的最后一个结点并返回false
5 g' W* D/ m/ D$ g' K6 ?0 \* E if(!T)
' o* t- K* s9 _( P; W# A: L9 J {
7 {1 b5 U" U7 P' z6 S. j" d- T       *p=f;
: {' Q; b# z1 J       return false;; n3 g8 x8 c+ H. Q- y
}
8 L0 E5 L* x- l# n  o# I else if(key==T->data), {1 Z/ y$ g0 Z
{                   //查找成功- q* }' H6 C8 E" n" }, N
      *p=T;
  `8 [- p3 r0 \% J       return true;
% L1 \" z& n' k0 @ }0 V& M! h+ `2 V( H- Q
else if(key<T->data)
+ m( C3 d3 C$ Y. b7 v% _       return Search_BST(T->lchild,key,T,p); //递归查找左子树, }+ ]3 k) U* w+ c' v; p
else  n/ z7 Q4 \$ X/ I3 y
      return Search_BST(T->rchild,key,T,p); //递归查找右子树4 m, u! ]* b; w; T/ R

9 g  l- [/ j% ?/ ?}3 _/ X0 O* f6 Y) c, T7 ^

" U0 l5 e% C4 G! {) G  |8 `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还要大。

' P9 v" P) F! X: g9 M- E$ K

算法思路:
要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中的任何一个相等，查找命中。否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。
2-3 树中查找键为H的节点 2-3 树中查找键为B的节点
代码：
two_three *search23(two_three *t, element x)
0 p) r" [4 i, T% o% D) R, X3 F{
  q$ S( @6 ^3 E% _4 u# I$ y while(t)
3 O) H, {4 q0 d) O2 B- V {) e( C. ^5 a/ f6 s& C( D+ i
      if (x < t->data_l)
2 d$ m& l9 Z: [7 P% L       {
2 j: T$ m0 O' U) Y- g6 S8 J2 L          t = t->left_child;, F2 e# \! w0 h. e
      }
& {- t  y, H: ^- f6 K2 j9 ^       else if (x > t->data_l && x < t->data_r)
: Q3 r0 A% A5 F, f( T5 w/ O       {2 Y3 t/ A2 D  F, _
         t = t->middle_child;* C5 |) f# }% G. T( G
      }
. J+ X  r; V" \6 |; l" n8 \/ b       else if (x > t->data_r)2 H# X9 L# v3 }/ J- D
      {) p2 }; A0 y: v1 O5 a- O; m
         t = t->right_child;
2 c, n' [2 m9 Z0 \" a. l       }% ]0 l+ f3 o) g+ I" V
      else
3 h& f* u6 g3 s; N) ^( V" x       {! r( j# @/ s3 d1 s" g# X! I/ @- i
         return t;
9 h8 s- I; g7 o4 f       }
" j, c/ s# M9 E0 F8 F2 Z- Z }
) o5 |# y4 Z% p' V$ }' J! r return NULL;
: I1 S% @: y7 ?: g}- Z6 \* J  d# j9 U8 B; p
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树转红黑树
为什么使用红黑树：
红黑树是一种平衡树，他复杂的定义和规则都是为了保证树的平衡性。如果树不保证他的平衡性就是下图：很显然这就变成一个链表了。
保证平衡性的最大的目的就是降低树的高度，因为树的查找性能取决于树的高度。所以树的高度越低搜索的效率越高！
这也是为什么存在二叉树、搜索二叉树等，各类树的目的。2 a; [2 v: K$ @3 j2 }# y

红黑树性质：
每个节点要么是黑色，要么是红色。
根节点是黑色。
每个叶子节点（NIL）是黑色。
每个红色结点的两个子结点一定都是黑色。
任意一结点到每个叶子结点的路径都包含数量相同的黑结点。7 }, W, Q6 r- d. b

算法思路：
红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。
代码：
#define BLACK 1
! p" d7 a' v1 u3 o1 U#define RED 0
! y5 v2 q1 ]. B8 d& X. O+ E+ E6 m#include <iostream>* R! E) n: ^( t, G5 q$ q5 C

0 k3 i* c$ s$ x' }7 I9 s; rusing namespace std;: Q/ M% ^( D% K
0 u) J. n* Z& w. s
class bst) G3 b, `8 l' Q: S* U- b
{
9 o* `2 ~( [! w) b3 \" ?0 Sprivate:* X( `" |/ b( ~

; m; J) f' d3 z       struct Node
  P2 V+ P& A9 U/ Z% ]       {. ]9 t& `9 K- W) o; L+ g: ~
            int value;! r6 T% A. q% `- Y" w
            bool color;
' R, K" q7 T& Z! H, F- ]             Node *leftTree, *rightTree, *parent;
7 s9 O' {' s' x4 a
/ a% j: ~3 [5 \             Node() : value(0), color(RED), leftTree(NULL), rightTree(NULL), parent(NULL) { }
% W; `) Y( h% L3 u) a! Q4 {+ g8 A# X+ J3 U9 f5 @
            Node* grandparent()# v, l4 R! ]/ h" x
            {
* q6 N" b* ~! t% s                      if (parent == NULL)5 k1 @% x+ H) P( P- A+ x+ x; X7 r/ ^
                     {7 G2 C' }2 n1 f2 r7 W; v3 b" \
                              return NULL;
* W3 ]& J4 A, K# f7 M0 g% ?& a5 t                      }$ J! K0 m* M6 `/ n
                     return parent->parent;% x/ C5 p* v+ p' x* u7 e- b2 o3 z
            }. [- f, I9 q' Y8 b/ L* o: }
& p* c8 T9 M" O" u2 J  m9 m1 ]; N
            Node* uncle()7 \2 }8 }; S& T! ]9 {6 N
            {
3 z+ ?* i- m3 n5 o                      if (grandparent() == NULL): G1 V& `  O( [9 h+ _" m. }! ~
                     {
. z% u/ {$ K* c                               return NULL;
; m5 ]. W8 ]5 q& v* e' O                      }
8 i+ P9 g: e9 R& u: t" ^* j                      if (parent == grandparent()->rightTree)
; s5 F9 x( Q) f; @8 U                               return grandparent()->leftTree;
) R+ r# N8 ?. G0 X+ c2 w                      else
  ^1 Q' @$ p/ K) J5 H2 T. V                               return grandparent()->rightTree;
2 B+ j$ O$ q) R, X' p             }. u. H) R" V# @1 R( h. Y

( p. N2 F* h: B* d             Node* sibling()
7 h) P! K: e( Q( {             {
( E5 b0 G6 X0 H- s3 Q                      if (parent->leftTree == this)
) t$ e  J, A4 A8 k: c                               return parent->rightTree;) l: T; g) [2 h# |# ]- O, K8 e9 F
                     else5 n9 ~7 n% a8 E+ g# U
                              return parent->leftTree;; D% W  F8 V$ a/ k
            }4 e( h. X! F3 n' }% A; R& U
      };
- G5 ~% B6 l3 o  R: ~. R2 ]7 e: Z' f$ u
      void rotate_right(Node *p)4 D% ]. j8 N( h9 W
      {0 L" N8 c6 Q5 z8 _7 N  D" u: T
            Node *gp = p->grandparent();
+ a& v7 J! I+ U; [6 `             Node *fa = p->parent;
9 B9 @( q/ G+ Q3 U             Node *y = p->rightTree;' b: x* j' d( G2 c0 M* F

! b+ |2 ?* W$ C# q) w( c  Y4 j             fa->leftTree = y;
* g+ \" S( V5 m8 B0 u# s5 \, `/ Q  F: q3 Q: T' n4 s' J3 b
            if (y != NIL)
- N" j) I! s* B; g5 J                      y->parent = fa;
1 \, E$ d9 b( I! c& B. V$ H2 c             p->rightTree = fa;
* \& b% B5 x% C* E- F! F3 ~0 J             fa->parent = p;9 r8 W4 a* @! D

6 K+ Q8 J+ d, p8 o* k; x             if (root == fa)7 @1 r8 w& d2 E( X  T$ Y' R
                     root = p;' c4 R; ~' K. ^( \
            p->parent = gp;; Q( n( f; C- v8 G- l
# _4 V8 G/ \( S- D7 Z% R4 @" v
            if (gp != NULL)) L$ x& u+ U& K% ~/ w' U( x" j$ Z; d6 ^
            {
; Q5 t% O+ b) d+ u                      if (gp->leftTree == fa)  M3 C. w0 ^! @" v, E6 Z/ a- |
                              gp->leftTree = p;- u; ]8 M; Y! w
                     else
+ A) ^4 r/ n. E* H6 W                               gp->rightTree = p;
/ H: u( `* }' Y( ~% d( k             }$ d6 ?: P. N+ J6 t7 V, O0 Z9 q

* X+ _" k- Q& L  {  d* Q+ p       }
8 ~. c+ I3 h- O1 [( Y
1 v: `& ~! x9 |" p3 z; y       void rotate_left(Node *p)4 z! ]; e0 ~% I
      {
: _. {) j$ K& V" A& a             if (p->parent == NULL)# u' _) E, J- Y# M: e
            {
% f! l1 m' _4 z- x+ s- b4 H/ L                      root = p;
7 ]$ r: X2 k0 y# c% |                      return;
- }! e3 \* v, G1 v2 u* n. u             }
1 n# B6 F/ e9 |( Z) d1 |: U  j. G( Q             Node *gp = p->grandparent();* V  M' ~3 g, T; |) G: ~( t
            Node *fa = p->parent;, G: b+ d+ N3 ^* R2 {( d) C7 P
            Node *y = p->leftTree;3 y& E* N& s9 J& v" h/ Y' ?
: P$ Y" i% n6 J0 P% v
            fa->rightTree = y;
' Q4 a  G0 _) j. Y, K8 U% s1 a' o% R! i( d
            if (y != NIL)
8 Y" D  m8 M) r7 T                      y->parent = fa;" E& r$ Q8 @2 t8 x! \) P" m- E
            p->leftTree = fa;/ F% ~4 k* A8 Z& m  k
            fa->parent = p;
% F7 R9 \: A  a/ R6 I  [' P$ [2 B6 G+ h0 q% j# ]
            if (root == fa)- o+ C( a0 h0 o, f, a) |
                     root = p;6 o+ A- Z( \' P
            p->parent = gp;/ Y, ?) {8 a/ j$ Y( B
; U9 z# W2 i4 _% P
            if (gp != NULL)
5 t6 A/ r3 \$ g0 t, [             {  L. z. l1 ~/ o- _6 E5 E
                     if (gp->leftTree == fa). b. E$ `6 U, y* R+ N2 Q2 s8 l2 ]
                              gp->leftTree = p;$ c4 T8 a8 Q( ?2 F$ l
                     else
( K- K3 a% b1 }5 R                               gp->rightTree = p;
# b1 t2 l- O/ F  R* R# n/ r             }
6 }' J- ]7 k8 E8 R9 X       }2 _6 Y& {& q2 ^0 _9 i) O' _2 Y
6 m' g5 y7 E) l3 p
      void inorder(Node *p)
0 ^6 {: M2 C6 h2 J0 e       {: I7 L5 d0 [) T( P
            if (p == NIL)
! V% O6 ^# [+ n. @* h: L2 V0 }                      return;
& z9 h. z7 U6 B7 z3 i5 _& C! ?& x' _" U$ D. ]" X
            if (p->leftTree)( a1 m( [! f! m6 J) K! s
                     inorder(p->leftTree);
( u0 K/ c' x* T4 Q
- I" g9 ]8 r/ l  `             cout << p->value << " ";) ~3 A( b8 |/ l9 x$ O
+ X, t6 G- m: d; \
            if (p->rightTree)
  ^+ i' V7 ^  r; |$ ^7 ~, r" O                      inorder(p->rightTree);
$ v8 L$ G" I6 |4 x& K6 n5 i       }$ O. D/ p, w+ N6 W6 T
0 D# @, S8 \' m6 W% z4 B' y$ D$ P
      string outputColor(bool color)
: w: C- o5 m% Z% y0 W& k/ n       {
2 v% C5 M) ], P  P) _9 I             return color ? "BLACK" : "RED";
% y. ~" N. C9 _& g$ g       }
# W7 C2 h- m5 I& a4 T2 Z# {" @; W7 w0 g; b3 H. Z
      Node* getSmallestChild(Node *p)
9 c6 [! E; \* Z3 d- B, A$ Q; A       {
- R5 ?4 Y/ y! i$ |4 Q; u             if (p->leftTree == NIL)
6 P6 A8 V+ s/ J  J" K& k                      return p;3 ?! v3 x" T+ Q: l9 _" l) V
            return getSmallestChild(p->leftTree);
) h' T- N0 K) F0 T9 W! @1 K       }
$ i0 \7 A) a+ }5 c) L' [' x/ D. p- B* F0 U1 b7 S1 o
      bool delete_child(Node *p, int data)
5 o$ O; G# K% u* F! ]; k       {) M. ]3 \0 ~  h% C/ F6 {
            if (p->value > data)* e0 H1 Y! w3 H
            {
  x  }. t( E6 v& Q3 y) ~                      if (p->leftTree == NIL)
4 y! C- r$ C" Y6 R. P( m                      {2 c) [  t. G* {: m3 u
                              return false;
- c  P4 \/ l9 ]4 x# p                      }
% ~& G# i, O% U9 d* E                      return delete_child(p->leftTree, data);
0 I8 S% \! ~* L' X$ q0 e1 k  ?! s             }
1 B: R: m  g6 {  k3 Q- ^             else if (p->value < data)4 R2 m8 f: u2 ^, {! l8 g# p
            {+ h% D/ ?6 z4 ?0 \/ \8 X8 s
                     if (p->rightTree == NIL)
/ I) a1 y: d) ^: b9 W" X                      {
% w3 e' p' l$ Q8 Z8 }- H( }                               return false;. l) n: w! {* t- J
                     }
8 l; Y; x2 R( K3 f) K                      return delete_child(p->rightTree, data);! y' _; A& i1 A) Y7 T2 r1 F- h
            }
9 ^  |$ z& T% `( X8 C, M; j0 w             else if (p->value == data)
0 B0 y$ F5 \2 a( K7 [# C             {
4 j( e9 n0 G5 E0 Z& r                      if (p->rightTree == NIL)
- |. @" |/ x3 `$ E5 Q/ A) P5 [- g                      {
/ r7 [( y6 G' v0 n3 a. H! I3 ~                               delete_one_child(p);0 G2 }5 h* O  U1 U5 c& e
                              return true;
% H  j( K- J9 }2 X+ u                      }0 O; W2 H6 T# T8 L& I6 S
                     Node *smallest = getSmallestChild(p->rightTree);
: }0 U; \3 K; D1 J3 m0 m& m                      swap(p->value, smallest->value);4 S0 R9 n# _( p* X4 o6 I5 n
                     delete_one_child(smallest);& g0 b' h. d- _4 z; b1 S

( w; S6 ^3 A5 h. u                      return true;
5 R  B. }) b" T5 ~# g+ ?' `             }
0 {. N7 j$ d7 ~             else
+ J2 i9 x3 c% a* [             {
                     return false;5 e6 `, m/ ?1 a% }  w
            }$ E- @2 g/ S  {* a* C, U8 o! _
      }
9 m0 X# N# t4 R. y/ I; p; @. |7 f+ v$ c2 h; `1 i7 z9 J5 _  D% q1 S+ o
      void delete_one_child(Node *p)/ F5 q. k0 _: k+ k
      {
& p( {5 P" t) G9 {, R             Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
. A4 F0 J6 F3 F" A$ [5 ?+ N. ^2 E             if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL)' S0 L' p& g- F, b9 P7 |
            {$ n. D2 G' `- o) e: E
                     p = NULL;
6 j$ W2 w' t0 `" A                      root = p;
! {2 G$ y3 W, H                      return;
* J' e7 r8 r% s$ T+ x* a9 o3 h& F% M             }
5 g- i& j( N9 ]: J6 x% L1 Y# e$ _  A1 x
            if (p->parent == NULL)% I( D; S! ~4 {2 T& q  b# o9 }' v
            {  q; K8 W. j* l4 h
                     delete  p;
* G1 ?" c4 p$ r% T: T6 w                      child->parent = NULL;
  q+ H. ]1 e3 b! b& i3 |; }% D4 S                      root = child;
  ~0 b; D& c+ V+ M- i* I* A                      root->color = BLACK;9 ?# M& L. u. k1 y
                     return;% s4 W) j5 p) A: m4 Y' [" r
            }
4 ^0 g' T) v/ i$ M# Q4 A, U
3 ?: I6 h! f; V: h1 d4 f             if (p->parent->leftTree == p)4 x$ w: l) }0 Y7 W$ z/ t
            {$ x, i' K# c% s2 @) P
                     p->parent->leftTree = child;
% h0 Q! q3 [$ o0 }, L/ Q1 I             }
  R5 I# `9 ?' W9 E1 `6 x* D* X             else
5 L' [/ \# x( b% I1 W; _             {( C5 G. U9 C# p% A
                     p->parent->rightTree = child;
8 t9 Y5 O$ h' G9 L0 Z             }
9 i1 d0 r! U- K6 C+ H1 Z% `: M  s             child->parent = p->parent;
/ e6 |: R/ k* {2 F8 f/ w3 b" S" |0 I/ _) |* O$ |1 q" _
            if (p->color == BLACK)
% E. b+ p+ O  S- N# x             {& T4 T0 b. f( s( I) b
                     if (child->color == RED)
' Q: G% F) e1 K9 r& o                      {
) t. G$ J! i; E& G6 a                               child->color = BLACK;+ M+ z5 f9 l, D- Y6 |! G! R
                     }
( k% U  [8 `2 l, J                      else) k' Z! a% Z, p$ Y- y  U& X
                              delete_case(child);) W. S% X3 H1 U1 F8 ^9 K5 [) c& V
            }7 b) @% T& d" a( E) T. K# P
8 R$ z" @. ]( J; b, e( R
            delete p;* G* Q2 o8 W7 l  M
      }  l! v4 q" ?. P' n
: C/ {% _, b" p$ g# `
      void delete_case(Node *p)5 r# Z# `: R% |; X. K
      {& |8 \9 V8 h, e, h9 v
            if (p->parent == NULL); I# o0 x" l! e( Z
            {) q, T7 E+ @4 D
                     p->color = BLACK;
2 Q6 Q0 T: X/ V+ U( v" D/ I                      return;
& m$ }3 d3 ^# D/ T0 B1 h' G             }$ @( o0 v% U0 @/ {8 _. ?: U* O
            if (p->sibling()->color == RED)
& H1 Z/ l% F# _             {
" `7 P! b. J! g. q) ?                      p->parent->color = RED;
                     p->sibling()->color = BLACK;
5 A  v& C! V+ X$ K; r                      if (p == p->parent->leftTree)
3 e# D2 G0 n1 E; M' U, `                               rotate_left(p->sibling());, h, E4 A, o- l3 x0 G8 _3 s
                     else1 D0 I5 |' t3 M
                              rotate_right(p->sibling());* V/ |3 m& p1 k' A' o' E1 I$ j! `
            }$ b" g% L: U2 I8 q) |5 S, `
            if (p->parent->color == BLACK && p->sibling()->color == BLACK
% K8 b" `+ K) U7 c+ `5 t; L; _                      && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK); u0 B9 J! x3 _5 b& ^" s) t+ V/ B$ I
            {
% v; C5 z3 V9 i6 D+ G, c' K                      p->sibling()->color = RED;
# C8 i/ U1 r& ~2 n; `* m! P                      delete_case(p->parent);' s6 W) p$ n, ?8 f/ H% T8 K& j
            }( [: o! E6 ~: D0 _$ {- l$ k/ O* y
            else if (p->parent->color == RED && p->sibling()->color == BLACK
7 x% q6 m; o: }3 v" h! U                      && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK)9 e; ~; W& K/ r3 {, V$ E& R: x
            {; j+ K* E1 Z- d' _& K( H7 `1 q
                     p->sibling()->color = RED;
, P" `" J" ^& ^                      p->parent->color = BLACK;
' [; j  }+ m* L' ^& n             }8 A) @: `* _, q4 I' G
            else
# w0 i# n. `, B, S             {
( h) p: @* |  ?: |0 q3 f* }6 S5 E3 H                      if (p->sibling()->color == BLACK)
* i! \, V- ]1 `( ^                      {
* ^& `* X5 C3 w  i: G8 t                               if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED
& [7 |0 q6 c4 |( y  T* j* ~4 ^) a                                     && p->sibling()->rightTree->color == BLACK)
6 m' |5 q! h& C7 }4 n$ ?( D                               {' V8 T; u! J, M- P0 n
                                    p->sibling()->color = RED;
0 m6 B2 G- u( F) ]6 f: C! H( y/ A                                     p->sibling()->leftTree->color = BLACK;! U) C: \7 f5 C  v0 w
                                    rotate_right(p->sibling()->leftTree);% K# U( M8 A6 c4 l8 r; s1 D, J6 V
                              }
# b. R* x- A0 W1 G* {. t7 J                               else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK: c, c! q3 ^# f, [6 M
                                    && p->sibling()->rightTree->color == RED)
6 o! H9 X4 J- K1 [8 a5 W                               {
; V) F" ~) G* S" x                                     p->sibling()->color = RED;
                                    p->sibling()->rightTree->color = BLACK;
7 q5 o8 H% M4 z% ^                                     rotate_left(p->sibling()->rightTree);, O! V) o$ H8 m1 Z
                              }
. M( A9 f) {' f5 F                      }% o2 g1 o; X. z2 B/ N
                     p->sibling()->color = p->parent->color;! k2 g5 f8 T- J3 E' I# F) g' A
                     p->parent->color = BLACK;
6 R* p* S& T/ M0 B                      if (p == p->parent->leftTree)9 g6 ?& [  S" Q0 u5 J2 Q, P2 B
                     {1 F) f6 k4 U- u
                              p->sibling()->rightTree->color = BLACK;
* S* T* t: a8 e  B                               rotate_left(p->sibling());- o( @5 o( g! V  G
                     }5 V2 g  j, L( [( Q
                     else) \0 t2 z( ]3 y) o/ v
                     {( M0 y* Y* r& ^+ i6 e% o- R
                              p->sibling()->leftTree->color = BLACK;
+ @# }2 [; n" D/ T2 d# w                               rotate_right(p->sibling());
2 F4 x- [" B9 K; k- y                      }
6 i5 z7 p) M  x( H             }
6 @* X0 b  h, J0 K+ A       }
6 X( P* E/ M& v6 c/ E, G# O* U8 p6 U6 l! Z" r" ~
      void insert(Node *p, int data)
! `- d# o! a+ P' z       {0 b9 P& ]; o  x3 Z0 _& g7 n! p, W
            if (p->value >= data)
+ Q; d; S/ ^4 ~) z+ a: ^# Z             {& i+ I0 _& H9 c+ o/ u& m
                     if (p->leftTree != NIL)3 y. S8 v. F8 E0 f
                              insert(p->leftTree, data);
                     else. @0 }' }7 A, d
                     {1 v) [; n4 Y( o7 T
                              Node *tmp = new Node();
( i* Y" e) e1 N% K                               tmp->value = data;6 |: I! G8 K1 [
                              tmp->leftTree = tmp->rightTree = NIL;
& W% J, f* u) t% S& v1 n. v( q- f                               tmp->parent = p;
1 E, r- i( ?# \3 c+ P) Y                               p->leftTree = tmp;
9 Z4 R- z$ U7 {& d$ Y                               insert_case(tmp);1 Z2 N8 A* v5 d7 \, g' C
                     }
8 n% F$ f- T: o% o3 e& l. z             }
4 g! Z+ b4 a( J" }             else3 q& l! Y% f. k$ @  O
            {
+ d* U: J, Q, H; V8 s5 `                      if (p->rightTree != NIL)
4 ~- p) o7 K$ w. h" g                               insert(p->rightTree, data);; j2 U: h  l0 @- j' [
                     else4 |* r* K/ y* x1 U  `' M: L2 T
                     {
) r4 p% k0 l9 D8 _- i% M                               Node *tmp = new Node();) j/ O8 [6 d3 q0 c
                              tmp->value = data;8 o" }  h% Q  C6 c5 H& C9 {
                              tmp->leftTree = tmp->rightTree = NIL;4 t% Q2 O  Q: q) Z! X1 g) C* x
                              tmp->parent = p;8 O% G/ K$ V4 \$ q8 k" y+ s6 H  f
                              p->rightTree = tmp;5 ]/ H; t# M6 _+ @+ ]2 ^, F3 z
                              insert_case(tmp);
( h4 L! e; m' X                      }
1 }1 I0 u6 @4 y- Z             }& d0 B* ^6 }% }- E# G
      }
3 ^# D( X( H! w, M' G, F2 i* @! J- b+ t8 A, @; j" P; N0 W
      void insert_case(Node *p)
      {
3 V+ m- @! [$ c& ], m1 O$ @             if (p->parent == NULL)
" Z& D4 N: Q8 B2 W             {: a9 _6 c1 }+ G! l4 \
                     root = p;
0 }. r, ?8 @( O                      p->color = BLACK;; Y" W$ I6 p5 }- U1 K
                     return;
/ B- J4 ?" Z9 z: j4 h+ f& z  `             }
% }0 \' U0 m; \4 s             if (p->parent->color == RED)0 F; e) l6 k4 u6 a
            {
0 Q3 F; w& k- f" ]/ b                      if (p->uncle()->color == RED)
  k- Y0 A& ], f/ {0 M" a                      {
4 q1 y& V2 W- o8 |: L) p                               p->parent->color = p->uncle()->color = BLACK;7 C; r- U& Q, v( w
                              p->grandparent()->color = RED;8 F( Q$ o  R; i* g" E, A/ R+ |- b
                              insert_case(p->grandparent());/ _3 d# T  Y& u( w
                     }
7 U/ T1 U/ ~0 T4 O                      else6 g" P2 B/ T; T+ I, n! {% x
                     {
' [9 H# n* c6 i4 K) a8 v                               if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent)( F* }+ J4 ]$ ~8 I) w1 [& i
                              {
0 B  Z7 J. c7 d8 q" {1 A. H                                     rotate_left(p);
, O2 R, m+ ?2 x. t5 n2 l                                     rotate_right(p);
4 y' a$ d- S1 P8 i4 q: d                                     p->color = BLACK;5 f$ _! L8 d& ~! {% p" j; Q
                                    p->leftTree->color = p->rightTree->color = RED;
" H9 t# K& N, _. N  R* n7 j* U                               }  I/ F! A6 t5 q# k" Y6 }3 S" ]; ?3 b! }) D
                              else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent)1 C- z6 E: Z, O4 E, |
                              {- w3 T  g8 D% f& ~  L6 p
                                    rotate_right(p);
4 P. `3 b- X$ R* m5 z2 e; K                                     rotate_left(p);% E, g* |, f8 G4 ?
                                    p->color = BLACK;4 X! q3 a: k! e' ]
                                    p->leftTree->color = p->rightTree->color = RED;! r" U' `3 Y& n# A
                              }
% G% Q' S7 |* S% z# [" k) C: r                               else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent)& ^. ^. u4 r% ?$ X7 i
                              {
( n/ n* t/ h% y; g% D) ~                                     p->parent->color = BLACK;  c9 P( r8 C+ F1 Z$ G
                                    p->grandparent()->color = RED;) w$ |4 r# J3 W3 _- T4 K
                                    rotate_right(p->parent);
+ @: V! J- s2 \. L2 h$ g  E4 P5 k+ E                               }' ?+ X+ A* ]6 q1 i2 i9 x
                              else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent)
" v, J. ?; {, u  r                               {2 X& {& L9 R6 }3 e/ `: Q0 d1 w2 i+ I
                                    p->parent->color = BLACK;
# Z2 [6 p. Z% p4 v4 N0 ]- k                                     p->grandparent()->color = RED;" N' n6 N( |8 w0 j. [
                                    rotate_left(p->parent);' t& k4 w; D2 n7 m2 \- l- M8 D
                              }/ K% T% d5 _: |( g8 e
                     }1 g& U# X8 a. C3 d, _5 T# {
            }
* N5 V( m0 I6 J1 c6 ?3 K- q       }
! g8 {3 \5 {, t5 O! L: P& O9 ~5 }0 X; ]
      void DeleteTree(Node *p)
  v( Q0 O! b. J' f       {; X3 x" F; U. \' u( J1 ^
            if (!p || p == NIL)6 X- `' t# z5 w6 I4 x; ~
            {3 U6 R) P) D6 r( H
                     return;* L) A- b: y8 J# [
            }" i. l0 B% V' N- b) P$ j. I
            DeleteTree(p->leftTree);( a  }4 [/ @# P+ o4 d4 t% z  W
            DeleteTree(p->rightTree);
) H3 F) t3 X/ J+ f: s2 v3 E0 P) e             delete p;  m" B1 e, J3 M- A4 `, h2 D  }
      }
. p- W& A: R' D7 R. @' qpublic:
' X% c$ X7 i$ {3 ~
5 L3 a* _4 j7 N) h0 i! o       bst()' B& a7 z: D0 x1 ~
      {
+ j" y/ U# n) q9 h. U8 S5 ?& Z- r             NIL = new Node();
6 w+ t, }% g: u             NIL->color = BLACK;
  V$ p& N; V5 a1 k6 O( z7 R             root = NULL;
2 O% n& ^# x$ a8 Q       }5 d" c4 l: g8 i: e3 w. h4 i

+ ]3 @* g% {/ ]+ W) C7 f  L( j6 Q! w       ~bst()3 X4 [' x/ l- Z3 }6 J
      {
$ `1 a6 R& ]' l& E7 w3 I6 a             if (root)5 {& `: Z; s5 W. D/ s" D, c4 j' v
                     DeleteTree(root);
1 y) P# L; u6 @8 I4 j. }             delete NIL;
3 P$ ^! @: Z- e5 O  U       }3 F8 H* W4 B5 Q, t4 m

0 l  R5 P  C1 }- {3 _5 O! ]       void inorder(), m  p5 y0 P5 [  m. H& r
      {
  K3 V9 U5 Q" [/ q9 b& R             if (root == NULL)
* M4 k* n, ~8 ?! L5 ]+ e4 Z, j                      return;
' q2 ^- [' W+ ]- [) n% k- p. L$ d- e             inorder(root);
' [! X2 O- U' b6 B" c, p  R0 E             cout << endl;5 R* n: h) P. g; u
      }
0 H4 V$ n" n. V- O5 q$ `5 t8 N6 Z7 d. x* T$ \* Y
      void insert(int x)
8 U6 X% G) S& A: x' p: i       {
) k0 ~) r2 f1 h. t: O3 F, A4 Q- e/ |             if (root == NULL)3 w$ p' ]' T( `6 R% e9 w- Y! _
            {
. {8 x) j6 y  R) Y$ o! k                      root = new Node();
* j% `  d* T- N4 ^' a                      root->color = BLACK;+ h: i3 \% @+ W* x6 X% B) W
                     root->leftTree = root->rightTree = NIL;4 m+ W0 ]! Z- J/ q- B
                     root->value = x;
. E0 I) U$ p( X2 M- v             }
+ @; q. P: _4 W' y& H1 b: U             else' g5 l& m, Z1 b) \8 F$ G% ]" `
            {
                     insert(root, x);+ C4 s* b- W! W8 P5 ~
            }
! t  l& k' E& r5 o) y5 q       }
1 i- {: h5 U- C; J$ y6 Y
: i. B5 Y( X5 E9 Q2 [. T) B- C5 J* B       bool delete_value(int data): a8 r8 d; H- N7 e) w
      {, I+ d! |! `4 Y5 o. \
            return delete_child(root, data);7 B+ l4 r6 i0 g+ e, l
      }
3 L; n- Y3 `! V  n" O& C7 jprivate:9 b2 Z: ]8 d2 O0 [/ G
      Node *root, *NIL;
% E& Z% T2 L, t7 q7 N};* p. J% G$ E* c- O4 S

5 J3 S+ c- M+ yint main(); P4 M* j; W: y
{
/ J1 o, Y/ I* f$ b% e& o       cout << "---【红黑树】---" << endl;2 g4 U. q* m  s; Q6 {2 o% @
      // 创建红黑树( V* A9 k8 F1 S0 S# ], B- w$ S
      bst tree;$ x0 B: \, m' `% F& G/ |

/ r6 _  ^% J: b, M3 ~6 H       // 插入元素( R7 q& K& p* ]6 P, Z) d2 k
      tree.insert(2);3 h* v0 G7 B& q
      tree.insert(9);
8 O& T, Y8 `# [6 D       tree.insert(-10);
5 P; ~' R; f, D       tree.insert(0);
! h- e$ x! v8 u: w       tree.insert(33);$ W1 c: A2 Q# }. T; g
      tree.insert(-19);
+ b  B, `3 a0 }# j# Q1 `
, r  m* M6 q2 J+ E( s       // 顺序打印红黑树
2 X, F2 [8 }' C; e3 K       cout << "插入元素后的红黑树：" << endl;
      tree.inorder();
. E" W" Q% }$ @  }' ]( Z5 J, X; ^. A' [7 m4 \+ t
      // 删除元素6 l" T! \( |9 K8 ]9 f
      tree.delete_value(2);
7 b5 j- m. E% @6 e3 E; X. w. t/ F9 Q
      // 顺序打印红黑树
, ~. @* x0 U! e% L$ V       cout << "删除元素 2 后的红黑树：" << endl;
/ F( {5 h- a3 K7 Z* k2 J+ `       tree.inorder();
! n4 g- Z5 Y9 t5 A
8 d8 m' w- i, x% p, `$ K* b       // 析构/ d( ^& r& d: q6 D# d& x
      tree.~bst();) ?  Z9 U' c) V) w2 i
: R; p+ J+ d# M* O9 [) B
      getchar();
$ H5 g* o0 {( i       return 0;+ v- k& s/ N! U& N5 ?' |, V
}
+ u9 N6 e( W# H; H! s% ?4 q! ?2 [7 h* R& d8 h  q0 C3 f5 h9 A
! d1 r% ^* ?  r. X' u' d1 z- w- F5 L
9 B树/B+树
在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。
                           ——维基百科
* N/ j* }0 s) h7 Q# \
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)的子树；
所有叶子结点位于同一层；6 Y, h. R$ a0 K9 |
+ q4 f6 {! _! N  X4 R

如：（M=3）
算法思路：
从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；
关键字集合分布在整颗树中；
任何一个关键字出现且只出现在一个结点中；
搜索有可能在非叶子结点结束；
其搜索性能等价于在关键字全集内做一次二分查找；
自动层次控制；3 }5 C- W& C) E+ N+ P; z' O
  g% U  h: Z0 {& L$ l* x3 ?1 z

代码：
BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)
( I3 j% l8 B; y{- F1 m/ n/ `" J6 j
int i = 0;  j4 l5 x& {) v+ W
while (i < tree->keynum && key > tree->key)% x" e9 |# w" |1 V4 n- T' ~
{7 Y# X  D/ T* p$ x+ l- H9 t
      ++i;6 X6 e, i/ |% Z! E; K+ i
}0 d/ Y! x7 ?: {; V
4 p! Z% x# e7 f+ N! q
// 查找关键字
7 n, m% k: A7 I" u* l if (i < tree->keynum && tree->key == key)" u/ j8 D/ I* D0 }# {+ \
{' y, s$ a8 G8 D9 j
      *pos = i;
# d5 j; }! b: I5 H! n       return tree;
9 S; L5 x7 P7 z) d# v' z }
! w# G* r) W% m" O/ [
/ K# {" J6 @- d# t% z // tree 为叶子节点，找不到 key，查找失败返回
8 A+ G6 ?7 ^0 J& ~; t if (tree->isLeaf)2 K; C( i5 D& a; m
{
, K: o% o  r6 k9 i. c# q) N$ {       return NULL;3 S8 X5 A5 F6 w0 z) {7 J# A
}
3 T5 D, }8 _. D: q5 F( ~# l 1 L' n8 A9 d/ Y1 [% D0 S, d
// 节点内查找失败，但 tree->key[i - 1]< key < tree->key，
, y# X' ~0 s0 P: h6 I# T9 \ // 下一个查找的结点应为 child8 w; f. k5 K" F: m; f6 [1 _  V. d) X
9 v. _, I; Q& k8 A/ f4 m; e6 g
// 从磁盘读取第 i 个孩子的数据) H9 Q# a# m6 c
disk_read(&tree->child);9 _8 r2 Q8 k# z& a7 O; `

4 |) r2 v$ M5 I$ M( x // 递归地继续查找于树 tree->child
1 n1 ~5 G  w' {6 `  z+ a! O return BTree_recursive_search(tree->child, key, pos);& x$ R7 D+ E0 v
}
: E; F/ E' M/ W  m9 [" ?% ]; w
B+树：
B+树是B树的变体，也是一种多路搜索树：
其定义基本与B-树同，除了：
非叶子结点的子树指针与关键字个数相同；
非叶子结点的子树指针P，指向关键字值属于[K, K[i+1])的子树, B树是开区间
为所有叶子结点增加一个链指针;
所有关键字都在叶子结点出现；
# v! a- H5 g$ F% T6 v- D; e2 ^# d3 |1 K1 a& U& [

如:（M=3）
1
算法思路：
B+的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；
所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
不可能在非叶子结点命中；
非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
更适合文件索引系统；
, N. [$ ?% `" E) s+ }