c++ - 重新平衡时如何修复 AVL 删除操作中的分段错误?
问题描述
我正在实现 AVL 树,并且我的搜索和插入功能正常工作,但是我的删除功能出现分段错误。我之前已经正确实现了 BST 树,所以我知道问题在于树的重新平衡,而不是节点的初始删除。
由于我的插入操作适用于重新平衡,我也知道问题不在于旋转功能本身。
我尝试了不同的策略,例如在每个节点上保持平衡因子,并尝试实现我在网上找到的其他源代码,但我总是以分段错误而告终,并且真的找不到在哪里。我会很感激任何帮助。
class AVL
{
public:
AVL();
Node* insert(int num);
Node* search(int num);
Node* remove(int num);
void print();
void comparisonPrint();
private:
int comparisonCount;
Node* root;
int max(int a, int b);
int getHeight(Node* t);
int getBalance(Node* t);
Node* insert(Node* &t, int num);
Node* rotateWithLeftChild(Node* t);
Node* rotateWithRightChild(Node* t);
Node* doubleRotateWithLeftChild(Node* t);
Node* doubleRotateWithRightChild(Node* t);
Node* search(Node* t, int num);
Node* removeMin(Node* parent, Node* node);
Node* remove(Node* &t, int num);
void print(Node* t);
//print
};
int AVL::max(int a, int b)
{
return (a > b)? a : b;
}
int AVL::getHeight(Node* t)
{
return (t == NULL) ? 0 : t->height;
}
int AVL::getBalance(Node* t)
{
if(t == NULL)
return 0;
return getHeight(t->leftChild) - getHeight(t->rightChild);
}
//helper function for remove - finds min
Node* AVL::removeMin(Node* parent, Node* node) //removes node, but does not delete - returns ptr instead
{
if(node != NULL)
{
if(node->leftChild != NULL) //go to leftmost child in right subtree
return removeMin(node, node->leftChild);
else //min val
{
parent->leftChild = node->rightChild;
return node;
}
}
else //subtree empty - incorrect use of function
return NULL;
}
Node* AVL::remove(Node* &t, int num)
{
cout << num;
if(t != NULL)
{
if(num > t->key)
{
comparisonCount++;
remove(t->rightChild, num);
}
else if(num < t->key)
{
comparisonCount++;
remove(t->leftChild, num);
}
else if(t->leftChild != NULL && t->rightChild != NULL)
{
comparisonCount++;
//2 children
Node* minRightSubtree = removeMin(t, t->rightChild);
t->key = minRightSubtree->key;
delete minRightSubtree;
}
else
{
comparisonCount++;
//0 or 1 child
Node* temp = t;
if(t->leftChild != NULL)
t = t->leftChild;
else if(t->rightChild != NULL)
t = t->rightChild;
delete temp;
}
//update height
t->height = max(getHeight(t->leftChild), getHeight(t->rightChild)) + 1;
int balance = getBalance(t);
if(balance > 1 && getBalance(t->leftChild) >= 0)
return rotateWithRightChild(t);
if(balance > 1 && getBalance(t->leftChild) < 0)
{
t->leftChild = rotateWithLeftChild(t->leftChild);
return rotateWithRightChild(t);
}
if(balance < -1 && getBalance(t->rightChild) <= 0)
return rotateWithLeftChild(t);
if(balance < -1 && getBalance(t->rightChild) > 0)
{
t->rightChild = rotateWithRightChild(t->rightChild);
return rotateWithLeftChild(t);
}
}
return t;
}
所以我需要删除函数来删除指定的节点,并在必要时使用适当的旋转重新平衡树。但是,每当我尝试在我的 main.js 中调用该函数时,我都会遇到分段错误。谢谢。
解决方案
您的代码有两个问题。首先是要删除的节点有两个孩子时的removeMin
函数和函数中的else if
部分。remove
该功能的基本目的removeMin
应该是找到要删除的节点的顺序后继者,这就是t
您的情况。考虑t
有 2 个子节点(两个叶节点)的情况,那么您的removeMin
函数将设置t->leftChild
为t->rightChild->rightChild
哪个NULL
是错误的。树的重组也应该在内部完成,remove
因此removeMin
变为:
Node* AVL::removeMin(Node* node) // returns inorder successor of 't'
{
if(node->left == NULL)
return node;
return removeMin(node->left);
}
开始remove
工作,我们重置t->key
并且minRightSubtree->key
现在要删除的节点是minRightSubtree
。但请注意,从 nodet
到 node的链中键的顺序发生了变化minRightSubtree
。t->key
小于之前节点的所有键minRightSubtree
。因此,您不能只是delete minRightSubtree
,您必须调用remove
节点上的函数,该函数minRightSubtree
将负责重组此链。您还可以从递归堆栈中获得一些帮助,以便t
在删除/旋转后为当前节点获取正确的子节点:
Node* AVL::remove(Node* &t, int num)
{
if (t == NULL)
return NULL;
if (num > t->key)
t->rightChild = remove(t->rightChild, num);
else if (num < t->key)
t->leftChild = remove(t->leftChild, num);
else if (t->leftChild != NULL && t->rightChild != NULL)
{
//2 children
Node* minRightSubtree = removeMin(t->rightChild);
t->key = minRightSubtree->key;
t->rightChild = remove(t->rightChild, minRightSubtree->key);
}
else
{
//0 or 1 child
Node* temp = t;
if (t->leftChild != NULL)
t = t->leftChild;
else if (t->rightChild != NULL)
t = t->rightChild;
if(temp == t)
t = NULL;
delete temp;
}
if (t == NULL) // this case was added since there is a possibility of deleting 't'
return NULL;
//update height
t->height = max(getHeight(t->leftChild), getHeight(t->rightChild)) + 1;
int balance = getBalance(t);
if (balance > 1 && getBalance(t->leftChild) >= 0)
return rotateWithRightChild(t);
if (balance > 1 && getBalance(t->leftChild) < 0)
{
t->leftChild = rotateWithLeftChild(t->leftChild);
return rotateWithRightChild(t);
}
if (balance < -1 && getBalance(t->rightChild) <= 0)
return rotateWithLeftChild(t);
if (balance < -1 && getBalance(t->rightChild) > 0)
{
t->rightChild = rotateWithRightChild(t->rightChild);
return rotateWithLeftChild(t);
}
return t;
}
我假设您用于更新高度和平衡有根子树的代码是正确的,因为我忘记了它的理论并且需要修改。
推荐阅读
- typescript - 如何为返回模块本身的第三方库函数创建 TypeScript defs
- excel - 最后一行问题
- sql - 如果可用,请按月加入,否则请在最近一个月加入
- python-3.x - 如果 else 条件不适用于具有 None 值的列
- xaml - Xamarin Visual Studio 无法检测到同一命名空间中的视图
- linux - 在 bash 中移动文件时遇到问题
- java - 何时不使用两种方式的 SSL 认证验证
- r - Shinyserver 中 rshiny 中两个不同数据集的两个图
- python - 如何使用 Tensorflow 执行笛卡尔积?
- javascript - Three.js 获取 translateZ 值 [three.js]