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
This repository contains code for CTF platform.

CTF-platform Repository for backend of CTF hosting website For starting the project first time : Clone the repo in which you have to work in your syst

Yash Jain 3 Feb 18, 2022
This repo is all about different data structures and algorithms..

Data Structure and Algorithm : Want to learn data strutrues and algorithms ??? Then Stop thinking more and start to learn today. This repo will help y

Priyanka Kothari 7 Jul 10, 2022
Basic sort and search algorithms written in python.

Basic sort and search algorithms written in python. These were all developed as part of my Computer Science course to demonstrate understanding so they aren't 100% efficent

Ben Jones 0 Dec 14, 2022
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
Decided to include my solutions for leetcode problems.

LeetCode_Solutions Decided to include my solutions for leetcode problems. LeetCode # 1 TwoSum First leetcode problem and it was kind of a struggle. Th

DandaIT04 0 Jan 01, 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
Chemical Structure Generator

CSG: Chemical Structure Generator A simple Chemical Structure Generator. Requirements Python 3 (= v3.8) PyQt5 (optional; = v5.15.0 required for grap

JP&K 5 Oct 22, 2022
Leetcode solutions - All algorithms implemented in Python 3 (for education)

Leetcode solutions - All algorithms implemented in Python 3 (for education)

Vineet Dhaimodker 3 Oct 21, 2022
Supporting information (calculation outputs, structures)

Supporting information (calculation outputs, structures)

Eric Berquist 2 Feb 02, 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
Persistent dict, backed by sqlite3 and pickle, multithread-safe.

sqlitedict -- persistent dict, backed-up by SQLite and pickle A lightweight wrapper around Python's sqlite3 database with a simple, Pythonic dict-like

RARE Technologies 954 Dec 23, 2022
This Repository consists of my solutions in Python 3 to various problems in Data Structures and Algorithms

Problems and it's solutions. Problem solving, a great Speed comes with a good Accuracy. The more Accurate you can write code, the more Speed you will

SAMIR PAUL 1.3k Jan 01, 2023
Programming of a spanning tree algorithm with Python : In depth first with a root node.

ST Algorithm Programming of a spanning tree algorithm with Python : In depth first with a root node. Description This programm reads informations abou

Mathieu Lamon 1 Dec 16, 2021
A high-performance immutable mapping type for Python.

immutables An immutable mapping type for Python. The underlying datastructure is a Hash Array Mapped Trie (HAMT) used in Clojure, Scala, Haskell, and

magicstack 996 Jan 02, 2023
A DSA repository but everything is in python.

DSA Status Contents A: Mathematics B: Bit Magic C: Recursion D: Arrays E: Searching F: Sorting G: Matrix H: Hashing I: String J: Linked List K: Stack

Shubhashish Dixit 63 Dec 23, 2022
Integrating C Buffer Data Into the instruction of `.text` segment instead of on `.data`, `.rodata` to avoid copy.

gcc-bufdata-integrating2text Integrating C Buffer Data Into the instruction of .text segment instead of on .data, .rodata to avoid copy. Usage In your

Jack Ren 1 Jan 31, 2022
A Munch is a Python dictionary that provides attribute-style access (a la JavaScript objects).

munch munch is a fork of David Schoonover's Bunch package, providing similar functionality. 99% of the work was done by him, and the fork was made mai

Infinidat Ltd. 643 Jan 07, 2023
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
Al-Quran dengan Terjemahan Indonesia

Al-Quran Rofi Al-Quran dengan Terjemahan / Tafsir Jalalayn Instalasi Al-Quran Rofi untuk Archlinux untuk pengguna distro Archlinux dengan paket manage

Nestero 4 Dec 20, 2021
dict subclass with keylist/keypath support, normalized I/O operations (base64, csv, ini, json, pickle, plist, query-string, toml, xml, yaml) and many utilities.

python-benedict python-benedict is a dict subclass with keylist/keypath support, I/O shortcuts (base64, csv, ini, json, pickle, plist, query-string, t

Fabio Caccamo 799 Jan 09, 2023