A Python implementation of red-black trees

Overview

Python red-black trees

Python application codecov

A Python implementation of red-black trees. This code was originally copied from programiz.com, but I have made a few tweaks to improve the user interface. I have also fixed a hard-to-catch but serious bug in the original implementation (which has since been propogated to a number of tutorials on the internet), and added a rigorous testing suite to ensure there are no further bugs.

What is this for?

I made this repo so that students in my algorithms class can try out red-black trees without needing to use C++. Feel free to use it for similar educational purposes! For more practical use-cases, you're probably better off useing the SortedContainers library.

Documentation

This data structure is designed to be used either as a standard red-black binary search tree or as a red-black tree backed dictionary.

Standard red-black tree interface

Constructor

A new red-black tree can be constructed as follows:

bst = RedBlackTree()

Insert

Items can be inserted into a tree using the insert method:

bst.insert(5)  # inserts a node with value 5

Delete

Items can be removed from the tree using the delete method. This method will do nothing if there is no item in the tree with the specific key.

bst.delete(5)  # removes a node with value 5

Minimum and maximum

The minimum and maximum value in the tree can be found with the corresponding methods. If the tree is empty, these methods will both return the special value bst.TNULL

bst.minimum()  # returns minimum value
bst.maximum()  # returns maximum value

bst.minimum() == bst.TNULL  # Check whether tree is empty

Tree size

Tree size can be accessed via the size member variable:

bst.size  # contains the tree's size

Search

To find a specific item in the tree, you can use the search method:

bst.search(6)  # returns the node containing 6. Will return bst.TNULL if item is not present.

Predecessor and successor

To get a node's predecessor or sucessor;

bst.predecessor(bst.search(6))  # Gets the predecessor a node containing 6
bst.successor(bst.search(6))  # Gets the successor a node containing 6

Printing methods

To know more about the contents of the tree, you can use various printing methods:

bst.print_tree()  # prints an ASCII representation of the whole tree
bst.preorder()      # prints a preorder traversal
bst.inorder()       # prints an inorder traveral
bst.postorder()     # prints a postorder traversal

Dictionary interface

bst[80] = 4  # Store the value 4 with the key 80
bst[80]      # Retrieve the value associated with the key 80
Owner
Emily Dolson
Assistant professor studying evolution in cancer and digital organisms and building tools to do so. Views my own.
Emily Dolson
One-Stop Destination for codes of all Data Structures & Algorithms

CodingSimplified_GK This repository is aimed at creating a One stop Destination of codes of all Data structures and Algorithms along with basic explai

Geetika Kaushik 21 Sep 26, 2022
schemasheets - structuring your data using spreadsheets

schemasheets - structuring your data using spreadsheets Create a data dictionary / schema for your data using simple spreadsheets - no coding required

Linked data Modeling Language 23 Dec 01, 2022
IADS 2021-22 Algorithm and Data structure collection

A collection of algorithms and datastructures introduced during UoE's Introduction to Datastructures and Algorithms class.

Artemis Livingstone 20 Nov 07, 2022
My notes on Data structure and Algos in golang implementation and python

My notes on DS and Algo Table of Contents Arrays LinkedList Trees Types of trees: Tree/Graph Traversal Algorithms Heap Priorty Queue Trie Graphs Graph

Chia Yong Kang 0 Feb 13, 2022
A HDF5-based python pickle replacement

Hickle Hickle is an HDF5 based clone of pickle, with a twist: instead of serializing to a pickle file, Hickle dumps to an HDF5 file (Hierarchical Data

Danny Price 450 Dec 21, 2022
A collection of data structures and algorithms I'm writing while learning

Data Structures and Algorithms: This is a collection of data structures and algorithms that I write while learning the subject Stack: stack.py A stack

Dhravya Shah 1 Jan 09, 2022
Supporting information (calculation outputs, structures)

Supporting information (calculation outputs, structures)

Eric Berquist 2 Feb 02, 2022
Python tree data library

Links Documentation PyPI GitHub Changelog Issues Contributors If you enjoy anytree Getting started Usage is simple. Construction from anytree impo

776 Dec 28, 2022
Solutions for leetcode problems.

Leetcode-solution This is an repository for storring new algorithms that I am learning form the LeetCode for future use. Implemetations Two Sum (pytho

Shrutika Borkute 1 Jan 09, 2022
A simple tutorial to use tree-sitter to parse code into ASTs

A simple tutorial to use py-tree-sitter to parse code into ASTs. To understand what is tree-sitter, see https://github.com/tree-sitter/tree-sitter. Tr

Nghi D. Q. Bui 7 Sep 17, 2022
A JSON-friendly data structure which allows both object attributes and dictionary keys and values to be used simultaneously and interchangeably.

A JSON-friendly data structure which allows both object attributes and dictionary keys and values to be used simultaneously and interchangeably.

Peter F 93 Dec 01, 2022
Python library for doing things with Grid-like structures

gridthings Python library for doing things with Grid-like structures Development This project uses poetry for dependency management, pre-commit for li

Matt Kafonek 2 Dec 21, 2021
pyprobables is a pure-python library for probabilistic data structures

pyprobables is a pure-python library for probabilistic data structures. The goal is to provide the developer with a pure-python implementation of common probabilistic data-structures to use in their

Tyler Barrus 86 Dec 25, 2022
This repository is a compilation of important Data Structures and Algorithms based on Python.

Python DSA 🐍 This repository is a compilation of important Data Structures and Algorithms based on Python. Please make seperate folders for different

Bhavya Verma 27 Oct 29, 2022
Webtesting for course Data Structures & Algorithms

Selenium job to automate queries to check last posts of Module Data Structures & Algorithms Web-testing for course Data Structures & Algorithms Struct

1 Dec 15, 2021
Python collections that are backended by sqlite3 DB and are compatible with the built-in collections

sqlitecollections Python collections that are backended by sqlite3 DB and are compatible with the built-in collections Installation $ pip install git+

Takeshi OSOEKAWA 11 Feb 03, 2022
A Python dictionary implementation designed to act as an in-memory cache for FaaS environments

faas-cache-dict A Python dictionary implementation designed to act as an in-memory cache for FaaS environments. Formally you would describe this a mem

Juan 3 Dec 13, 2022
Multidict is dict-like collection of key-value pairs where key might be occurred more than once in the container.

multidict Multidict is dict-like collection of key-value pairs where key might be occurred more than once in the container. Introduction HTTP Headers

aio-libs 325 Dec 27, 2022
Map single-cell transcriptomes to copy number evolutionary trees.

Map single-cell transcriptomes to copy number evolutionary trees. Check out the tutorial for more information. Installation $ pip install scatrex SCA

Computational Biology Group (CBG) 12 Jan 01, 2023
Python Data Structures and Algorithms

No non-sense and no BS repo for how data structure code should be in Python - simple and elegant.

Prabhu Pant 1.9k Jan 08, 2023