ecs.cpp

利用平衡二叉树实现一个动态查找表 实现动态查找表的三种基本功能:查找、插入和删除

//平衡二叉数的c实现
#include <stdio.h>
#include <stdlib.h>
#include <assert.h> 

#define LH 1
#define EH 0
#define RH -1 

typedef int ElemType; 

typedef struct BSTNode {
 ElemType data;
 int  bf;
 struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree; 

int Equal(ElemType *a, ElemType *b)
{
 return *a == *b ? 1 : 0;
}
int Less(ElemType *a, ElemType *b)
{
 return *a < *b ? 1 : 0;
}
int Great(ElemType *a, ElemType *b)
{
 return *a > *b ? 1 : 0;
}
void ElemCopy(ElemType *data, ElemType *e)
{
 *data = *e;
}
/*
** rotate the tree p with type LL.
*/
void R_Rotate(BSTree *p) 
{
 BSTree t = (*p)->lchild; 

 (*p)->lchild = t->rchild;
 t->rchild = *p;
 *p = t;
}
/*
** rotate the tree p with type RR.
*/
void L_Rotate(BSTree *p)
{
 BSTree t = (*p)->rchild; 

 (*p)->rchild = t->lchild;
 t->lchild = *p;
 *p = t;
}
/*
** left sub-tree out of balance.
*/
void LeftBalance(BSTree *T)
{
 BSTree ptree = (*T)->lchild;
 BSTree t; 

 switch (ptree->bf) {
 case LH:
  ptree->bf = (*T)->bf = EH;
  R_Rotate(T);
  break;
 case RH:
  t = ptree->rchild;
  switch (t->bf) {
  case LH:
   ptree->bf = EH; 
   (*T)->bf = RH;
   break;
  case EH:
   ptree->bf = (*T)->bf = EH;
   break;
  case RH:
   ptree->bf = LH;
   (*T)->bf = EH;
   break;
  }
  t->bf = EH;
  L_Rotate(&((*T)->lchild)); 
  R_Rotate(T);
  break;
 }
}
/*
** right sub-tree out of balance.
*/
void RightBalance(BSTree *T)
{
 BSTree ptree = (*T)->rchild;
 BSTree t; 

 switch (ptree->bf) {
 case LH:
  t = ptree->lchild;
  switch (t->bf) {
  case LH:
   (*T)->bf = EH;
   ptree->bf = RH;
   break;
  case EH:
   (*T)->bf = ptree->bf =  EH; 
   break;
  case RH:
   (*T)->bf = LH;
   ptree->bf = EH;
   break;
  }
  t->bf = EH;
  R_Rotate(&((*T)->rchild));
  L_Rotate(T);
  break;
 case RH:
  (*T)->bf = ptree->bf = EH; 
  L_Rotate(T);
  break;
 }
}
int InsertAVL(BSTree *T, ElemType *e, int *taller)
{
 if (!*T) {
  *T = (BSTree)malloc(sizeof(BSTNode));
  assert(*T);
  (*T)->lchild = (*T)->rchild = NULL; 
  (*T)->bf = 0;
  ElemCopy(&((*T)->data), e);
  *taller = 1;
 } else {
  if (Equal(e, &((*T)->data))) {
   *taller = 0;
   return 0;
  } else if (Less(e, &((*T)->data))) {
   /* Insert To left tree */
   if (!InsertAVL(&((*T)->lchild), e, taller)) return 0;
   if (*taller) {
    switch ((*T)->bf) {
    case LH:
     LeftBalance(T);
     *taller = 0;
     break; 
    case EH:
     (*T)->bf = LH;  
     *taller = 1;
     break;
    case RH:
     (*T)->bf = EH;
     *taller = 0;
     break;
    }
   }
   
  } else {
   /* Insert to right tree */ 
   if (!InsertAVL(&((*T)->rchild), e, taller)) return 0;
   switch ((*T)->bf) {
   case LH:
    (*T)->bf = EH;
    *taller = 0;
    break;
   case EH:
    (*T)->bf = RH;
    *taller = 1; 
    break;
   case RH:
    RightBalance(T);
    *taller = 0;
    break;
   }
  }
 }
 return 1;
}
void DestroyAVL(BSTree *t)
{
 if (*t) {
  DestroyAVL(&((*t)->lchild));
  DestroyAVL(&((*t)->rchild));
  *t = NULL;
 }
}
int main(void)
{
 BSTree t = NULL;
 int m, taller; 

 while (scanf("%d", &m) != EOF) { 
  InsertAVL(&t, &m, &taller);
 }
 return 0;
}