This project implements Splay Trees, a type of self-adjusting binary search tree. Splay trees bring recently accessed elements to the root, optimizing access patterns with locality of reference.
- Splay tree implementation with insert, delete, search, and traversal operations.
- Performance analysis and comparison with other tree structures.
- Example usage and test cases.
- Node.js (for JavaScript/TypeScript implementations)
- Or a C++/Java compiler (if codebase is in C++/Java)
Clone the repository:
git clone https://github.com/yourusername/DSA-project.git
cd Splay-TreesInstall dependencies (if applicable):
npm installTo run the main program:
# For JavaScript/TypeScript
npm start
# For C++
g++ main.cpp -o splay
./splay
# For Java
javac Main.java
java MainThe code supports the following operations:
- Insert: Add a new node to the splay tree.
- Delete: Remove a node from the splay tree.
- Search: Find a node and splay it to the root.
- Traversal: In-order, pre-order, and post-order traversals.
Example (pseudocode):
// Insert elements
tree.insert(10)
tree.insert(20)
tree.insert(5)
// Search for an element
tree.search(20)
// Delete an element
tree.delete(10)
The analysis.doc file provides a detailed comparison of splay trees with other binary search trees:
- Time Complexity:
- Amortized O(log n) for insert, delete, and search.
- Worst-case O(n) for a single operation, but sequences of operations are efficient.
- Advantages:
- Good for access patterns with locality.
- No need to store balance information.
- Disadvantages:
- Not always optimal for uniformly random access.
- Can be slower than AVL/Red-Black trees for some workloads.
For more details, see analysis.doc and the source code files.