Implemented Splay Tree Data Structure

Ramy-Badr-Ahmed commented 1 month ago

Description

A Splay Tree is a self-adjusting binary search tree that performs splaying, moving a specified element to the root of the tree through rotations. This allows frequently accessed elements to be accessed quickly, improving the performance of subsequent operations.

Applications

Caching: Cache memory management, where the most frequently accessed items are saved on top for quicker access.
Database Indexing: As databases index mechanism for faster data searching and retrieval.
File Systems: Storage of file system metadata.
Data Compression: Data compression by identifying and encoding repeating patterns.
Text Processing: Such as spell-checkers, where words are stored for quick searching and retrieval.
Graph Algorithms: In implemention of graph algorithms, such as finding the shortest path in a weighted graph.

Contents

SplayTreeNode Class: Represents individual nodes in the Splay Tree with attributes key, value, left, right and parent. Where: key: The value used to organize the nodes in the tree. value: Stores any associated data for the node. left, right: Pointers to the left and right child nodes. parent: Pointer to the parent node.

The SplayTreeNode class encapsulates the structure of each node, linking to its child and parent nodes to maintain the tree structure and facilitate traversal.
SplayTree Class: Implements the core functionalities of a Splay Tree.

insert: Adds a new node to the tree, performing necessary rotations to maintain balance through the splay method.

search: Locates a node with a specific key and splay it to the root. If not found, the last visited node is splayed to the root.

update: Update a node with a specific key and splay it to the root. If not found, the last visited node is splayed to the root.

delete: Deletes a node from the tree and restructures the tree to ensure it remains a valid Splay Tree. It follows the top-down splayig approach, where deletion is performed after splaying the node to the root. Once the element is deleted, the two remaining subtrees are merged. If not found, throws a LogicException

splay: Repositions the accessed node to the root of the tree using tree rotations. It is divided into splayLeft() and
splayRight() depending on the location of the key in the left or right subtree.

The SplayTree class employs splaying to ensure that frequently accessed nodes are quicker to reach, enhancing access times for repeated operations.
SplayTreeRotations Abstract Class: Contains rotation methods for all cases of the Splay Tree.

zig: Performs a right rotation on the given node when it is a left child of its parent.

zag: Performs a left rotation on the given node when it is a right child of its parent.

zigZig: Performs two consecutive right rotations on the node and its parent.

zagZag: Performs two consecutive left rotations on the node and its parent.

zigZag: Performs a left rotation on the left child followed by a right rotation on the node.

zagZig: Performs a right rotation on the right child followed by a left rotation on the node.

rotateLeft: Rotates the node to the left, promoting its right child.

rotateRight: Rotates the node to the right, promoting its left child.

The SplayTreeRotations class facilitates the rotation operations needed to maintain the balance of the Splay Tree during node access and restructuring.

Unit Tests:

SplayTreeTest.php: Contains PHPUnit tests to validate the correct behavior of insertion, deletion, searching, updating, and ensuring the integrity of the Splay Tree structure. It also consider edge cases for these operations.

Time Complexity

The insert, delete, and search operations have an amortized time complexity of O(log n) in terms of tree height. The splay operation is also O(log n) on average.

GitHub Actions

All tests and workflows (in my forked repository) have passed.