// AVLTree.cpp
//
#include "AVLTree.h"
#include <iostream>
#include <list>
using namespace std ;
void AVLTREE::create()
{
while (false != append())
{
}//while
return ;
}
void AVLTREE::reset()
{
reset_(root) ;
}
void AVLTREE::del(DATA data)
{
}
bool AVLTREE::append()
{
NODE* pNode = getInput_() ;
if (NULL == pNode)
{
return false ;
}//if
if (false != isEmpty_())
{
initRoot_(pNode) ;
}
else
{
NODE* p = append_(pNode) ;
if (NULL == p)
{
return true ;
}//if
}//if
return true ;
}
void AVLTREE::show()
{
if (false != isEmpty_())
{
cout <<STR_EMPTY <<endl ;
return ;
}//if
list<NODE* > l ;
l.push_back(root) ;
l.push_back(NULL) ; // push a newline
NODE* p = NULL ;
while (0 != l.size())
{
p = l.front() ;
l.pop_front() ;
if (NULL == p)
{
cout <<endl ;
continue ;
}//if
#ifdef DEBUG
cout <<p->data <<':' <<p->height <<' ' ;
#else
cout <<*(p->data) <<' ' ;
#endif
if (NULL != p->lChild)
{
l.push_back(p->lChild) ;
}//if
if (NULL != p->rChild)
{
l.push_back(p->rChild) ;
}//if
if (NULL == l.front()) // display in different level
{
l.push_back(NULL) ; // push a NULL pointer to indicate a newline
}
}//while
cout <<endl ;
return ;
}
// logic
void AVLTREE::LTurn_(NODE*& turnRoot)
{
if (NULL == turnRoot)
{
return ;
}//if
NODE* newRoot = turnRoot->rChild ;
if (LEFT == leftRight_(turnRoot))
{
turnRoot->parent->lChild = newRoot ;
}
else if (RIGHT == leftRight_(turnRoot))
{
turnRoot->parent->rChild = newRoot ;
}//if
newRoot->parent = turnRoot->parent ;
if (NULL != newRoot->lChild)
{
turnRoot->rChild = newRoot->lChild ;
}
else
{
turnRoot->rChild = NULL ;
}//if
newRoot->lChild = turnRoot ;
turnRoot->parent = newRoot ;
if (root == turnRoot) // if root has changed
{
root = newRoot ;
}//if
// set height to 0
newRoot->height = 0 ;
turnRoot->height = 0 ;
return ;
}
void AVLTREE::RTurn_(NODE*& turnRoot)
{
if (NULL == turnRoot)
{
return ;
}//if
NODE* newRoot = turnRoot->lChild ;
if (LEFT == leftRight_(turnRoot))
{
turnRoot->parent->lChild = newRoot ;
}
else if (RIGHT == leftRight_(turnRoot))
{
turnRoot->parent->rChild = newRoot ;
}//if
newRoot->parent = turnRoot->parent ;
if (NULL != newRoot->rChild)
{
turnRoot->lChild = newRoot->rChild ;
}
else
{
turnRoot->lChild = NULL ;
}//if
newRoot->rChild = turnRoot ;
turnRoot->parent = newRoot ;
if (root == turnRoot) // if root has changed
{
root = newRoot ;
}//if
// set height to 0
newRoot->height = 0 ;
turnRoot->height = 0 ;
return ;
}
NODE* AVLTREE::append_(NODE*& newNode)
{
NODE* p = searchParent_(newNode) ; // find a node where to insert the newNode
if (NULL == p)
{
return NULL ;
}//if
newNode->parent = p ;
if (newNode->data < p->data)
{
p->lChild = newNode ;
adjust_(p->lChild, -1) ;
}
else if (newNode->data > p->data)
{
p->rChild = newNode ;
adjust_(p->rChild, 1) ;
}
else
{
return NULL ;
}//if
return newNode ;
}
void AVLTREE::initRoot_(NODE*& newNode)
{
root = newNode ;
return ;
}
void AVLTREE::adjust_(NODE*& cur, int inc)
{
NODE* tRoot = searchTRoot_(cur, inc) ;
if (NULL == tRoot) // no node needs turning
{
return ;
}//if
#ifdef DEBUG
cout <<tRoot->data <<" needs turning" <<endl ;
#endif
#ifdef ADJUST
DIRECTION dir = analysisDirect_(tRoot, cur) ;
switch (dir)
{
case L:
{
LTurn_(tRoot) ;
break ;
}
case R:
{
RTurn_(tRoot) ;
break ;
}
case LR:
{
LTurn_(tRoot->lChild) ;
RTurn_(tRoot) ;
break ;
}
case RL:
{
RTurn_(tRoot->rChild) ;
LTurn_(tRoot) ;
break ;
}
default:
{
break ;
}
}//switch
#endif
return ;
}
NODE* AVLTREE::searchTRoot_(NODE*& cur, int inc)
{
NODE* temp = cur ;
if (NULL == temp)
{
return NULL ;
}//if
NODE* p = NULL ;
while (NULL != temp)
{
temp = temp->parent ;
p = _incHeight(temp, inc) ;
if (NULL != p)
{
return p ;
}//if
}//while
return NULL ;
}
DIRECTION AVLTREE::analysisDirect_(NODE*& tRoot, NODE*& cur)
{
if (2 == tRoot->height)
{
if (1 == tRoot->rChild->height)
{
return L ;
}
else if (-1 == tRoot->rChild->height)
{
return RL ;
}//if
}
else if (-2 == tRoot->height)
{
if (1 == tRoot->lChild->height)
{
return LR ;
}
else if (-1 == tRoot->lChild->height)
{
return R ;
}//if
}//if
return ERR_DIR ;
}
NODE* AVLTREE::searchParent_(NODE*& cur) const
{
if (NULL == cur)
{
return NULL ;
}//if
NODE* p = root ;
bool left = false ;
while (NULL != p)
{
if (cur->data < p->data)
{
if (NULL == p->lChild)
{
return p ;
}
else
{
p = p->lChild ;
}//if
}
else if (cur->data > p->data)
{
if (NULL == p->rChild)
{
return p ;
}
else
{
p = p->rChild ;
}//if
}
else
{
return NULL ;
}//if
}//while
return p ;
}
NODE* AVLTREE::getInput_()
{
DATA data ;
cin >>data ;
if (END == data) // end of input
{
return NULL ;
}//if
return _newNode(data) ;
}
void AVLTREE::reset_(NODE*& root)
{
if (NULL == root)
{
_delNode(root) ;
}//if
reset_(root->lChild) ;
reset_(root->rChild) ;
return ;
}
bool AVLTREE::isEmpty_()
{
if (NULL == root)
{
return true ;
}//if
return false ;
}
LEFTRIGHT AVLTREE::leftRight_(NODE*& p)
{
if (NULL == p)
{
return ERR_CHI ;
}//if
if (NULL == p->parent)
{
return ERR_CHI ;
}//if
NODE*& parent = p->parent ;
if (parent->lChild == p)
{
return LEFT ;
}
else if (parent->rChild == p)
{
return RIGHT ;
}
else
{
return ERR_CHI ;
}//if
return ERR_CHI ;
}
// implementation
NODE* AVLTREE::_newNode(DATA data)
{
NODE* p = new NODE() ;
#ifdef DEBUG
p->data = data ;
#else
*(p->data) = data ;
#endif
return p ;
}
void AVLTREE::_delNode(NODE*& p)
{
delete p ;
p = NULL ;
return ;
}
NODE* AVLTREE::_incHeight(NODE*& cur, int inc)
{
if (NULL == cur)
{
return NULL ;
}//if
cur->height += inc ;
if (2 > cur->height && -2 < cur->height)
{
return NULL ;
}//if
return cur ; // if we find any node whose height is unnormal , we return it
}
