cdata-structurestreeavl-tree
How to make insert operation in AVL Tree?
I need to make an AVL trees using input {1,2,3,4,5,6,7,8,9,10,11,12,13}. However, I am having trouble with my Insert operation. This is my code:
#include<stdio.h>
#include<stdlib.h>
#define MAXNODE 100
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
struct AvlNode
{
int Element;
AvlTree Left;
AvlTree Right;
int Height;
};
int Max(int a, int b)
{
return (a > b)? a:b;
}
AvlTree MakeEmpty(AvlTree T)
{
if(T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
int Height(Position P)
{
if(P == NULL)
{
return -1;
}
else
{
return P->Height;
}
}
Position SingleRotateWithLeft(Position K2)
{
Position K1; //Rotate centered with K1
K1 = K2->Left; //Assign K1 as the left subtree of K2
K2->Left = K1->Right; //Link Y as left subtree of K2
K1->Right = K2;
K2->Height = Max(K2->Left->Height, K2->Right->Height) + 1;
K1->Height = Max(K1->Left->Height, K2->Height) + 1;
return K1;
}
Position SingleRotateWithRight(Position K2)
{
Position K1;
K1 = K2->Right;
K2->Right = K1->Left;
K1->Left = K2;
K2->Height = Max(K2->Right->Height, K2->Left->Height) + 1;
K1->Height = Max(K1->Right->Height, K2->Height) + 1;
return K1;
}
Position DoubleRotateWithLeft(Position K3)
{
K3->Left = SingleRotateWithRight(K3->Left);
return SingleRotateWithLeft(K3);
}
Position DoubleRotateWithRight(Position K3)
{
K3->Right = SingleRotateWithLeft(K3->Right);
return SingleRotateWithRight(K3);
}
/*Insert function*/
/*
-perform normal BST insertion
-current node must be one of the ancestors of the newly inserted node
-update height
-get balance factor(left subtree height-right subtree height)
-if balance factor > 1: current node is unbalance(left left case or left right case
-if balance factor < -1: current node is unbalance(right right left or right left case)
*/
AvlTree Insert(int X, AvlTree T)
{
if(T == NULL)
{
T = (AvlTree)malloc(sizeof(struct AvlNode));
if(T == NULL)
{
printf("Out of space!\n");
return NULL;
}
else
{
T->Element = X;
T->Height = 0;
T->Left = NULL;
T->Right = NULL;
}
}
else if(X < T->Element)
{
T->Left = Insert(X, T->Left);
if(T->Left->Height - T->Right->Height == 2)
{
if(X<T->Left->Element)
{
T = SingleRotateWithLeft(T);
}
else
{
T = DoubleRotateWithLeft(T);
}
}
}
else if(X > T->Element)
{
T->Right = Insert(X, T->Right);
if(T->Right->Height - T->Left->Height == 2)
{
if(X > T->Right->Element)
{
T = SingleRotateWithRight(T);
}
else
{
T = DoubleRotateWithRight(T);
}
}
}
//X is in the tree already
T->Height = Max(T->Left->Height, T->Right->Height) + 1;
return T;
}
//To print the all edges in tree using level order traversal
void PrintTreeEdge(AvlTree T)
{
AvlTree Queue[MAXNODE];
int front;
int rear;
if(T == NULL)
{
return;
}
front = -1;
rear = 0;
Queue[rear] = T;
while(front != rear)
{
front++;
printf("%d-> ", Queue[front]->Element);
if(Queue[front]->Left != NULL)
{
rear++;
Queue[rear] = Queue[front]->Left;
}
if(Queue[front]->Right != NULL)
{
rear++;
Queue[rear] = Queue[front]->Right;
}
}
}
int main()
{
struct AvlNode* Tree = NULL;
Tree = Insert(1, Tree);
Insert(2, Tree);
Insert(3, Tree);
Insert(4, Tree);
Insert(5, Tree);
Insert(6, Tree);
Insert(7, Tree);
Insert(8, Tree);
Insert(9, Tree);
printf("The order is:\n");
PrintTreeEdge(Tree);
return 0;
}
The PrintTreeEdge() function is used to traverse and print the trees using level-order traversal.
Whenever I ran this code there is no output, but there's no error report, so I don't know which part is wrong.
This is the output:
Solution
There are essentially two problems in your code:
There are several places where you access the
->Heightmember of aNULLreference. Instead, always use the functionHeightwhen you need to get that information from a reference which might beNULL. Fix this in both single rotation functions, and in theInsertfunction.The
Insertfunction may perform a rotation on the root node, so it may return a different root reference. This means that the caller must always take the returned value and assign it to its own root reference. You have not done this in the main program.
As a side note, I find it useful for debugging to have a print function that prints the tree in in-order sequence with depth-indentations, so you can actually see its structure.
Here is your code with the 2 issues corrected, and the additional print function:
#include<stdio.h>
#include<stdlib.h>
#define MAXNODE 100
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
struct AvlNode
{
int Element;
AvlTree Left;
AvlTree Right;
int Height;
};
int Max(int a, int b)
{
return (a > b)? a:b;
}
AvlTree MakeEmpty(AvlTree T)
{
if(T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
int Height(Position P)
{
if(P == NULL)
{
return -1;
}
else
{
return P->Height;
}
}
Position SingleRotateWithLeft(Position K2)
{
Position K1; //Rotate centered with K1
K1 = K2->Left; //Assign K1 as the left subtree of K2
K2->Left = K1->Right; //Link Y as left subtree of K2
K1->Right = K2;
K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
K1->Height = Max(Height(K1->Left), Height(K2)) + 1;
return K1;
}
Position SingleRotateWithRight(Position K2)
{
Position K1;
K1 = K2->Right;
K2->Right = K1->Left;
K1->Left = K2;
K2->Height = Max(Height(K2->Right), Height(K2->Left)) + 1;
K1->Height = Max(Height(K1->Right), Height(K2)) + 1;
return K1;
}
Position DoubleRotateWithLeft(Position K3)
{
K3->Left = SingleRotateWithRight(K3->Left);
return SingleRotateWithLeft(K3);
}
Position DoubleRotateWithRight(Position K3)
{
K3->Right = SingleRotateWithLeft(K3->Right);
return SingleRotateWithRight(K3);
}
/*Insert function*/
/*
-perform normal BST insertion
-current node must be one of the ancestors of the newly inserted node
-update height
-get balance factor(left subtree height-right subtree height)
-if balance factor > 1: current node is unbalance(left left case or left right case
-if balance factor < -1: current node is unbalance(right right left or right left case)
*/
AvlTree Insert(int X, AvlTree T)
{
if(T == NULL)
{
T = (AvlTree)malloc(sizeof(struct AvlNode));
if(T == NULL)
{
printf("Out of space!\n");
return NULL;
}
else
{
T->Element = X;
T->Height = 0;
T->Left = NULL;
T->Right = NULL;
}
}
else if(X < T->Element)
{
T->Left = Insert(X, T->Left);
if(Height(T->Left) - Height(T->Right) == 2)
{
if(X < T->Left->Element)
{
T = SingleRotateWithLeft(T);
}
else
{
T = DoubleRotateWithLeft(T);
}
}
}
else if(X > T->Element)
{
T->Right = Insert(X, T->Right);
if(Height(T->Right) - Height(T->Left) == 2)
{
if(X > T->Right->Element)
{
T = SingleRotateWithRight(T);
}
else
{
T = DoubleRotateWithRight(T);
}
}
}
//X is in the tree already
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
return T;
}
void printIndent(AvlTree T, int depth) {
if (T == NULL) return;
printIndent(T->Right, depth + 2);
printf("%*d\n", depth + 1, T->Element);
printIndent(T->Left, depth + 2);
}
//To print the all edges in tree using level order traversal
void PrintTreeEdge(AvlTree T)
{
AvlTree Queue[MAXNODE];
int front;
int rear;
if(T == NULL)
{
return;
}
front = -1;
rear = 0;
Queue[rear] = T;
while(front != rear)
{
front++;
printf("%d-> ", Queue[front]->Element);
if(Queue[front]->Left != NULL)
{
rear++;
Queue[rear] = Queue[front]->Left;
}
if(Queue[front]->Right != NULL)
{
rear++;
Queue[rear] = Queue[front]->Right;
}
}
}
int main()
{
struct AvlNode* Tree = NULL;
Tree = Insert(1, Tree);
Tree = Insert(2, Tree);
Tree = Insert(3, Tree);
Tree = Insert(4, Tree);
Tree = Insert(5, Tree);
Tree = Insert(6, Tree);
Tree = Insert(7, Tree);
Tree = Insert(8, Tree);
Tree = Insert(9, Tree);
printIndent(Tree, 0);
printf("The order is:\n");
PrintTreeEdge(Tree);
return 0;
}
This produces the following output:
9
8
7
6
5
4
3
2
1
The order is:
4-> 2-> 6-> 1-> 3-> 5-> 8-> 7-> 9->
- Casting Pointer array from one type to another
- Minimizing the number of malloc() calls improves performance?
- Difference between curl/curl.h, libcurl, libcurl4-openssl-dev, libcurl4-nss-dev libraries?
- Why doesn't my manually entered double value match the expected value in C?
- From 2D Arrays to 2x2 Matrix in C
- How to determine the value of socket listen() backlog parameter?
- What does #define do in the Compiler?
- Deleting selected element in a doubly linked list
- Writing to qemu RISCV UART using c
- Bubble sort does not sort as expected
- How to store and then print a 2d character/string array horizontally for 5 times?
- Fast CRC algorithm?
- Assertion —to a function pointer— failed
- Learning c, my code runs but doesn't displayed print?
- Strange size change in core dump file
- Rust's .o file format not recognized by GCC
- How to declare a constant "mutable pointer" to an immutable block of memory
- Printing all environment variables in C / C++
- What is the difference between getch() and getchar()?
- Filemanagement in C: Unsuccessful attempt in creating/overwriting a file using fopen
- Get pixel color at mouse position fastest way
- Valid VISA: 4222222222222 outputted as invalid
- Unique Words Counter in C
- Confused about casting and order of operations
- What is the closest thing Windows has to fork()?
- Why No Variable Declarations in Boolean Expressions in C?
- Search Algorithm to find the k lowest values in a list (selection algorithm/problem)
- What is the need of hh and h format specifiers?
- can't load bmp file with SDL_LoadBMP in CodeBlocks
- Need help to solve function issue