#include
#include
#include
#include
#include

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;
}