python-splay-tree

Warning

This implementation is inspired by a homework assignment from 15-213 at Carnegie Mellon University. It is intended for educational purposes only and is not suitable for production use.

A simple naive implementation of a splay tree in Python.

The purpose of this repo is to serve as an example of how to set up a GitHub Actions workflow.

Definition

A self-adjusting binary search tree in which every access (search, insert) performs a splay operation that moves the accessed node to the root via a sequence of rotations (zig, zig-zig, zig-zag). This gives O(log n) amortized performance for all operations, with recently accessed elements remaining near the root for fast repeated access.

— Paul E. Black, splay tree, Dictionary of Algorithms and Data Structures [online], NIST.

When to Use

A splay tree is the right structure when access patterns are non-uniform and recently used items are likely to be accessed again:

• Caches and working sets — recently accessed elements bubble to the root, so repeated lookups on a hot working set are faster than in a plain BST or even a red-black tree.
• Network routing tables — routers frequently look up the same popular destinations; splaying keeps hot routes near the root.
• Garbage collectors — memory managers that repeatedly access recently allocated or freed blocks benefit from the temporal locality of splay trees.
• Text editors — gap buffers and piece tables in editors like Emacs use splay trees to efficiently represent recently edited regions of a document.
• Competitive programming — splay trees support efficient split and merge operations, making them useful for order-statistic and interval problems.

Requirements

• Python 3.6+

Installation

Clone the repository and install dependencies:

git clone https://github.com/icaoberg/python-splay-tree.git
cd python-splay-tree
pip install -r requirements.txt

Usage

from SplayTree import SplayTree

tree = SplayTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)

print(tree.size())     # 5
print(tree.min())      # 1
print(tree.max())      # 7
print(tree.inorder())  # [1, 3, 4, 5, 7]
print(tree.is_empty()) # False
print(len(tree))       # 5
print(tree.search(3))  # Node(3)  — also splays 3 to root

Methods

Method	Description
insert(element)	Insert an element and splay it to the root
search(element)	Return the node with the given value (splayed to root), or None
random(n)	Populate the tree with n random integers
min()	Return the minimum value
max()	Return the maximum value
inorder()	Return elements in sorted order as a list
is_empty()	Return True if the tree has no nodes
size()	Return the number of nodes
get_root()	Return the root node

Testing

pytest tests.py

Support

If you found this project helpful, consider buying me a coffee!

Copyright © icaoberg at Carnegie Mellon University. All rights reserved.