展开树实现

Question

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

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;
     }
     
};

main.cpp

#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;
}

Answer 1

仔细一看，你做的肯定有问题。让我们用原理图分解 left_rotate 代码：

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

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

最后，node->m_right = temp->m_left 理论上看起来像这样：

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

您应该纠正错误的是：

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

Answer 2

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

You are using wrong nomenclature for the rotation functions i.e where it should be left_rotate you are using 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);
}

展开树实现

Splay Tree Implementation

c++

binary-tree

binary-search-tree

splay-tree