本文介绍了这是用于移除avl树中的项目的代码,在移除功能中什么是“后继者”。 ?我得到这个错误的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
struct node
{
int key ;
int h;
node *left;
node *root;
node *right;
};
int h(struct node* x)
{
if (x == NULL)
return 0;
return x->h;
}
int balanceavl(struct node *n)
{
if (n == NULL)
return 0;
return (h(n->left) , h(n->right));
}
node* rightrotate(struct node *y)
{
struct node *x = y->left;
struct node *z = x->right;
x->right = y;
y->left = z;
y->h = max(h(y->left), h(y->right))+1;
x->h = max(h(x->left), h(x->right))+1;
return x;
}
node* leftrotate(struct node *x)
{
struct node *y = x->right;
struct node *z = y->left;
y->left = x;
x->right = z;
y->h = max(h(y->left), h(y->right))+1;
x->h = max(h(x->left), h(x->right))+1;
return y;
}
struct node *remove(struct node *root, int key)
{
struct node *remove_node;
if (root == NULL)
{
return root;
}
if ( key < root->key)
{
root->left = remove(root->left, key);
}
else if ( key > root->key)
{
root->right = remove(root->right,key);
}
else {
if ((root->left == NULL) && (root->right != NULL)){
remove_node = root->right;
*root = *remove_node;
free(remove_node); // this is for free-ing the memory
} else if ((root->right == NULL) && (root->left != NULL)){
remove_node = root->left;
*root = *remove_node;
free(remove_node);
} else if ((root->right == NULL) && (root->left == NULL)){
remove_node = root;
root = NULL;
} else {
remove_node = successor(root);
root->key = remove_node->key;
root->right = remove(root->right, remove_node->key);
}
}
if (root == NULL) {
return root;
//lr
if (balanceavl(root) == 2){
if (balanceavl(root->left) == -1) {
root->left = leftrotate(root->left);
return rightrotate(root);
//ll
} else if (balanceavl(root->left) == 1) {
return rightrotate(root);
}
}
//rr
if (balanceavl(root) == -2) {
if (balanceavl(root->right) == -1) {
return leftrotate(root);
}
//rl
else if (balanceavl(root->right) == 1) {
root->right = rightrotate(root->right);
return leftrotate(root);
}
}
}
return root;
}
推荐答案
这篇关于这是用于移除avl树中的项目的代码,在移除功能中什么是“后继者”。 ?我得到这个错误的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!