/*AATree.c -- AA树实现文件*/
#include "AATree.h"
/*全局变量声明*/
static Node * NullNode &＃61; NULL ;
/*局部函数声明*/
static Node * singleRotateWithLeft (Node * const pn) ;
static Node * singleRotateWithRight (Node * const pn) ;
static Node * skew (Node * pn) ;
static Node * split (Node * pn) ;
static void release (AATree aat) ;
/*接口函数定义*/
Node * Initialize_A (void)
{
if (NULL &＃61;&＃61; NullNode)
{
NullNode &＃61; (Node *) malloc (sizeof (Node)) ;
if (NULL &＃61;&＃61; NullNode)
return NULL ;
NullNode -> left &＃61; NullNode -> right &＃61; NullNode ;
NullNode -> level &＃61; 0 ;
}
return NullNode ;
}
AATree Insert_A (AATree aat, const Item item)
{
if (aat &＃61;&＃61; NullNode)
{
/*Create and return a one-node tree.*/
aat &＃61; (Node *) malloc (sizeof (Node)) ;
if (NULL &＃61;&＃61; aat)
puts ("Out of space.") ;
else
{
aat -> item &＃61; item ;
aat -> level &＃61; 1 ;
aat -> left &＃61; aat -> right &＃61; NullNode ;
}
return aat ;
}
else if (item item)
aat -> left &＃61; Insert_A (aat -> left, item) ;
else if (item > aat -> item)
aat -> right &＃61; Insert_A (aat -> right, item) ;
/*Otherwise it&＃39;s a duplicate; do nothint.*/
aat &＃61; skew (aat) ;
aat &＃61; split (aat) ;
return aat ;
}
BOOL Find_A (AATree aat, const Item item)
{
Node * scan &＃61; aat ;
while (scan !&＃61; NullNode)
{
if (item item)
scan &＃61; scan -> left ;
else if (item > scan -> item)
scan &＃61; scan -> right ;
else
return TRUE ;
}
return FALSE ;
}
int Count_A (AATree aat)
{
static count &＃61; 0 ;
if (aat !&＃61; NullNode)
{
Count_A (aat -> left) ;
Count_A (aat -> right) ;
count&＃43;&＃43; ;
return count ;
}
else
return 0 ;
}
AATree Delete_A (AATree aat, const Item item)
{
static Node * deletePtr, * lastPtr ;
if (aat !&＃61; NullNode)
{
/*Step 1:Search down tree.*/
/*Set lastPtr and deletePtr.*/
lastPtr &＃61; aat ;
if (item item)
aat -> left &＃61; Delete_A (aat -> left, item) ;
else
{
deletePtr &＃61; aat ;
aat -> right &＃61; Delete_A (aat -> right, item) ;
}
/*Step 2:If at the bottom of the tree and*/
/*item is present, we delete it.*/
if (aat &＃61;&＃61; lastPtr)
{
if (deletePtr !&＃61; NullNode && item &＃61;&＃61; deletePtr -> item)
{
deletePtr -> item &＃61; aat -> item ;
deletePtr &＃61; NullNode ;
aat &＃61; aat -> right ;
free (lastPtr) ;
}
}
/*Step 3:Otherwise, we are not at the bottom.*/
/*Rebalance.*/
else
{
if (aat -> left -> level level - 1 ||
aat -> right -> level level - 1)
{
if (aat -> right -> level > --aat -> level)
aat -> right -> level &＃61; aat -> level ;
aat &＃61; skew (aat) ;
aat -> right &＃61; skew (aat -> right) ;
aat -> right -> right &＃61; skew (aat -> right -> right) ;
aat &＃61; split (aat) ;
aat -> right &＃61; split (aat -> right) ;
}
}
}
return aat ;
}
void Release_A (AATree aat)
{
Release_A (aat) ;
free (NullNode) ;
NullNode &＃61; NULL ;
}
/*局部函数定义*/
static Node * singleRotateWithLeft (Node * const pn)
{
Node * left ;
left &＃61; pn -> left ;
pn -> left &＃61; left -> right ;
left -> right &＃61; pn ;
return left ;
}
static Node * singleRotateWithRight (Node * const pn)
{
Node * right ;
right &＃61; pn -> right ;
pn -> right &＃61; right -> left ;
right -> left &＃61; pn ;
return right ;
}
static Node * skew (Node * pn)
{
if (pn -> left -> level &＃61;&＃61; pn -> level)
pn &＃61; singleRotateWithLeft (pn) ;
return pn ;
}
static Node * split (Node * pn)
{
if (pn -> right -> right -> level &＃61;&＃61; pn -> level)
{
pn &＃61; singleRotateWithRight (pn) ;
pn -> level&＃43;&＃43; ;
}
return pn ;
}
static void release (AATree aat)
{
if (aat !&＃61; NullNode)
{
release (aat -> left) ;
release (aat -> right) ;
free (aat) ;
}
}
京公网安备 11010802041100号