输入 1 - 10 的数字时,LeftRotate 在最后一点在 AVL Tree 中失败
LeftRotate failing in AVL Tree at the last point when entering numbers from 1 - 10
我正在尝试在节点采用(键,值)的AVL树中添加数字。在 for 循环中输入从 (0,0) 到 (10,10) 的数字时,代码在尝试输入数字 (10,10) 时失败。
以下是在树中插入节点的代码:
int insert_in_tree_q5(struct AVLTreeNode **node, int key, int value){
//AVLTreeNode *newNode = newAVLTreeNode(key, value);
// if the tree is empty
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
if(key != (*node)->key){
// insert on left if the data in the key is less than the data in the node.
if (key<(*node)->key){
insert_in_tree_q5(&(*node)->left, key,value);
}
// insert on right if the data in the key is greater than the data in the node.
else if(key>(*node)->key)
{
insert_in_tree_q5(&(*node)->right, key,value);
}
// Update height of the ancestor node
(*node)->height = 1 + max(height((*node)->left), height((*node)->right));
// check balance to see if this node became unbalanced
int balance = getBalance(*node);
//First case to balance the unbalanced node
// Left Left case
if(balance>1 && key<(*node)->left->key){
*node = rightRotate(*node);
}
// Right Right Case
if (balance < -1 && key > (*node)->right->key)
*node = leftRotate(*node);
// Left Right Case
if (balance > 1 && key > (*node)->left->key)
{
(*node)->left = leftRotate((*node)->left);
*node = rightRotate(*node);
}
// Right Left Case
if (balance < -1 && key < (*node)->right->key)
{
(*node)->right = rightRotate((*node)->right);
*node = leftRotate(*node);
}
}
else if(key == (*node)->key){
if (value<(*node)->value){
insert_in_tree_q5(&(*node)->left, key,value);
}
// insert on right if the data in the key is greater than the data in the node.
else if(value>(*node)->value)
{
insert_in_tree_q5(&(*node)->right, key,value);
}
// Update height of the ancestor node
(*node)->height = 1 + max(height((*node)->left), height((*node)->right));
// check balance to see if this node became unbalanced
int balance = getBalance(*node);
//First case to balance the unbalanced node
// Left Left case
if(balance>1 && value<(*node)->left->value){
*node =rightRotate(*node);
}
// Right Right Case
if (balance < -1 && value > (*node)->right->value)
*node =leftRotate(*node);
// Left Right Case
if (balance > 1 && value > (*node)->left->value)
{
(*node)->left = leftRotate((*node)->left);
*node =rightRotate(*node);
}
// Right Left Case
if (balance < -1 && value < (*node)->right->value)
{
(*node)->right = rightRotate((*node)->right);
*node =leftRotate(*node);
}
}else if(key == (*node)->key && value == (*node)->value){
return 0;
}
return 1;
}
向左旋转的代码是:
struct AVLTreeNode* leftRotate(struct AVLTreeNode *x){
struct AVLTreeNode *y = x->right;
struct AVLTreeNode *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
// Return new root
return y;
}
我在树中输入值的方式是:
int InsertNode(AVLTree *T, int k, int v)
{
//put your code here
int returnedValue = insert_in_tree_q5(&T->root, k, v);
if(returnedValue==0){
return 0;
}
return 1;
}
tree4=newAVLTree();
j=InsertNode(tree4, 10, 10);
for (i=0; i<15; i++)
{
j=InsertNode(tree4, i, i);
if (j==0) printf("(%d, %d) already exists\n", i, i);
}
AVLTreeNode 和 AVLTree 的签名是:
typedef struct AVLTreeNode {
int key; //key of this item
int value; //value (int) of this item
int height; //height of the subtree rooted at this node
struct AVLTreeNode *parent; //pointer to parent
struct AVLTreeNode *left; //pointer to left child
struct AVLTreeNode *right; //pointer to right child
} AVLTreeNode;
AVLTree *newAVLTree()
{
AVLTree *T;
T = malloc(sizeof (AVLTree));
assert (T != NULL);
T->size = 0;
T->root = NULL;
return T;
}
PS:如果项目 (k,v) 已经存在,它应该 return 0 否则将它添加到树中并且 return 1。
关于为什么它接受直到 (9,9) 的所有值但在 (10,10) 处失败并出现错误 "Thread 1: EXC_BAD_ACCESS (code=1, address=0x18)"
的任何想法
If the item (k,v) already exists, it should return 0 else add it to the tree and return 1
在 insert_in_tree_q5
你做 :
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
if(key != (*node)->key){
...CASE A
}
else if(key == (*node)->key){
...CASE B
} else if(key == (*node)->key && value == (*node)->value){
return 0;
}
return 1;
情况 else if(key == (*node)->key && value == (*node)->value)
永远不会到达,因为就在您 else if(key == (*node)->key)
之前,您需要颠倒他们的顺序。
对我来说 (*node == NULL)
你也不必继续
请注意,您已经知道 if(key != (*node)->key)
为假,因此在接下来的两个测试中测试相等性是无用的
最后你的代码必须是:
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
else if(key != (*node)->key){
...CASE A
}
else if( value == (*node)->value){
return 0;
}
else {
...CASE B
}
return 1;
在
int InsertNode(AVLTree *T, int k, int v)
{
//put your code here
int returnedValue = insert_in_tree_q5(&T->root, k, v);
if(returnedValue==0){
return 0;
}
return 1;
}
因为insert_in_tree_q5
只有returns0或1InsertNode可以简化为just
int InsertNode(AVLTree *T, int k, int v)
{
return insert_in_tree_q5(&T->root, k, v);
}
我正在尝试在节点采用(键,值)的AVL树中添加数字。在 for 循环中输入从 (0,0) 到 (10,10) 的数字时,代码在尝试输入数字 (10,10) 时失败。
以下是在树中插入节点的代码:
int insert_in_tree_q5(struct AVLTreeNode **node, int key, int value){
//AVLTreeNode *newNode = newAVLTreeNode(key, value);
// if the tree is empty
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
if(key != (*node)->key){
// insert on left if the data in the key is less than the data in the node.
if (key<(*node)->key){
insert_in_tree_q5(&(*node)->left, key,value);
}
// insert on right if the data in the key is greater than the data in the node.
else if(key>(*node)->key)
{
insert_in_tree_q5(&(*node)->right, key,value);
}
// Update height of the ancestor node
(*node)->height = 1 + max(height((*node)->left), height((*node)->right));
// check balance to see if this node became unbalanced
int balance = getBalance(*node);
//First case to balance the unbalanced node
// Left Left case
if(balance>1 && key<(*node)->left->key){
*node = rightRotate(*node);
}
// Right Right Case
if (balance < -1 && key > (*node)->right->key)
*node = leftRotate(*node);
// Left Right Case
if (balance > 1 && key > (*node)->left->key)
{
(*node)->left = leftRotate((*node)->left);
*node = rightRotate(*node);
}
// Right Left Case
if (balance < -1 && key < (*node)->right->key)
{
(*node)->right = rightRotate((*node)->right);
*node = leftRotate(*node);
}
}
else if(key == (*node)->key){
if (value<(*node)->value){
insert_in_tree_q5(&(*node)->left, key,value);
}
// insert on right if the data in the key is greater than the data in the node.
else if(value>(*node)->value)
{
insert_in_tree_q5(&(*node)->right, key,value);
}
// Update height of the ancestor node
(*node)->height = 1 + max(height((*node)->left), height((*node)->right));
// check balance to see if this node became unbalanced
int balance = getBalance(*node);
//First case to balance the unbalanced node
// Left Left case
if(balance>1 && value<(*node)->left->value){
*node =rightRotate(*node);
}
// Right Right Case
if (balance < -1 && value > (*node)->right->value)
*node =leftRotate(*node);
// Left Right Case
if (balance > 1 && value > (*node)->left->value)
{
(*node)->left = leftRotate((*node)->left);
*node =rightRotate(*node);
}
// Right Left Case
if (balance < -1 && value < (*node)->right->value)
{
(*node)->right = rightRotate((*node)->right);
*node =leftRotate(*node);
}
}else if(key == (*node)->key && value == (*node)->value){
return 0;
}
return 1;
}
向左旋转的代码是:
struct AVLTreeNode* leftRotate(struct AVLTreeNode *x){
struct AVLTreeNode *y = x->right;
struct AVLTreeNode *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
// Return new root
return y;
}
我在树中输入值的方式是:
int InsertNode(AVLTree *T, int k, int v)
{
//put your code here
int returnedValue = insert_in_tree_q5(&T->root, k, v);
if(returnedValue==0){
return 0;
}
return 1;
}
tree4=newAVLTree();
j=InsertNode(tree4, 10, 10);
for (i=0; i<15; i++)
{
j=InsertNode(tree4, i, i);
if (j==0) printf("(%d, %d) already exists\n", i, i);
}
AVLTreeNode 和 AVLTree 的签名是:
typedef struct AVLTreeNode {
int key; //key of this item
int value; //value (int) of this item
int height; //height of the subtree rooted at this node
struct AVLTreeNode *parent; //pointer to parent
struct AVLTreeNode *left; //pointer to left child
struct AVLTreeNode *right; //pointer to right child
} AVLTreeNode;
AVLTree *newAVLTree()
{
AVLTree *T;
T = malloc(sizeof (AVLTree));
assert (T != NULL);
T->size = 0;
T->root = NULL;
return T;
}
PS:如果项目 (k,v) 已经存在,它应该 return 0 否则将它添加到树中并且 return 1。 关于为什么它接受直到 (9,9) 的所有值但在 (10,10) 处失败并出现错误 "Thread 1: EXC_BAD_ACCESS (code=1, address=0x18)"
的任何想法If the item (k,v) already exists, it should return 0 else add it to the tree and return 1
在 insert_in_tree_q5
你做 :
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
if(key != (*node)->key){
...CASE A
}
else if(key == (*node)->key){
...CASE B
} else if(key == (*node)->key && value == (*node)->value){
return 0;
}
return 1;
情况 else if(key == (*node)->key && value == (*node)->value)
永远不会到达,因为就在您 else if(key == (*node)->key)
之前,您需要颠倒他们的顺序。
对我来说 (*node == NULL)
你也不必继续
请注意,您已经知道 if(key != (*node)->key)
为假,因此在接下来的两个测试中测试相等性是无用的
最后你的代码必须是:
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
else if(key != (*node)->key){
...CASE A
}
else if( value == (*node)->value){
return 0;
}
else {
...CASE B
}
return 1;
在
int InsertNode(AVLTree *T, int k, int v)
{
//put your code here
int returnedValue = insert_in_tree_q5(&T->root, k, v);
if(returnedValue==0){
return 0;
}
return 1;
}
因为insert_in_tree_q5
只有returns0或1InsertNode可以简化为just
int InsertNode(AVLTree *T, int k, int v)
{
return insert_in_tree_q5(&T->root, k, v);
}