KhairDigital11: program C++ : implement AVL Tree & its Operations

#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#define FALSE 0
#define TRUE 1
struct AVLNode
{
int data ;
int balfact ;
AVLNode *left ;
AVLNode *right ;
} ;

class avltree
{
private :
AVLNode *root ;
public :
avltree( ) ;
AVLNode* insert ( int data, int *h ) ;
static AVLNode* buildtree ( AVLNode *root, int data, int *h ) ;
void display( AVLNode *root ) ;
AVLNode* deldata ( AVLNode* root, int data, int *h ) ;
static AVLNode* del ( AVLNode *node, AVLNode* root, int *h ) ;
static AVLNode* balright ( AVLNode *root, int *h ) ;
static AVLNode* balleft ( AVLNode* root, int *h ) ;
void setroot ( AVLNode *avl ) ;
~avltree( ) ;
static void deltree ( AVLNode *root ) ;
} ;
avltree::avltree( )
{
root=NULL;
}
AVLNode* avltree::insert(int data, int *h )
{
root = buildtree ( root, data, h ) ;
return root ;
}
AVLNode* avltree :: buildtree ( AVLNode *root, int data, int *h )
{
AVLNode *node1, *node2 ;

if ( root == NULL )
{
root = new AVLNode ;
root -> data = data ;
root -> left = NULL ;
root -> right = NULL ;
root -> balfact = 0 ;
*h = TRUE ;
return ( root ) ;
}
if ( data < root -> data )
{
root -> left = buildtree ( root -> left, data, h ) ;

// If left subtree is higher
if ( *h )
{
   switch ( root -> balfact )
   {
    case 1 :
     node1 = root -> left ;
     if ( node1 -> balfact == 1 )
     {
      cout << "\nRight rotation.\n" ;
      root -> left = node1 -> right ;
      node1 -> right = root ;
      root -> balfact = 0 ;
      root = node1 ;
     }
     else
     {
      cout << "\nDouble rotation, left then right." ;
      node2 = node1 -> right ;
      node1 -> right = node2 -> left ;
      node2 -> left = node1 ;
      root -> left = node2 -> right ;
      node2 -> right = root ;
      if ( node2 -> balfact == 1 )
       root -> balfact = -1 ;
      else
       root -> balfact = 0 ;
      if ( node2 -> balfact == -1 )
       node1 -> balfact = 1 ;
      else
       node1 -> balfact = 0 ;
      root = node2 ;
     }
     root -> balfact = 0 ;
     *h = FALSE ;
     break ;

    case 0 :
     root -> balfact = 1 ;
     break ;
    case -1 :
     root -> balfact = 0 ;
     *h = FALSE ;
   }
}
}

if ( data > root -> data )
{
root -> right = buildtree ( root -> right, data, h ) ;

if ( *h )
{
   switch ( root -> balfact )
   {
    case 1 :
     root -> balfact = 0 ;
     *h = FALSE ;
     break ;
    case 0 :
     root -> balfact = -1 ;
     break ;
    case -1 :
     node1 = root -> right ;
     if ( node1 -> balfact == -1 )
     {
      cout << "\nLeft rotation.\n" ;
      root -> right = node1 -> left ;
      node1 -> left = root ;
      root -> balfact = 0 ;
      root = node1 ;
     }
     else
     {
      cout << "\nDouble rotation, right then left." ;
    node2 = node1 -> left ;
      node1 -> left = node2 -> right ;
      node2 -> right = node1 ;
      root -> right = node2 -> left ;
      node2 -> left = root ;
      if ( node2 -> balfact == -1 )
       root -> balfact = 1 ;
      else
       root -> balfact = 0 ;
      if ( node2 -> balfact == 1 )
       node1 -> balfact = -1 ;
      else
       node1 -> balfact = 0 ;
      root = node2 ;
     }
     root -> balfact = 0 ;
     *h = FALSE ;
   }
}
}
return ( root ) ;
}
void avltree :: display ( AVLNode* root )
{
if ( root != NULL )
{
display ( root -> left ) ;
cout << root -> data << "\t" ;
display ( root -> right ) ;
}
}
AVLNode* avltree :: deldata ( AVLNode *root, int data, int *h )
{
AVLNode *node ;
if ( root -> data == 13 )
cout << root -> data ;
if ( root == NULL )
{
cout << "\nNo such data." ;
return ( root ) ;
}
else
{
if ( data < root -> data )
{
   root -> left = deldata ( root -> left, data, h ) ;
   if ( *h )
    root = balright ( root, h ) ;
}
else
{
   if ( data > root -> data )
   {
    root -> right = deldata ( root -> right, data, h ) ;
    if ( *h )
     root = balleft ( root, h ) ;
   }
   else
   {
    node = root ;
    if ( node -> right == NULL )
    {
     root = node -> left ;
     *h = TRUE ;
     delete ( node ) ;
    }
    else
    {
     if ( node -> left == NULL )
     {
      root = node -> right ;
      *h = TRUE ;
      delete ( node ) ;
     }
     else
     {
      node -> right = del ( node -> right, node, h ) ;
      if ( *h )
       root = balleft ( root, h ) ;
     }
    }
   }
}
}
return ( root ) ;
}
AVLNode* avltree :: del ( AVLNode *succ, AVLNode *node, int *h )
{
AVLNode *temp = succ ;

if ( succ -> left != NULL )
{
succ -> left = del ( succ -> left, node, h ) ;
if ( *h )
   succ = balright ( succ, h ) ;
}
else
{
temp = succ ;
node -> data = succ -> data ;
succ = succ -> right ;
delete ( temp ) ;
*h = TRUE ;
}
return ( succ ) ;
}
AVLNode* avltree :: balright ( AVLNode *root, int *h )
{
AVLNode *temp1, *temp2 ;
switch ( root -> balfact )
{
case 1 :
   root -> balfact = 0 ;
   break ;
case 0 :
   root -> balfact = -1 ;
   *h = FALSE ;
   break ;
case -1 :
   temp1 = root -> right ;
   if ( temp1 -> balfact <= 0 )
   {
    cout << "\nLeft rotation.\n";
    root -> right = temp1 -> left ;
    temp1 -> left = root ;
    if ( temp1 -> balfact == 0 )
    {
     root -> balfact = -1 ;
     temp1 -> balfact = 1 ;
     *h = FALSE ;
    }
    else
    {
     root -> balfact = temp1 -> balfact = 0 ;
    }
   root = temp1 ;
   }
   else
   {
    cout << "\nDouble rotation, right then left." ;
    temp2 = temp1 -> left ;
    temp1 -> left = temp2 -> right ;
    temp2 -> right = temp1 ;
    root -> right = temp2 -> left ;
    temp2 -> left = root ;
    if ( temp2 -> balfact == -1 )
     root -> balfact = 1 ;
    else
     root -> balfact = 0 ;
    if ( temp2 -> balfact == 1 )
     temp1 -> balfact = -1 ;
    else
     temp1 -> balfact = 0 ;
    root = temp2 ;
    temp2 -> balfact = 0 ;
   }
}
return ( root ) ;
}
AVLNode* avltree :: balleft ( AVLNode *root, int *h )
{
AVLNode *temp1, *temp2 ;
switch ( root -> balfact )
{
case -1 :
   root -> balfact = 0 ;
   break ;

case 0 :
   root -> balfact = 1 ;
   *h = FALSE ;
   break ;

case 1 :
   temp1 = root -> left ;
   if ( temp1 -> balfact >= 0 )
   {
    cout << "\nRight rotation." ;
    root -> left = temp1 -> right ;
    temp1 -> right = root ;

    if ( temp1 -> balfact == 0 )
    {
     root -> balfact = 1 ;
     temp1 -> balfact = -1 ;
     *h = FALSE ;
    }
    else
    {
     root -> balfact = temp1 -> balfact = 0 ;
    }
    root = temp1 ;
   }
   else
   {
    cout << "\nDouble rotation, left then right." ;
    temp2 = temp1 -> right ;
    temp1 -> right = temp2 -> left ;
    temp2 -> left = temp1 ;
    root -> left = temp2 -> right ;
    temp2 -> right = root ;
    if ( temp2 -> balfact == 1 )
     root -> balfact = -1 ;
    else
     root -> balfact = 0 ;
    if ( temp2-> balfact == -1 )
     temp1 -> balfact = 1 ;
    else
     temp1 -> balfact = 0 ;
    root = temp2 ;
    temp2 -> balfact = 0 ;
   }
}
return ( root ) ;
}
void avltree :: setroot ( AVLNode *avl )
{
root = avl ;
}
avltree :: ~avltree( )
{
deltree ( root ) ;
}

void avltree :: deltree ( AVLNode *root )
{
if ( root != NULL )
{
deltree ( root -> left ) ;
deltree ( root -> right ) ;
}
delete ( root ) ;
}
int main( )
{
avltree at ;
AVLNode *avl = NULL ;
int h ;
avl = at.insert(20,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(6,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(29,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(5,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(12,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(25,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(32,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(10,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(15,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(27,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(13,&h);
at.setroot(avl);
at.display(avl);
cout<<endl<<"\nAVL tree:\n";
at.display(avl);
avl = at.deldata(avl, 20, &h);
at.setroot(avl);
avl = at.deldata(avl, 12, &h);
at.setroot(avl);
cout<<"\n\npohon AVL setelah penghapusan 20 dan 12:\n" ;
at.display(avl);
cout<<endl;
avl = at.insert(2,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(28,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(20,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.insert(8,&h);
at.setroot(avl);
at.display(avl);
cout<<endl;
avl = at.deldata(avl, 15, &h);
at.setroot(avl);
avl = at.deldata(avl, 6, &h);
at.setroot(avl);
avl = at.deldata(avl, 5, &h);
at.setroot(avl);
avl = at.deldata(avl, 13, &h);
at.setroot(avl);
avl = at.deldata(avl, 10, &h);
at.setroot(avl);
cout<<"\n\nPohon AVL setelah penghapusan 15,6,5,13 dan 10:\n" ;
at.display(avl);
cout<<endl<<endl;
avl = at.insert(22,&h);
at.setroot(avl);
at.display(avl);
avl = at.insert(23,&h);
at.setroot(avl);
cout<<"\n\nAVL Tree Akhir:\n";
at.display(avl);
getch();
}

KhairDigital11

Sabtu, 14 Januari 2012

program C++ : implement AVL Tree & its Operations

Tidak ada komentar:

Posting Komentar