我正在尝试实现伸展树。代码进入无限循环打印
20 10 20 15 10 20 15 15 10 10 20 15
用于以下测试代码,它会不断重复。我试过调试,但我找不到哪里出错了。如果我继续以倾斜的方式插入节点,代码运行良好。例如:如果我最后不插入 1 它会很好,但是一旦它不倾斜就会产生问题。
这是我的代码
splay_tree.h
#include<queue>
#include<iostream>
#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;
}
//left 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;
}
//splaying the node
void splay(Node<T>* node){
while(node!=root){
if(node->m_parent->m_parent==nullptr){
if(node==node->m_parent->m_left){
right_rotate(node->m_parent);
return ;
}else if(node==node->m_parent->m_right){
left_rotate(node->m_parent);
return ;
}
}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){//leftleft case or 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){//rightright case or zag zag
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){
left_rotate(node->m_parent);
right_rotate(node->m_parent);
}else{
right_rotate(node->m_parent);
left_rotate(node->m_parent);
}
}
}
}
//level order traversal
void level_order(){
if(this->root==nullptr){return ;}
else{
std::queue<Node<T>* > q;
q.push(this->root);
while(!q.empty()){
Node<T>* curr_ptr=q.front();
q.pop();
std::cout<<curr_ptr->m_data<<" ";
if(curr_ptr->m_left!=nullptr){
q.push(curr_ptr->m_left);
}
if(curr_ptr->m_right!=nullptr){
q.push(curr_ptr->m_right);
}
}
}
}
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;
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){
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;
s1.insert(10);
s1.insert(20);
s1.insert(15);
s1.insert(1);
s1.level_order();
return 0;
}