c++ - 展开树实现

问题描述

我正在尝试实现一个展开树。但是在由 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;
}

标签： c++binary-treebinary-search-treesplay-tree

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

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

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

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

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

纠正错误应该做的是：

确保在将其分配给新节点之前破坏了与 node->m_right 的所有连接。
不要忘记将连接添加到新的临时节点

c++ - 展开树实现

问题描述

解决方案

推荐阅读