# Path: pyalgs/algorithms/commons/util.py
# def cmp(a, b):
#     if a is None:
#         return -1
#     if b is None:
#         return -1
#     return (a > b) - (a < b)
# 
# Path: pyalgs/data_structures/commons/queue.py
# class Queue(object):
#     """ Queue interface
#     
#     """
# 
#     __metaclass__ = ABCMeta
# 
#     @abstractmethod
#     def enqueue(self, item):
#         pass
# 
#     @abstractmethod
#     def dequeue(self):
#         pass
# 
#     @abstractmethod
#     def is_empty(self):
#         pass
# 
#     @abstractmethod
#     def size(self):
#         pass
# 
#     @staticmethod
#     def create():
#         return LinkedListQueue()
# 
#     @abstractmethod
#     def iterate(self):
#         pass


from abc import ABCMeta
from pyalgs.algorithms.commons.util import cmp
from pyalgs.data_structures.commons.queue import Queue

    def __init__(self, key, value, red=None):
        self.key = key
        self.value = value
        self.count = 1

        if red is not None:
            self.red = red
        else:
            self.red = 0


def _count(x):
    if x is None:
        return 0
    return x.count


class BinarySearchTree(object):
    __metaclass__ = ABCMeta

    root = None

    def put(self, key, value):
        self.root = self._put(self.root, key, value)

    def _put(self, x, key, value):
        if x is None:
            return Node(key, value)


# Path: pyalgs/algorithms/commons/util.py
# def cmp(a, b):
#     if a is None:
#         return -1
#     if b is None:
#         return -1
#     return (a > b) - (a < b)
# 
# Path: pyalgs/data_structures/commons/queue.py
# class Queue(object):
#     """ Queue interface
#     
#     """
# 
#     __metaclass__ = ABCMeta
# 
#     @abstractmethod
#     def enqueue(self, item):
#         pass
# 
#     @abstractmethod
#     def dequeue(self):
#         pass
# 
#     @abstractmethod
#     def is_empty(self):
#         pass
# 
#     @abstractmethod
#     def size(self):
#         pass
# 
#     @staticmethod
#     def create():
#         return LinkedListQueue()
# 
#     @abstractmethod
#     def iterate(self):
#         pass


# Path: pyalgs/data_structures/commons/binary_search_tree.py
from abc import ABCMeta
from pyalgs.algorithms.commons.util import cmp
from pyalgs.data_structures.commons.queue import Queue


    def __init__(self, key, value, red=None):
        self.key = key
        self.value = value
        self.count = 1

        if red is not None:
            self.red = red
        else:
            self.red = 0


def _count(x):
    if x is None:
        return 0
    return x.count


class BinarySearchTree(object):
    __metaclass__ = ABCMeta

    root = None

    def put(self, key, value):
        self.root = self._put(self.root, key, value)

    def _put(self, x, key, value):
        if x is None:
            return Node(key, value)


        compared = cmp(key, x.key)