AVL树C语言完整实现

AVL树C语言完整实现

AVL树的介绍见，本文给出的是AVL树的一种实现。
 
采用非递归方式，效率较好，经过常规测试。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <assert.h>

typedef enum
{
 EH = 0,
 LH = 1,
 RH = -1
}bh_t;

typedef enum
{
 FALSE = 0,
 TRUE = 1
}bool_t;

typedef int ElemType;

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

bool_t  searchAVL(BSTree root,ElemType key, BSTNode **parent)
{
 BSTNode *tmp = NULL;
 assert(root != NULL);
 *parent = root->parent;
 tmp = root;
 while(NULL != tmp)
 {
  if(tmp->key == key)
  {
   return TRUE;
  }

  *parent = tmp;
  if(tmp->key > key)
  {
   tmp = tmp->lchild;
  }
  else
  {
   tmp = tmp->rchild;
  }
 }
 return FALSE;
}

/* get the minimum node*/
BSTNode* minNode(BSTNode* root)
{
 if (root == NULL)
 {
  return NULL;
 }
 while (root->lchild != NULL)
 {
  root = root->lchild;
 }
 return root;
}

/* get the maximum node*/
BSTNode* maxNode(BSTNode* root)
{
 if (root == NULL)
 {
  return NULL;
 }
 while (root->rchild != NULL)
 {
  root = root->rchild;
 }
 return root;
}

/* get the previous node*/
BSTNode* preNode(BSTNode* target)
{
 if (target == NULL)
 {
  return NULL;
 }
 if (target->lchild != NULL)
 {
  return maxNode(target->lchild);
 }
 while ((target->parent!=NULL) && (target!=target->parent->rchild))
 {
  target = target->parent;
 }
 return target->parent;
}

/* get the next node*/
BSTNode* nextNode(BSTNode* target)
{
 if (target == NULL)
 {
  return NULL;
 }
 if (target->rchild != NULL)
 {
  return minNode(target->rchild);
 }
 while ((target->parent!=NULL) && (target!=target->parent->lchild))
 {
  target = target->parent;
 }
 return target->parent;
}

BSTNode* leftbalance(BSTNode* root, BSTNode* parent, BSTNode* child)
{
 BSTNode *cur;
 assert((parent != NULL)&&(child != NULL));
 /* LR */
 if (child->bf == RH)
 {
  cur = child->rchild;
  cur->parent = parent->parent;
  child->rchild = cur->lchild;
  if (cur->lchild != NULL)
  {
   cur->lchild->parent = child;
  }
  parent->lchild = cur->rchild;
  if (cur->rchild != NULL)
  {
   cur->rchild->parent = parent;
  }
  cur->lchild = child;
  cur->rchild = parent;
  child->parent = cur;

  if (parent->parent != NULL)
  {
   if (parent->parent->lchild == parent)
   {
    parent->parent->lchild = cur;
   }
   else
   {
    parent->parent->rchild = cur;
   }
  }
  else
  {
   root = cur;
  }
  parent->parent = cur;
  if (cur->bf == EH)
  {
   parent->bf = EH;
   child->bf = EH;
  }
  else if (cur->bf == RH)
  {
   parent->bf = EH;
   child->bf = LH;
  }
  else
  {
   parent->bf = RH;
   child->bf = EH;
  }
  cur->bf = EH;
 }
 /* LL */
 else
 {
  child->parent = parent->parent;
  parent->lchild = child->rchild;
  if (child->rchild != NULL)
  {
   child->rchild->parent = parent;
  }
  child->rchild = parent;
  if (parent->parent != NULL)
  {
   if (parent->parent->lchild == parent)
   {
    parent->parent->lchild = child;
   }
   else
   {
    parent->parent->rchild = child;
   }
  }
  else
  {
   root = child;
  }
  parent->parent = child;
  /* when insert */
  if (child->bf == LH)
  {
   child->bf = EH;
   parent->bf = EH;
  }
  /* when delete*/
  else
  {
   child->bf = RH;
   parent->bf = LH;
  }
 }
 return root;
}

BSTNode* rightbalance(BSTNode* root, BSTNode* parent, BSTNode* child)
{
 BSTNode *cur;
 assert((parent != NULL)&&(child != NULL));
 /* RL */
 if (child->bf == LH)
 {
  cur = child->lchild;
  cur->parent = parent->parent;
  child->lchild = cur->rchild;
  if (cur->rchild != NULL)
  {
   cur->rchild->parent = child;
  }
  parent->rchild = cur->lchild;
  if (cur->lchild != NULL)
  {
   cur->lchild->parent = parent;
  }
  cur->lchild = parent;
  cur->rchild = child;
  child->parent = cur;
  if (parent->parent != NULL)
  {
   if (parent->parent->lchild == parent)
   {
    parent->parent->lchild = cur;
   }
   else
   {
    parent->parent->rchild = cur;
   }
  }
  else
  {
   root = cur;
  }
  parent->parent = cur;
  if (cur->bf == EH)
  {
   parent->bf = EH;
   child->bf = EH;
  }
  else if (cur->bf == LH)
  {
   parent->bf = EH;
   child->bf = RH;
  }
  else
  {
   parent->bf = LH;
   child->bf = EH;
  }
  cur->bf = EH;
 }
 /* RR */
 else
 {
  child->parent = parent->parent;
  parent->rchild = child->lchild;
  if (child->lchild != NULL)
   child->lchild->parent = parent;
  child->lchild = parent;
  if (parent->parent != NULL)
  {
   if (parent->parent->lchild == parent)
   {
    parent->parent->lchild = child;
   }
   else
   {
    parent->parent->rchild = child;
   }
  }
  else
  {
   root = child;
  }
  parent->parent = child;
  /* when insert */
  if (child->bf == RH)
  {
   child->bf = EH;
   parent->bf = EH;
  }
  /* when delete*/
  else
  {
   child->bf = LH;
   parent->bf = RH;
  }
 }
 return root;
}

BSTNode* insertNode(ElemType key, BSTNode* root)
{
 BSTNode *parent = NULL, *cur = NULL, *child = NULL;
 assert (root != NULL);
 /* node exists*/
 if (searchAVL(root,key,&parent))
 {
  return root;
 }
 cur = (BSTNode*)malloc(sizeof(BSTNode));
 cur->parent = parent;
 cur->key = key;
 cur->lchild = NULL;
 cur->rchild = NULL;
 cur->bf = EH;
 if (key<parent->key)
 {
  parent->lchild = cur;
  child = parent->lchild;
 }
 else
 {
  parent->rchild = cur;
  child = parent->rchild;
 }
 /*get the minimax tree needed to be adjusted*/
 while ((parent != NULL))
 {
  if (child == parent->lchild)
  {
   if (parent->bf == RH)
   {
    parent->bf = EH;
    return root;
   }
   else if (parent->bf == EH)
   {
    root = leftbalance(root, parent, child);
    break;
   }
   else
   {
    parent->bf = LH;
    child = parent;
    parent = parent->parent;
   }
  }
  else
  {
   if (parent->bf == LH) //是右孩子，不会引起不平衡
   {
    parent->bf = EH;
    return root;
   }
   else if (parent->bf == RH) //是右孩子，并且引起parent的不平衡

   {
    root = rightbalance(root, parent, child);
    break;
   }
   else //是右孩子，并且可能引起parent的parent的不平衡
   {
    parent->bf = RH;
    child = parent;
    parent = parent->parent;
   }
  }
 }

 return root;
}

BSTNode* deleteNode(ElemType key, BSTNode* root)
{
 BSTNode *dNode=NULL, *parent=NULL, *child = NULL;
 ElemType temp;
 assert(root!=NULL);
 if (!searchAVL(root,key,&parent))
 {
  return root;
 }

 if (parent == NULL)
 {
  dNode = root;
 }
 else if ((parent->lchild!=NULL)&&(parent->lchild->key==key))
 {
  dNode = parent->lchild;
 }
 else
 {
  dNode = parent->rchild;
 }

 child = dNode;
 while ((child->lchild!=NULL)||(child->rchild!=NULL)) //确定需要删除的结点
 {
  if (child->bf == LH)
  {
   child = preNode(dNode);
  }
  else
  {
   child = nextNode(dNode);
  }
  temp = child->key;
  child->key = dNode->key;
  dNode->key = temp;
  dNode = child;
 }

 child = dNode;
 parent = dNode->parent;

 while ((parent != NULL)) //查找需要调整的最小子树
 {
  if (child == parent->lchild)
  {
   if (parent->bf == LH)
   {
    parent->bf = EH;
    child = parent;
    parent = parent->parent;
   }
   else if (parent->bf == RH)
   {
    child = parent->rchild;
    root = rightbalance(root, parent, child);
    break;
   }
   else
   {
    parent->bf = RH;
    break;
   }
  }
  else
  {
   if (parent->bf == RH)
   {
    parent->bf = EH;
    child = parent;
    parent = parent->parent;
   }
   else if (parent->bf == LH)
   {

    child = parent->lchild;
    root = leftbalance(root, parent, child);
    break;
   }
   else
   {
    parent->bf = LH;
    break;
   }
  }
 }
 if (dNode->parent != NULL)
 {
  if (dNode == dNode->parent->lchild)
  {
   dNode->parent->lchild = NULL;
  }
  else
  {
   dNode->parent->rchild = NULL;
  }
 }
 free(dNode);
 dNode = NULL;
 if (root == dNode)
 {
  root = NULL; //root被删除, 避免野指针
 }
 return root;
}

BSTNode* createAVL(int *data, int size)
{
 int i, j;
 BSTNode *root;
 if (size<1)
 {
  return NULL;
 }
 root = (BSTNode*)malloc(sizeof(BSTNode));
 root->parent = NULL;
 root->lchild = NULL;
 root->rchild = NULL;
 root->key = data[0];
 root->bf = 0;

 for(i=1;i<size;i++)
  root = insertNode(data[i], root);
 return root;
}

void destroyAVL(BSTNode* root)
{
 if (root != NULL)
 {
  destroyAVL(root->lchild);
  destroyAVL(root->rchild);
  free(root);
  root=NULL;
 }

}

void InOrderTraverse(BSTree root)
{
 if(NULL != root)
 {
  InOrderTraverse(root->lchild);
  printf("%d\t",root->key);
  InOrderTraverse(root->rchild);
 }
}

void PreOrderTraverse(BSTree root)
{
 if(NULL != root)
 {
  printf("%d\t",root->key);
  PreOrderTraverse(root->lchild);
  PreOrderTraverse(root->rchild);
 }
}

int main(int argc, char *argv[])
{
 int data[] = {1, 5, 7, 4, 3, 2, 11, 9, 10,100};
 BSTNode* root;
 root = createAVL(data, sizeof(data)/sizeof(data[0]));

 printf("\n++++++++++++++++++++++++++++\n");
 InOrderTraverse(root);
 printf("\n");
 PreOrderTraverse(root);

 root = deleteNode(5, root);
 printf("\n++++++++delete 5++++++++++\n");
 InOrderTraverse(root);
 printf("\n");
 PreOrderTraverse(root);

 root = deleteNode(3, root);
 printf("\n++++++++delete 3++++++++++\n");
 InOrderTraverse(root);
 printf("\n");
 PreOrderTraverse(root);

 root = deleteNode(1, root);
 printf("\n++++++++delete 1++++++++++\n");
 InOrderTraverse(root);
 printf("\n");
 PreOrderTraverse(root);

 root = deleteNode(7, root);
 printf("\n++++++++delete 7++++++++++\n");
 InOrderTraverse(root);
 printf("\n");
 PreOrderTraverse(root);

 root = deleteNode(4, root);
 printf("\n++++++++delete 4++++++++++\n");
 InOrderTraverse(root);
 printf("\n");
 PreOrderTraverse(root);

 root = deleteNode(2, root);
 printf("\n++++++++delete 2++++++++++\n");
 InOrderTraverse(root);
 printf("\n");
 PreOrderTraverse(root);
 printf("\n");

 destroyAVL(root);
}