# Path: pyalgs/data_structures/commons/binary_search_tree.py
# 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)
# 
#         if compared < 0:
#             x.left = self._put(x.left, key, value)
#         elif compared > 0:
#             x.right = self._put(x.right, key, value)
#         else:
#             x.value = value
# 
#         x.count = 1 + _count(x.left) + _count(x.right)
# 
#         return x
# 
#     def get(self, key):
#         x = self._get(self.root, key)
#         if x is None:
#             return None
#         return x.value
# 
#     def _get(self, x, key):
#         if x is None:
#             return None
#         compared = cmp(key, x.key)
#         if compared < 0:
#             return self._get(x.left, key)
#         elif compared > 0:
#             return self._get(x.right, key)
#         else:
#             return x
# 
#     def size(self):
#         return _count(self.root)
# 
#     def is_empty(self):
#         return self.root is None
# 
#     def delete(self, key):
#         self.root = self._delete(self.root, key)
# 
#     def _delete(self, x, key):
#         if x is None:
#             return None
# 
#         compared = cmp(key, x.key)
#         if compared < 0:
#             x.left = self._delete(x.left, key)
#         elif compared > 0:
#             x.right = self._delete(x.right, key)
#         else:
#             if x.left is None:
#                 return x.right
#             elif x.right is None:
#                 return x.left
#             else:
#                 m = self.min(x.right)
#                 m.right = self.del_min(x.right)
#                 m.left = x.left
# 
#                 x = m
# 
#         x.count = 1 + _count(x.left) + _count(x.right)
#         return x
# 
#     def min(self, x):
#         if x.left is None:
#             return x
#         return self.min(x.left)
# 
#     def del_min(self, x):
#         if x.left is None:
#             return x.right
#         x.left = self.del_min(x.left)
#         return x
# 
#     def contains_key(self, x):
#         return self.get(x) is not None
# 
#     def keys(self):
#         queue = Queue.create()
#         self.collect_keys(self.root, queue)
#         return queue.iterate()
# 
#     def collect_keys(self, x, queue):
#         if x is None:
#             return
# 
#         self.collect_keys(x.left, queue)
#         queue.enqueue(x.key)
#         self.collect_keys(x.right, queue)
# 
#     @staticmethod
#     def create():
#         return BinarySearchTree()
# 
#     @staticmethod
#     def create_red_black_tree():
#         return RedBlackTree()


import unittest
from pyalgs.data_structures.commons.binary_search_tree import BinarySearchTree
        self.assertFalse(bst.is_empty())

        bst.delete("one")
        self.assertFalse(bst.contains_key("one"))
        self.assertEqual(4, bst.size())

        bst.delete("ten")
        self.assertFalse(bst.contains_key("ten"))
        self.assertEqual(3, bst.size())

        bst.delete("three")
        self.assertFalse(bst.contains_key("three"))
        self.assertEqual(2, bst.size())

        for i in range(100):
            bst.put(str(i), i)
            self.assertEqual(i, bst.get(str(i)))

        for key in bst.keys():
            print(key)

        for i in range(100):
            bst.delete(str(i))
            self.assertFalse(bst.contains_key(str(i)))




class RedBlackTreeUnitTest(unittest.TestCase):
    def test_binarySearchTree(self):

# Path: pyalgs/data_structures/commons/binary_search_tree.py
# 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)
# 
#         if compared < 0:
#             x.left = self._put(x.left, key, value)
#         elif compared > 0:
#             x.right = self._put(x.right, key, value)
#         else:
#             x.value = value
# 
#         x.count = 1 + _count(x.left) + _count(x.right)
# 
#         return x
# 
#     def get(self, key):
#         x = self._get(self.root, key)
#         if x is None:
#             return None
#         return x.value
# 
#     def _get(self, x, key):
#         if x is None:
#             return None
#         compared = cmp(key, x.key)
#         if compared < 0:
#             return self._get(x.left, key)
#         elif compared > 0:
#             return self._get(x.right, key)
#         else:
#             return x
# 
#     def size(self):
#         return _count(self.root)
# 
#     def is_empty(self):
#         return self.root is None
# 
#     def delete(self, key):
#         self.root = self._delete(self.root, key)
# 
#     def _delete(self, x, key):
#         if x is None:
#             return None
# 
#         compared = cmp(key, x.key)
#         if compared < 0:
#             x.left = self._delete(x.left, key)
#         elif compared > 0:
#             x.right = self._delete(x.right, key)
#         else:
#             if x.left is None:
#                 return x.right
#             elif x.right is None:
#                 return x.left
#             else:
#                 m = self.min(x.right)
#                 m.right = self.del_min(x.right)
#                 m.left = x.left
# 
#                 x = m
# 
#         x.count = 1 + _count(x.left) + _count(x.right)
#         return x
# 
#     def min(self, x):
#         if x.left is None:
#             return x
#         return self.min(x.left)
# 
#     def del_min(self, x):
#         if x.left is None:
#             return x.right
#         x.left = self.del_min(x.left)
#         return x
# 
#     def contains_key(self, x):
#         return self.get(x) is not None
# 
#     def keys(self):
#         queue = Queue.create()
#         self.collect_keys(self.root, queue)
#         return queue.iterate()
# 
#     def collect_keys(self, x, queue):
#         if x is None:
#             return
# 
#         self.collect_keys(x.left, queue)
#         queue.enqueue(x.key)
#         self.collect_keys(x.right, queue)
# 
#     @staticmethod
#     def create():
#         return BinarySearchTree()
# 
#     @staticmethod
#     def create_red_black_tree():
#         return RedBlackTree()


# Path: tests/data_structures/commons/binary_search_tree_unit_test.py
import unittest
from pyalgs.data_structures.commons.binary_search_tree import BinarySearchTree

        self.assertFalse(bst.is_empty())

        bst.delete("one")
        self.assertFalse(bst.contains_key("one"))
        self.assertEqual(4, bst.size())

        bst.delete("ten")
        self.assertFalse(bst.contains_key("ten"))
        self.assertEqual(3, bst.size())

        bst.delete("three")
        self.assertFalse(bst.contains_key("three"))
        self.assertEqual(2, bst.size())

        for i in range(100):
            bst.put(str(i), i)
            self.assertEqual(i, bst.get(str(i)))

        for key in bst.keys():
            print(key)

        for i in range(100):
            bst.delete(str(i))
            self.assertFalse(bst.contains_key(str(i)))




class RedBlackTreeUnitTest(unittest.TestCase):
    def test_binarySearchTree(self):

        bst = BinarySearchTree.create_red_black_tree()