please help e to complete the program

**trojan32** · 01-26-2013

Program to maintain an AVL tree.

Code:

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
 
#define FALSE 0
#define TRUE 1
 
struct AVLNode
{
    int data ;
    int balfact ;
    struct AVLNode *left ;
    struct AVLNode *right ;
} ;
 
struct AVLNode * buildtree ( struct AVLNode *, int, int * ) ;
struct AVLNode * deldata ( struct AVLNode *, int, int * ) ;
struct AVLNode * del ( struct AVLNode *, struct AVLNode *, int * ) ;
struct AVLNode * balright ( struct AVLNode *, int * ) ;
struct AVLNode * balleft ( struct AVLNode *, int * ) ;
void display ( struct AVLNode * ) ;
void deltree ( struct AVLNode * ) ;
 
void main( )
{
    struct AVLNode *avl = NULL ;
    int h ;
 
    clrscr( ) ;
 
    avl = buildtree ( avl, 20, &h ) ;
    avl = buildtree ( avl, 6, &h ) ;
    avl = buildtree ( avl, 29, &h ) ;
    avl = buildtree ( avl, 5, &h ) ;
    avl = buildtree ( avl, 12, &h ) ;
    avl = buildtree ( avl, 25, &h ) ;
    avl = buildtree ( avl, 32, &h ) ;
    avl = buildtree ( avl, 10, &h ) ;
    avl = buildtree ( avl, 15, &h ) ;
    avl = buildtree ( avl, 27, &h ) ;
    avl = buildtree ( avl, 13, &h ) ;
 
    printf ( "\nAVL tree:\n" ) ;
    display ( avl ) ;
 
    avl = deldata ( avl, 20, &h ) ;
    avl = deldata ( avl, 12, &h ) ;
 
    printf ( "\nAVL tree after deletion of a node:\n" ) ;
    display ( avl ) ;
 
    deltree ( avl ) ;
 
    getch( ) ;
}
 
/* inserts an element into tree */
struct AVLNode * buildtree ( struct AVLNode *root, int data, int *h )
{
    struct AVLNode *node1, *node2 ;
 
    if ( !root )
    {
        root = ( struct AVLNode * ) malloc ( sizeof ( struct 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 )
                    {
                        printf ( "\nRight rotation along %d.", root -> data ) ;
                        root -> left = node1 -> right ;
                        node1 -> right = root ;
                        root -> balfact = 0 ;
                        root = node1 ;
                    }
                    else
                    {
                        printf ( "\nDouble rotation, left along %d", 
                                                           node1 -> data ) ;
                        node2 = node1 -> right ;
                        node1 -> right = node2 -> left ;
                        printf ( " then right along %d.\n", root -> data ) ;
                        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 the right subtree is higher */
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 )
                    {
                        printf ( "\nLeft rotation along %d.", root -> data ) ;
                        root -> right = node1 -> left ;
                        node1 -> left = root ;
                        root -> balfact = 0 ;
                        root = node1 ;
                    }
                    else
                    {
                        printf ( "\nDouble rotation, right along %d", 
                                                           node1 -> data ) ;
                        node2 = node1 -> left ;
                        node1 -> left = node2 -> right ;
                        node2 -> right = node1 ;
                        printf ( " then left along %d.\n", root -> data ) ;
                        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 ) ;
}
 
/* deletes an item from the tree */
struct AVLNode * deldata ( struct AVLNode *root, int data, int *h )
{
    struct AVLNode *node ;
 
    if ( !root )
    {
        printf ( "\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 ;
                    free ( node ) ;
                }
                else
                {
                    if ( node -> left == NULL )
                    {
                        root = node -> right ;
                        *h = TRUE ;
                        free ( node ) ;
                    }
                    else
                    {
                        node -> right = del ( node -> right, node, h ) ;
                        if ( *h )
                            root = balleft ( root, h ) ;
                    }
                }
            }
        }
    }
    return ( root ) ;
}
 
struct AVLNode * del ( struct AVLNode *succ, struct AVLNode *node, int *h )
{
    struct 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 ;
        free ( temp ) ;
        *h = TRUE ;
    }
    return ( succ ) ;
}
 
/* balances the tree, if right sub-tree is higher */
struct AVLNode * balright ( struct AVLNode *root, int *h )
{
    struct AVLNode *node1, *node2 ;
 
    switch ( root -> balfact )
    {
        case 1:
            root -> balfact = 0 ;
            break;
 
        case 0:
            root -> balfact = -1 ;
            *h  = FALSE ;
            break;
 
        case -1:
            node1 = root -> right ;
            if ( node1 -> balfact <= 0 )
            {
                printf ( "\nLeft rotation along %d.", root -> data ) ;
                root -> right = node1 -> left ;
                node1 -> left = root ;
                if ( node1 -> balfact == 0 )
                {
                    root -> balfact = -1 ;
                    node1 -> balfact = 1 ;
                   *h = FALSE ;
                }
                else
                {
                    root -> balfact = node1 -> balfact = 0 ;
                }
                root = node1 ;
            }
            else
            {
                printf ( "\nDouble rotation, right along %d", node1 -> data );
                node2 = node1 -> left ;
                node1 -> left = node2 -> right ;
                node2 -> right = node1 ;
                printf ( " then left along %d.\n", root -> data );
                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 ;
                node2 -> balfact = 0 ;
            }
    }
    return ( root ) ;
}
 
/* balances the tree, if left sub-tree is higher */
struct AVLNode * balleft ( struct AVLNode *root, int *h )
{
    struct AVLNode *node1, *node2 ;
 
    switch ( root -> balfact )
    {
        case -1:
            root -> balfact = 0 ;
            break ;
 
        case 0:
            root -> balfact = 1 ;
            *h = FALSE ;
            break ;
 
        case 1:
            node1 = root -> left ;
            if ( node1 -> balfact >= 0 )
            {
                printf ( "\nRight rotation along %d.", root -> data ) ;
                root -> left = node1 -> right ;
                node1 -> right = root ;
                if ( node1 -> balfact == 0 )
                {
                    root -> balfact = 1 ;
                    node1 -> balfact = -1 ;
                    *h = FALSE ;
                }
                else
                {
                    root -> balfact = node1 -> balfact = 0 ;
                }
                root = node1 ;
            }
            else
            {
                printf ( "\nDouble rotation, left along %d", node1 -> data ) ;
                node2 = node1 -> right ;
                node1 -> right = node2 -> left ;
                node2 -> left = node1 ;
                printf ( " then right along %d.\n", root -> data ) ;
                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 ;
                node2 -> balfact = 0 ;
            }
    }
    return ( root ) ;
}
 
/* displays the tree in-order */
void display ( struct AVLNode *root )
{
    if ( root != NULL )
    {
        display ( root -> left ) ;
        printf ( "%d\t", root -> data ) ;
        display ( root -> right ) ;
    }
}
 
/* deletes the tree */
void deltree ( struct AVLNode *root )
{
    if ( root != NULL )
    {
        deltree ( root -> left ) ;
        deltree ( root -> right ) ;
    }
    free ( root ) ;
}

i want to insert this functions inside the program

Make Empty
This operation is for mainly intialization and can be used to destroy entire search tree also.

Code:

Tree *make_empty(Tree *t)
{
  if (t != NULL)
  {
    make_empty(t->left);
    make_empty(t->right);
    free(t);
    t = NULL;
  }
 
  return NULL;
}

i want to insert this functions inside the program
Height
Finds height of the tree

Code:

int height(Tree *t)
{
  if (t == NULL)
  {
    return -1;
  }
  else
  {
    return t->height;
  }
}

i want to insert this functions inside the program

Find
This operation returns a Tree node pointer in the search tree that has key X, or returns NULL if there is such node.
We make a recursive call on sub tree of the tree , either left or right, depending on the relationship of key X to the
element stored in the tree node

Code:

Tree *find(int elem, Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
 
  if (elem < t->element)
  {
    return find(elem, t->left);
  }
  else if (elem > t->element)
  {
    return find(elem, t->right);
  }
  else
  {
    return t;
  }
}

i want to insert this functions inside the program

FindMin
This operation returns the smallest element node in the tree, i.e. left most element of the tree

Code:

Tree *find_min(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->left == NULL)
  {
    return t;
  }
  else
  {
    return find_min(t->left);
  }
}

FindMax
This operation returns the biggest element node in the tree, i.e. right most element of the tree

Code:

Tree *find_max(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->right == NULL)
  {
    return t;
  }
  else
  {
    return find_max(t->right);
  }
}

Insert
This operation applies a Find operation on the tree, if its found, does nothing., otherwise,
insert the element at the last spot on the path traversed. After insertion, only nodes that are on the path from the insertion point to the root might have their balance altered because only those nodes have their subtrees altered. As we follow up the path and update the balancing information, we may find a node whose new balance voilates the AVL (balance) condition. We need to rebalance the tree to satisfy AVL property. A violation of the AVL property may occur in four cases: (N is a node to be rebalanced)
1) An insertion into the left subtree of the left child of the node N
2) An insertion into the right subtree of the left child of the node N
3) An insertion into the left subtree of the right child of the node N
4) An insertion into the right subtree of the right child of the node N
cases 1 & 4 can be fixed by single rotation
cases 2 & 3 can be fixed by double rotation
single and double rotation will be explained after explaing insert and delete operations.
//Insert i into the tree t, duplicate will be discarded
//Return a pointer to the resulting tree.

Code:

Tree * insert(int value, Tree * t)
{
  Tree * new_node;
  if (t == NULL)
  {
    new_node = (Tree *) malloc (sizeof (Tree));
    if (new_node == NULL)
    {
            return t;
    }
 
    new_node->element = value;
    new_node->height = 0;
    new_node->left = new_node->right = NULL;
    return new_node;
  }
  else if (value < t->element)
  {
    t->left = insert(value, t->left);
    if (height(t->left) - height(t->right) == 2)
    {
      if (value < t->left->element)
      {
        t = single_rotation_with_left(t);
      }
      else
      {
        t = double_rotation_with_left(t);
      }
    }
  }
  else if (value > t->element)
  {
    t->right = insert(value, t->right);
    if (height(t->right) - height(t->left) == 2)
    {
      if (value > t->right->element)
      {
        t = single_rotation_with_right(t);
      }
      else
      {
        t = double_rotation_with_right(t);
      }
    }
   }
  //else duplicate, ignore it
 
  t->height = MAX(height(t->left), height(t->right)) + 1;
  return t;
}

i had a hard time to find the COMPARE function ... which make this code incomplete! ...

if someone can insert the remaining functions that i listed above please help...

lastly ... can someone provide or add COMPARE function! ...

thanks in advance ... it gives me a headache with this project!

thank you!

**nonpuz** · 01-27-2013

You clearly didn't write any of this code, nor do you understand any of it, nor do you even understand what it is you are asking us to do or trying to do.

So please accept that you are going to fail whatever test/class this is for and move on. Next time DO THE COURSEWORK and READ THE MATERIAL. This is an obvious cry for free code and it's really quite insulting...you're lucky you're even getting a response at all.

**Salem** · 01-27-2013

It seems it came from here (indentation perfect copy)
Program to maintain an AVL tree - C Programming Examples and Tutorials

i want to insert this functions inside the program

Make Empty
This operation is for mainly intialization and can be used to destroy entire search tree also.

What does "I want to insert" even mean?
You've managed to get the hang of copy/paste to a forum, why can't you do the same in your source code editor.

Just paste the code, press save, press compile.

Of course, as nonpuz says, starting with your OWN code would be a bonus.

**trojan32** · 01-27-2013

Originally Posted by Salem

It seems it came from here (indentation perfect copy)
Program to maintain an AVL tree - C Programming Examples and Tutorials

What does "I want to insert" even mean?
You've managed to get the hang of copy/paste to a forum, why can't you do the same in your source code editor.

Just paste the code, press save, press compile.

Of course, as nonpuz says, starting with your OWN code would be a bonus.

-----------------------------------------------------------------

ive already done with all the functions i listed above ...
*empty
*max
*min
*insert
*delete

but in compare function ... cant figure it out where to start which the program automatically balanced the trees! ...

i want to find the simpliest code because we have to compute for the the run time! and i have a doubt with my code which already done! but i have to find the smallest running time!

i left with the compare function!... got no idea!

Thread: please help e to complete the program

Thread Tools

Search Thread

Display

please help e to complete the program

Similar Threads

Auto-Complete Program HELP

Auto-Complete Program in c

Little help to complete my program..pls..

c++ complete program

How to complete program. Any probs now?