如何在AVL Tree中进行插入操作?
How to make insert operation in AVL Tree?
我需要使用输入 {1,2,3,4,5,6,7,8,9,10,11,12,13} 创建一个 AVL 树。但是,我的插入操作遇到了问题。
这是我的代码:
#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;
}
PrintTreeEdge()
函数用于使用level-order traversal遍历并打印树。
每当我 运行 这段代码没有输出,但也没有错误报告,所以我不知道是哪一部分出错了。
这是输出:
你的代码基本上有两个问题:
有几个地方可以访问 NULL
引用的 ->Height
成员。相反,当您需要从可能是 NULL
的引用中获取该信息时,请始终使用函数 Height
。在单旋转函数和 Insert
函数中修复此问题。
Insert
函数可能会在根节点上执行旋转,因此它可能return不同的根引用。这意味着调用者必须始终 获取returned 值并将其分配给自己的根引用。你没有在主程序中这样做。
附带说明一下,我发现有一个打印函数对调试很有用,它可以按顺序打印带有深度缩进的树,这样您就可以真正看到它的结构。
这是您的代码,已更正 2 个问题,并增加了打印功能:
#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;
}
这会产生以下输出:
9
8
7
6
5
4
3
2
1
The order is:
4-> 2-> 6-> 1-> 3-> 5-> 8-> 7-> 9->
我需要使用输入 {1,2,3,4,5,6,7,8,9,10,11,12,13} 创建一个 AVL 树。但是,我的插入操作遇到了问题。 这是我的代码:
#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;
}
PrintTreeEdge()
函数用于使用level-order traversal遍历并打印树。
每当我 运行 这段代码没有输出,但也没有错误报告,所以我不知道是哪一部分出错了。
这是输出:
你的代码基本上有两个问题:
有几个地方可以访问
NULL
引用的->Height
成员。相反,当您需要从可能是NULL
的引用中获取该信息时,请始终使用函数Height
。在单旋转函数和Insert
函数中修复此问题。Insert
函数可能会在根节点上执行旋转,因此它可能return不同的根引用。这意味着调用者必须始终 获取returned 值并将其分配给自己的根引用。你没有在主程序中这样做。
附带说明一下,我发现有一个打印函数对调试很有用,它可以按顺序打印带有深度缩进的树,这样您就可以真正看到它的结构。
这是您的代码,已更正 2 个问题,并增加了打印功能:
#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;
}
这会产生以下输出:
9
8
7
6
5
4
3
2
1
The order is:
4-> 2-> 6-> 1-> 3-> 5-> 8-> 7-> 9->