Master Splay Tree in DSA - Interactive Learning
Master Splay Tree - DSA Learning Platform 🔄 Master Splay Tree Self-Adjusting Amortized O(log n) Learn splay tree operations with interactive splaying animations and rotations 📖 Understanding Splay Tree Introduction Splay Rotations Operations Amortized Analysis Applications What is a Splay Tree? A Splay Tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, search, and deletion in O(log n) amortized time. The key operation is splaying - moving a node to the root through a sequence of rotations. This has the effect of bringing frequently accessed nodes closer to the root, providing a form of self-optimization. Unlike AVL or Red-Black trees, splay trees do not maintain explicit balance information. Instead, they achieve balance through the splaying operation which is performed after every access. 🔑 Key Properties Self-adjusting BST No balance information stored Recently accessed nodes near root Amortized O(log n) operations Good cache performance Simple implementation 💡 Key Advantage Splay trees work well when there is locality of reference - when a small subset of elements are accessed repeatedly. Splay Rotations Splaying uses three types of rotations to move a node to the root. The type of rotation depends on the node's position relative to its parent and grandparent. 🔄 Zig (Single Rotation) Used when the node's parent is the root. Simple left or right rotation. 🔄🔄 Zig-Zig (Double Rotation - Same Direction) Used when node and parent are both left children or both right children. Rotate parent first, then node. 🔄↩️ Zig-Zag (Double Rotation - Opposite Direction) Used when node is left child and parent is right child (or vice versa). Rotate node twice. 📍 Rotation Patterns Zig (Right Rotation) P X / \ / \ X C →→→ A P / \ / \ A B B C Zig-Zig (Left-Left Case) G X / \ / \ P →→→ A P / \ / \ X C B G / \ / \ A B C D Zig-Zag (Left-Right Case) G X / \ / \ P →→→ P G \ / \ / \ X A B C D / \ B C Splay Tree Operations 📥 Insert Operation Insert node as in regular BST Splay the newly inserted node to root 🔍 Search Operation Search for node as in regular BST If found, splay the node to root If not found, splay the last accessed node 🗑️ Delete Operation Splay the node to delete to root Remove the root Join left and right subtrees 🔄 Splay Operation Repeat until node is root: If parent is root: Zig Else if same direction: Zig-Zig Else: Zig-Zag ⏱️ Time Complexity Search: O(log n) amortized Insert: O(log n) amortized Delete: O(log n) amortized Splay: O(log n) amortized ⚠️ Worst Case Single operation: O(n) Sequence of m operations: O(m log n) Amortized Analysis Splay trees have amortized O(log n) time complexity, meaning that while individual operations may take O(n) time, any sequence of m operations takes O(m log n) time total. Potential Function The analysis uses a potential function based on the rank of each node: rank(x) = log₂(size...
Subject: Data Structures with Animation | Chapter: Splay Tree in DSA