patterncMinor
AVL tree insertion and deletion of nodes in C
Viewed 0 times
insertionnodesavlanddeletiontree
Problem
This is my implementation of AVL tree, it works fine. is there any thing that can be improved about addition and deletion procedures specifically when deleting the root,
```
#include
#include
#include
typedef struct treenode node;
struct treenode
{
int value;
int height;
node *left;
node *right;
node *parent;
};
node *root = NULL;
int max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
int nodetype(node *ptr,int flag=1)
{
//please ignore the default argument for now
/Determines type of node. ex. leaf or internal/
if ((ptr->parent == NULL)&&(flag))
{
return 1;
//root
}
else if ((ptr->left == NULL) && (ptr->right == NULL))
{
return 2;
//leaf node
}
else if (ptr->left == NULL)
{
return 3;
//internal node with right child
}
else if (ptr->right == NULL)
{
return 4;
//internal node with left child
}
else
{
return 5;
//internal node with left and right childs
}
}
int childtype(node *ptr)
{
/Determine wether ptr is left child of its parent or right child/
node *temp = ptr->parent;
if (temp->left == ptr)
{
return 1;
//left child
}
else if (temp->right == ptr)
{
return 2;
//right child
}
}
node* createnode(int value)
{
node ptr = (node)malloc(sizeof(node));
ptr->left = ptr->right = ptr->parent = NULL;
ptr->value = value;
ptr->height = 0;
return ptr;
}
node getposition(node ptr, int value)
{
/Return address of the first node having value equal to "value", returns NULL if not found/
if (ptr == NULL)
{
return NULL;
}
else if (value value)
{
return getposition(ptr->left, value);
}
else if (value > ptr->value)
{
return getposition(ptr->right, value);
}
else
{
return (ptr);
}
}
in
```
#include
#include
#include
typedef struct treenode node;
struct treenode
{
int value;
int height;
node *left;
node *right;
node *parent;
};
node *root = NULL;
int max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
int nodetype(node *ptr,int flag=1)
{
//please ignore the default argument for now
/Determines type of node. ex. leaf or internal/
if ((ptr->parent == NULL)&&(flag))
{
return 1;
//root
}
else if ((ptr->left == NULL) && (ptr->right == NULL))
{
return 2;
//leaf node
}
else if (ptr->left == NULL)
{
return 3;
//internal node with right child
}
else if (ptr->right == NULL)
{
return 4;
//internal node with left child
}
else
{
return 5;
//internal node with left and right childs
}
}
int childtype(node *ptr)
{
/Determine wether ptr is left child of its parent or right child/
node *temp = ptr->parent;
if (temp->left == ptr)
{
return 1;
//left child
}
else if (temp->right == ptr)
{
return 2;
//right child
}
}
node* createnode(int value)
{
node ptr = (node)malloc(sizeof(node));
ptr->left = ptr->right = ptr->parent = NULL;
ptr->value = value;
ptr->height = 0;
return ptr;
}
node getposition(node ptr, int value)
{
/Return address of the first node having value equal to "value", returns NULL if not found/
if (ptr == NULL)
{
return NULL;
}
else if (value value)
{
return getposition(ptr->left, value);
}
else if (value > ptr->value)
{
return getposition(ptr->right, value);
}
else
{
return (ptr);
}
}
in
Solution
if (x) return true; else return false;looks better asreturn x;
- Left/right operations are symmetric so do not need cut/paste. It should be possible to factor out 'small rotation' and 'large rotation' and express all other operations on the tree in terms of these. Switch statement will disappear too.
Context
StackExchange Code Review Q#135375, answer score: 3
Revisions (0)
No revisions yet.