درخت جستجوی دودویی بهینه

درخت جستجوی دودویی بهینه

Msmas.blogfa.com

// Optimal binary search tree

# include <stdio.h>

# define MAXKEYS 30

int n; // number of keys

int key[MAXKEYS+1];

float p[MAXKEYS+1]; // probability of hitting key i

float q[MAXKEYS+1];

float c[MAXKEYS+1][MAXKEYS+1]; // cost of subtree

int r[MAXKEYS+1][MAXKEYS+1]; // root of subtree

float w[MAXKEYS+1][MAXKEYS+1]; // accumulated p and q

void opttree();

void Buildtree(int,int);

//*****************************

void main()

{

int i,j;

n=3;

p[1]=0.7;

p[2]=0.2;

p[3]=0.1;

//p[4]=0.45;

//p[5]=0.12;

for (i=1;i<=n;i++)

  key[i]=i;

for (i=0;i<=n;i++)

{

  printf("w[%d][%d]=%2.2f\n",i,i,w[i][i]);

  for (j=i+1;j<=n;j++)

  {

             w[i][j]=w[i][j-1]+p[j];

             printf("w[%d][%d]=%2.2f\n",i,j,w[i][j]);

  }

}

opttree();

printf("Average probe length is %2.2f\n",c[0][n]);

printf("trees in parenthesized prefix\n");

for (i=0;i<=n;i++)

  for (j=0;j<=n-i;j++)

  {

    printf("c(%d,%d) cost %2.2f ",j,j+i,c[j][j+i]);

    Buildtree(j,j+i);

    printf("\n");

  }

}

//*********************

void opttree()

{

float x,min;

int i,j,k,h,m;

for (i=0;i<n;i++)

{

  j=i+1;

  c[i][j]=w[i][j];

  r[i][j]=j;

}

for (h=2;h<=n;h++)

  for (i=0;i<=n-h;i++)

  {

    j=i+h;

    m=r[i][j-1];

    min=c[i][m-1]+c[m][j];

    for (k=m+1;k<=r[i+1][j];k++)

    {

      x=c[i][k-1]+c[k][j];

      if (x<min)

      {

        m=k;

        min=x;

      }

    }

    c[i][j]=min+w[i][j];

    r[i][j]=m;

  }

}

//*********************

void Buildtree(int i,int j)

// prints optimal binary search tree

{

if (i<j)

{

  printf("%d",key[r[i][j]]);

  if (i<r[i][j]-1 && r[i][j]<j)

  {

    printf("(");

             Buildtree(i,r[i][j]-1);

    printf(",");

             Buildtree(r[i][j],j);

    printf(")");

  }

  else if (i<r[i][j]-1)

  {

    printf("(");

             Buildtree(i,r[i][j]-1);

    printf(",");

    printf(")");

  }

  else if (r[i][j]<j)

  {

    printf("(");

    printf(",");

             Buildtree(r[i][j],j);

    printf(")");

  }

}

}