Left Leaning Red Black Tree

lldb.py

class LLRB(object):

    class Node(object):
        RED = True
        BLACK = False

        __slots__ = ['value', 'left', 'right', 'color']

        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None
            self.color = LLRB.Node.RED


        def flip_colors(self):
            self.color = not self.color
            self.left.color = not self.left.color
            self.right.color = not self.right.color


    def __init__(self):
        self.root = None


    def search_higher(self, value):
        """Return the smallest item greater than or equal to value.  If no such value
        can be found, return 0.

        """
        x = self.root
        best = None
        while x is not None:
            if x.value == value:
                return value
            elif x.value < value:
                x = x.left
            else:
                best = x.value if best is None else min(best, x.value)
                x = x.right

        return 0 if best is None else best

    @staticmethod
    def is_red(node):
        if node is None:
            return False
        else:
            return node.color == LLRB.Node.RED


    def insert(self, value):
        self.root = LLRB.insert_at(self.root, value)
        self.root.color = LLRB.Node.BLACK


    @staticmethod
    def insert_at(node, value):
        if node is None:
            return LLRB.Node(value)

        if LLRB.is_red(node.left) and LLRB.is_red(node.right):
            node.flip_colors()

        if node.value == value:
            node.value = value
        elif node.value < value:
            node.left = LLRB.insert_at(node.left, value)
        else:
            node.right = LLRB.insert_at(node.right, value)


        if LLRB.is_red(node.right) and not LLRB.is_red(node.left):
            node = LLRB.rotate_left(node)
        if LLRB.is_red(node.left) and LLRB.is_red(node.left.left):
            node = LLRB.rotate_right(node)

        return node