0

我正在尝试实现一个展开树。但是在由 splay() 函数调用的 left_rotate 和 right_rotate 函数中出现了分段错误。我已经尝试调试但没有任何线索。我在哪里做错了！我认为存在某种逻辑错误。这是我的代码：

splay_tree.h

 #include"node.h"
    
    template<class T>
    class splay_tree{
    private:
     Node<T>* root=nullptr;
    
    public:
       splay_tree(){
           root=nullptr;
       }
     //gethead
     Node<T>* gethead(){
         return this->root;
     }
      void left_rotate(Node<T>* node){
     if(node==nullptr){return ;}
     if(node->m_right!=nullptr){  
         Node<T>* temp= node->m_right;
      node->m_right= temp->m_left;
      if(temp->m_left){
          temp->m_left->m_parent=node;
      }
      temp->m_parent=node->m_parent;
      if(node->m_parent==nullptr){
          this->root=temp;
      }else if(node=node->m_parent->m_left){
            node->m_parent->m_left=temp;
      }else if(node=node->m_parent->m_right){
            node->m_parent->m_right=temp;
      }
      temp->m_left=node;
      node->m_parent=temp;
       }
      
 }
    //right rotate
     void right_rotate(Node<T>* node){
         Node<T>* temp= node->m_left;
         node->m_left=temp->m_right;
         if(temp->m_right){
             temp->m_right->m_parent=node;
         }
         temp->m_parent=node->m_parent;
         if(node->m_parent==nullptr){
             this->root=temp;
         }else if(node==node->m_parent->m_left){
             node->m_parent->m_left=temp;
         }else{
             node->m_parent->m_right=temp;
         }
         temp->m_right=node;
         node->m_parent=temp;
         
     }
     //splaying the node
    void splay(Node<T>* node){
        while(node->m_parent){
            if(node->m_parent->m_parent==nullptr){
                if(node==node->m_parent->m_left){
                    right_rotate(node->m_parent);
                }else if(node==node->m_parent->m_right){
                    left_rotate(node->m_parent);
                }
            }else if(node->m_parent->m_parent!=nullptr){
                if(node==node->m_parent->m_left && node->m_parent==node->m_parent->m_parent->m_left){
                    right_rotate(node->m_parent->m_parent);
                    right_rotate(node->m_parent);
                }else if(node==node->m_parent->m_right && node->m_parent==node->m_parent->m_parent->m_right){
                    left_rotate(node->m_parent->m_parent);
                    left_rotate(node->m_parent);
                }else if(node==node->m_parent->m_right && node->m_parent==node->m_parent->m_parent->m_left){
                    right_rotate(node->m_parent);
                    left_rotate(node->m_parent);
                }else{
                    left_rotate(node->m_parent);
                    right_rotate(node->m_parent);
                }
            }
        }
    }
    
    void insert(T data){
        insert(data,this->root);
    }
    Node<T>* insert(T data,Node<T>* node){
        
        if(this->root==nullptr){
            this->root= new Node<T>(data);
            return this->root;
        }else{Node<T>* curr_ptr=node;
            while(node!=nullptr){
                
                if(data<node->m_data){
                    if(node->m_left!=nullptr){
                        node->m_left=insert(data,node->m_left);
                    }else{
                        Node<T>* new_node = new Node<T>(data);
                        curr_ptr->m_left= new_node;
                        new_node->m_parent=curr_ptr;
                        splay(new_node);
                    }
                    
                }else if(data> node->m_data){
                    if(node->m_right!= nullptr){
                        node->m_right= insert(data,node->m_right);
                    }else{
                        Node<T>* new_node= new Node<T>(data);
                        curr_ptr->m_right= new_node;
                        new_node->m_parent=curr_ptr;
                        splay(new_node);
                    }
                    
                }
    
            }
       }
       return node;
    }
    };

节点.h

template<class T>

class Node{

  public:
        T m_data; // holds the key
    Node<T>* m_parent; // pointer to the parent
    Node<T>* m_left; // pointer to left child
    Node<T>* m_right; // pointer to right child
     Node(T data){
        m_data=data;
        m_left=nullptr ;
        m_right=nullptr ;
        m_parent=nullptr;
     }
     
};

主文件

#include"splay_tree.h"
#include<iostream>

using namespace std;

int main(){
     splay_tree<int> s1;
     cout<<s1.gethead();
      s1.insert(12);
      s1.insert(89);
    return 0;
}
4

2 回答 2

2

再仔细看之后，肯定是你在做的事情有问题。让我们用示意图分解 left_rotate 代码：

这是进入旋转功能之前的样子

在此处输入图像描述

第一条指令Node<T>* temp = node->m_right导致：这本身并没有错，但请注意您的新节点临时缺少连接

在此处输入图像描述

最后，理论上node->m_right = temp->m_left会是这样的：

在此处输入图像描述

如您所见，node->m_right仍然有来自父母和孩子的传入连接，temp->m_left并将指向自身。这就是导致分段错误的原因。

纠正错误应该做的是：

  1. 确保在将其分配给新节点之前破坏了与 node->m_right 的所有连接。
  2. 不要忘记将连接添加到新的临时节点
于 2020-08-28T10:06:10.003 回答
1

好的，这是我为您的代码找到的

您对旋转函数使用了错误的命名法，即它应该在哪里 left_rotate 您正在使用 right_rotate。

注意：这可能是因为您正在从某个地方获取一部分代码，而另一部分来自其他地方。我强烈建议你先自己尝试。

谈论命名之字形可以理解为左或右，因此可能会造成混淆，这就是这里发生的事情！

对于答案部分，我更新了名称并改进了您的代码！

void left_rotate(Node<T>* node){
     if(node==nullptr){return ;}
     else{
         Node<T>* temp= node->m_right;
         node->m_right=temp->m_left;
         if(temp->m_left){
             temp->m_left->m_parent=node;
         }
         temp->m_parent=node->m_parent;
         if(node->m_parent==nullptr){
             this->root=temp;
         }else if(node==node->m_parent->m_left){
             node->m_parent->m_left=temp;
         }else if(node== node->m_parent->m_right){
             node->m_parent->m_right=temp;
         }
         temp->m_left=node;
         node->m_parent=temp;
     }
    
 }
void right_rotate(Node<T>* node){
        Node<T>* temp=node->m_left;
        node->m_left=temp->m_right;
        if(temp->m_right){
            temp->m_right->m_parent=node;
        }
        temp->m_parent= node->m_parent;
        if(node->m_parent==nullptr){
            this->root=temp;
        }else if(node==node->m_parent->m_left){
            node->m_parent->m_left=temp;
        }else if(node== node->m_parent->m_right){
            node->m_parent->m_right=temp;
        }
        temp->m_right=node;
        node->m_parent=temp;
   }

   //splay Function
      void splay(Node<T>* node){
        while(node->m_parent){
            if(!node->m_parent->m_parent){
                if(node==node->m_parent->m_left){//zig Rotation
                    right_rotate(node->m_parent);
                }else if(node==node->m_parent->m_right){
                    left_rotate(node->m_parent);
                }
            }
            else if(node==node->m_parent->m_left && node->m_parent==node->m_parent->m_parent->m_left){//Zig Zig 
                right_rotate(node->m_parent->m_parent);
                right_rotate(node->m_parent);
            }else if(node== node->m_parent->m_right && node->m_parent==node->m_parent->m_parent->m_right){//zag zag
                left_rotate(node->m_parent->m_parent);
                left_rotate(node->m_parent);
            }else if(node==node->m_parent->m_left && node->m_parent== node->m_parent->m_parent->m_right){
                right_rotate(node->m_parent);
                left_rotate(node->m_parent);
            }else if(node== node->m_parent->m_right && node->m_parent== node->m_parent->m_parent->m_left){
                left_rotate(node->m_parent);
                right_rotate(node->m_parent);
            }
        }
      }



    //Insert Function
void insert(T data){
    Node<T>* new_node= new Node<T>(data);
    Node<T>* y= nullptr;
    Node<T>* x= this->root;
    while (x!= nullptr){
        y=x;
        if(new_node->m_data<x->m_data){
            x= x->m_left;
        }
        else{
            x=x->m_right;
        }
    }
        // y is a m_parent of x
        new_node->m_parent=y;
        if(y==nullptr){
            this->root=new_node;
        }else if(new_node->m_data<y->m_data){
            y->m_left=new_node;
        }else{
            y->m_right=new_node;
        }
    
    splay(new_node);
}
于 2020-09-04T08:27:15.747 回答