red-black trees

.README.md

Makefile

q:
	python3.8 node.py
	python3.8 rbtree.py
all:
	python3 redblack.py
clean:
	rm -fr *.pyc __pycache__

node.py

class node(object):
    def __init__(self, v): self.d = [None, v, None]
    def __getindex__(self, k): return self.d[k+1]
    def __setindex__(self, k, v): self.d[k+1] = v
    pass


def insert_node(n, x, path = None):
    if path is None: path = []
    if not n: path.append(x); return path
    path.append(n)
    d = -1 if x < n[0] else 1
    if n[d]: insert_node(n[d], x, path)
    else:    n[d] = x; path.append(x)
    return path


def rotate(t, p, d):
    x = p[-d]; p[-d] = x[d]; x[d] = p
    return x if p == t else t
    

rbtree.py

from node import *


def color(x): return x.c if x else 'b'


def _adjust_rb(j):
    t = j[0]; x = j.pop(); x.c = 'r'
    while t != x and color(x.p) == 'r':
        p = j.pop(); g = j.pop()
        d = 1 if g[-1] == p else -1
        if color(g[ d])=='b':
            if   p[ d] == x: p = rotate(t, p, -d)
            g.c, p.c = 'rb'; t = rotate(t, g,  d)
            break
        x = g; g[-1].c, g.c, g[1].c = 'brb'
        pass
    t.c = 'b'
    return t


def insert_node_rb(n, x):
    return _adjust_rb(insert_node(n, x))


def insert_rb(n, v):
    return insert_node_rb(n, node(v))