AVL樹C語言完整實現

AVL樹的介紹見http://www.linuxidc.com/Linux/2014-04/99733.htm，本文給出的是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);
}