C++ Segmentation fault -- 自平衡树插入
C++ Segmentation fault -- Self-balancing Tree insertion
我正在尝试解决 Hackerrank (https://www.hackerrank.com/challenges/self-balancing-tree/problem) 上的自平衡树问题,但在最后 3 个测试用例中我一直遇到分段错误。我看到之前已经发布了同样的问题,并尝试将相同的方法(检查 nullptr)应用于我的案例,但到目前为止没有成功。以下代码是用 C++ 编写的,如果你们能帮助我,我将不胜感激。谢谢!
/* Node is defined as :
typedef struct node
{
int val;
struct node* left;
struct node* right;
int ht;
} node; */
node * newNode(int val)
{
node * newNode = new node;
newNode->val = val;
newNode->left = nullptr;
newNode->right = nullptr;
newNode->ht = 0;
return newNode;
}
int getHeight(node* root)
{
if(root == nullptr) {
return -1;
} else {
return root->ht;
}
}
node* rightRotate(node* root)
{
node* temp = root->left;
root->left = temp->right;
temp->right = root;
root->ht = 1 + max(getHeight(root->left), getHeight(root->right));
temp->ht = 1 + max(getHeight(temp->left), getHeight(temp->right));
return temp;
}
node* leftRotate(node* root)
{
node* temp = root->right;
root->right = temp->left;
temp->left = root;
root->ht = 1 + max(getHeight(root->left), getHeight(root->right));
temp->ht = 1 + max(getHeight(temp->left), getHeight(temp->right));
return temp;
}
node * insert(node * root,int val)
{
if(root == nullptr) {
root = newNode(val);
return root;
}
if(val > root->val) {
root->right = insert(root->right, val);
}
else if(val < root->val) {
root->left = insert(root->left, val);
}
else{ return 0; }
root->ht = 1 + max(getHeight(root->left),getHeight(root->right));
int balance = getHeight(root->left) - getHeight(root->right);
if(root->left != nullptr && balance > 1) {//Left subtree disbalanced
if(val < root->left->val) {
//Left-Left case: perform a right rotation on the disb. node
return rightRotate(root);
}
else {
//Left-Right case: perfom a left rotation on the disb. node left subtree
//and a right rotation on the disb. node
root->left = leftRotate(root->left);
return rightRotate(root);
}
}
if(root->right != nullptr && balance < -1) {//Right subtree disbalanced
if(val > root->right->val) {
//Right-Right case: perform a left rotation on the disb. node
return leftRotate(root);
}
else {
//Right-Left case: perfom a right rotation on the disb. node right subtree
//and a left rotation on the disb. node
root->right = rightRotate(root->left);
return leftRotate(root);
}
}
return root;
}
编辑:
出于调试目的,我使用了在线 gdb 并在上面的代码中添加了以下遍历方法和主要函数:
void inOrder(node* root) {
if(root == NULL) {
return;
} else {
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
}
int main()
{
node* root=NULL;
root=insert(root,2);
root=insert(root,4);
root=insert(root,3);
inOrder(root);
return 0;
}
尝试按此顺序插入值 2、4 和 3 后,我们将得到一个不平衡的树,因为右子树的高度为 1,而左子树的高度为 -1(叶node 是 nullptr) 并且平衡因子将小于 -1。进一步的分析表明我们有一个 RIGHT-LEFT 的情况,因为导致不平衡的节点是不平衡节点(根 2)的右子节点的左子节点。然后我们必须对不平衡节点的右子节点执行右旋转,然后对不平衡节点本身执行左旋转,树最终应该如下所示:
3
/ \
2 4
感谢所有试图帮助我解决这个问题的人,事实证明,我的愚蠢是没有限制的。我相信我已经弄清楚我做错了什么。
这个问题的问题在于检查右子树是否不平衡的部分,如果是,则执行必要的旋转。在下面的代码片中,应该是
root->right = rightRotate(root->right);
而不是
root->right = rightRotate(root->left);
我正在尝试解决 Hackerrank (https://www.hackerrank.com/challenges/self-balancing-tree/problem) 上的自平衡树问题,但在最后 3 个测试用例中我一直遇到分段错误。我看到之前已经发布了同样的问题,并尝试将相同的方法(检查 nullptr)应用于我的案例,但到目前为止没有成功。以下代码是用 C++ 编写的,如果你们能帮助我,我将不胜感激。谢谢!
/* Node is defined as :
typedef struct node
{
int val;
struct node* left;
struct node* right;
int ht;
} node; */
node * newNode(int val)
{
node * newNode = new node;
newNode->val = val;
newNode->left = nullptr;
newNode->right = nullptr;
newNode->ht = 0;
return newNode;
}
int getHeight(node* root)
{
if(root == nullptr) {
return -1;
} else {
return root->ht;
}
}
node* rightRotate(node* root)
{
node* temp = root->left;
root->left = temp->right;
temp->right = root;
root->ht = 1 + max(getHeight(root->left), getHeight(root->right));
temp->ht = 1 + max(getHeight(temp->left), getHeight(temp->right));
return temp;
}
node* leftRotate(node* root)
{
node* temp = root->right;
root->right = temp->left;
temp->left = root;
root->ht = 1 + max(getHeight(root->left), getHeight(root->right));
temp->ht = 1 + max(getHeight(temp->left), getHeight(temp->right));
return temp;
}
node * insert(node * root,int val)
{
if(root == nullptr) {
root = newNode(val);
return root;
}
if(val > root->val) {
root->right = insert(root->right, val);
}
else if(val < root->val) {
root->left = insert(root->left, val);
}
else{ return 0; }
root->ht = 1 + max(getHeight(root->left),getHeight(root->right));
int balance = getHeight(root->left) - getHeight(root->right);
if(root->left != nullptr && balance > 1) {//Left subtree disbalanced
if(val < root->left->val) {
//Left-Left case: perform a right rotation on the disb. node
return rightRotate(root);
}
else {
//Left-Right case: perfom a left rotation on the disb. node left subtree
//and a right rotation on the disb. node
root->left = leftRotate(root->left);
return rightRotate(root);
}
}
if(root->right != nullptr && balance < -1) {//Right subtree disbalanced
if(val > root->right->val) {
//Right-Right case: perform a left rotation on the disb. node
return leftRotate(root);
}
else {
//Right-Left case: perfom a right rotation on the disb. node right subtree
//and a left rotation on the disb. node
root->right = rightRotate(root->left);
return leftRotate(root);
}
}
return root;
}
编辑:
出于调试目的,我使用了在线 gdb 并在上面的代码中添加了以下遍历方法和主要函数:
void inOrder(node* root) {
if(root == NULL) {
return;
} else {
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
}
int main()
{
node* root=NULL;
root=insert(root,2);
root=insert(root,4);
root=insert(root,3);
inOrder(root);
return 0;
}
尝试按此顺序插入值 2、4 和 3 后,我们将得到一个不平衡的树,因为右子树的高度为 1,而左子树的高度为 -1(叶node 是 nullptr) 并且平衡因子将小于 -1。进一步的分析表明我们有一个 RIGHT-LEFT 的情况,因为导致不平衡的节点是不平衡节点(根 2)的右子节点的左子节点。然后我们必须对不平衡节点的右子节点执行右旋转,然后对不平衡节点本身执行左旋转,树最终应该如下所示:
3
/ \
2 4
感谢所有试图帮助我解决这个问题的人,事实证明,我的愚蠢是没有限制的。我相信我已经弄清楚我做错了什么。 这个问题的问题在于检查右子树是否不平衡的部分,如果是,则执行必要的旋转。在下面的代码片中,应该是
root->right = rightRotate(root->right);
而不是
root->right = rightRotate(root->left);