include
struct Node { int key; Node* left; Node* right; Node* parent; // Added parent pointer for easier traversal Node(int k, Node* p = nullptr) : key(k), left(nullptr), right(nullptr), parent(p) {} };
Node* createNode(int key, Node* parent = nullptr) { return new Node(key, parent); }
Node* rightRotate(Node* x) { Node* y = x->left; x->left = y->right; if (y->right) y->right->parent = x; y->right = x; y->parent = x->parent; x->parent = y; return y; }
Node* leftRotate(Node* x) { Node* y = x->right; x->right = y->left; if (y->left) y->left->parent = x; y->left = x; y->parent = x->parent; x->parent = y; return y; }
Node* splay(Node* root, int key) { if (root == nullptr || root->key == key) return root;
if (root->key > key) { if (root->left == nullptr) return root; if (root->left->key > key) { root->left->left = splay(root->left->left, key); root = rightRotate(root); } else if (root->left->key < key) { root->left->right = splay(root->left->right, key); if (root->left->right != nullptr) root->left = leftRotate(root->left); } return (root->left == nullptr) ? root : rightRotate(root); } else { if (root->right == nullptr) return root; if (root->right->key > key) { root->right->left = splay(root->right->left, key); if (root->right->left != nullptr) root->right = rightRotate(root->right); } else if (root->right->key < key) { root->right->right = splay(root->right->right, key); root = leftRotate(root); } return (root->right == nullptr) ? root : leftRotate(root); }
}
Node* insert(Node* root, int key) { if (root == nullptr) return createNode(key);
root = splay(root, key); if (root->key == key) return root; Node* newNode = createNode(key); if (root->key > key) { newNode->right = root; newNode->left = root->left; if (root->left) root->left->parent = newNode; root->left = nullptr; } else { newNode->left = root; newNode->right = root->right; if (root->right) root->right->parent = newNode; root->right = nullptr; } newNode->parent = nullptr; // New root has no parent return newNode;
}
void inOrder(Node* root) { if (root) { inOrder(root->left); std::cout << root->key << " "; inOrder(root->right); } }
int main() { Node* root = nullptr;
root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); root = insert(root, 50); std::cout << "Inorder traversal of the splay tree: "; inOrder(root); std::cout << std::endl; return 0;
}