Repository: keon/algorithms
Pull request #498 (2019-04-22 06:58:09)

Update limit.py
- [X] **Consider boundary conditions**


coveralls: ## Pull Request Test Coverage Report for [Build 895](https://coveralls.io/builds/22942487)

* **3** of **4**   **(75.0%)**  changed or added relevant lines in **1** file are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage increased (+**0.02%**) to **72.208%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/arrays/limit.py](https://coveralls.io/builds/22942487/source?filename=algorithms%2Farrays%2Flimit.py#L31) | 3 | 4 | 75.0%
<!-- | **Total:** | **3** | **4** | **75.0%** | -->


|  Totals | [![Coverage Status](https://coveralls.io/builds/22942487/badge)](https://coveralls.io/builds/22942487) |
| :-- | --: |
| Change from base [Build 885](https://coveralls.io/builds/22496581): |  0.02% |
| Covered Lines: | 5373 |
| Relevant Lines: | 7441 |

---
##### 💛  - [Coveralls](https://coveralls.io)

Everfighting: > Thanks for the bug fix, minor comments added.
 
Sorry, this is my first pull-request, I don't know whether my operation is right?  
I reopen it ,and add the fix following your suggestions
travishen: > > Thanks for the bug fix, minor comments added.
> 
> Sorry, this is my first pull-request, I don't know whether my operation is right?
> I reopen it ,and add the fix following your suggestions

Hi @Everfighting, looks like you have two commit now, my suggestion is that you could use `git rebase` to squash these two commit and force update to this branch.

Patch:
diff --git a/README.md b/README.md
index e279953..d2578e3 100644
--- a/README.md
+++ b/README.md
@@ -113,6 +113,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [binary_gap](algorithms/bit/binary_gap.py)
 - [calculator](algorithms/calculator)
     - [math_parser](algorithms/calculator/math_parser.py)
+- [compression](algorithms/compression)
+    - [huffman_coding](algorithms/compression/huffman_coding.py)
 - [dfs](algorithms/dfs)
     - [all_factors](algorithms/dfs/all_factors.py)
     - [count_islands](algorithms/dfs/count_islands.py)
@@ -212,6 +214,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [copy_transform](algorithms/matrix/copy_transform.py)
     - [count_paths](algorithms/matrix/count_paths.py)
     - [matrix_rotation.txt](algorithms/matrix/matrix_rotation.txt)
+    - [matrix_multiplication](algorithms/matrix/multiply.py)
     - [rotate_image](algorithms/matrix/rotate_image.py)
     - [search_in_sorted_matrix](algorithms/matrix/search_in_sorted_matrix.py)
     - [sparse_dot_vector](algorithms/matrix/sparse_dot_vector.py)
@@ -339,6 +342,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [trie](algorithms/tree/trie)
         - [add_and_search](algorithms/tree/trie/add_and_search.py)
         - [trie](algorithms/tree/trie/trie.py)
+    - [b_tree](algorithms/tree/b_tree.py)
     - [binary_tree_paths](algorithms/tree/binary_tree_paths.py)
     - [bin_tree_to_list](algorithms/tree/bin_tree_to_list.py)
     - [deepest_left](algorithms/tree/deepest_left.py)
diff --git a/algorithms/arrays/limit.py b/algorithms/arrays/limit.py
index 131d16e..75c13d5 100644
--- a/algorithms/arrays/limit.py
+++ b/algorithms/arrays/limit.py
@@ -13,19 +13,20 @@ Complexity = O(n)
 """
 
 # tl:dr -- array slicing by value
-def limit(arr, min_lim = None, max_lim = None):
+def limit(arr, min_lim=None, max_lim=None):
     result = []
-    if min_lim == None:
+    if min_lim is None and max_lim:
         for i in arr:
             if i <= max_lim:
                 result.append(i)
-    elif max_lim == None:
+    elif max_lim is None and min_lim:
         for i in arr:
             if i >= min_lim:
                 result.append(i)
-    else:
+    elif max_lim and min_lim:
         for i in arr:
             if i >= min_lim and i <= max_lim:
                 result.append(i)
-
+    else:
+        result = arr
     return result
diff --git a/algorithms/compression/__init__.py b/algorithms/compression/__init__.py
new file mode 100644
index 0000000..e69de29
diff --git a/algorithms/compression/huffman_coding.py b/algorithms/compression/huffman_coding.py
new file mode 100644
index 0000000..44effb1
--- /dev/null
+++ b/algorithms/compression/huffman_coding.py
@@ -0,0 +1,328 @@
+"""
+Huffman coding is an efficient method of compressing data without losing information.
+This algorithm analyzes the symbols that appear in a message.
+Symbols that appear more often will be encoded as a shorter-bit string
+while symbols that aren't used as much will be encoded as longer strings.
+"""
+
+from collections import defaultdict, deque
+import heapq
+
+
+class Node:
+    def __init__(self, frequency=0, sign=None, left=None, right=None):
+        self.frequency = frequency
+        self.sign = sign
+        self.left = left
+        self.right = right
+
+    def __lt__(self, other):
+        return self.frequency < other.frequency
+
+    def __gt__(self, other):
+        return self.frequency > other.frequency
+
+    def __eq__(self, other):
+        return self.frequency == other.frequency
+
+    def __str__(self):
+        return "<ch: {0}: {1}>".format(self.sign, self.frequency)
+
+    def __repr__(self):
+        return "<ch: {0}: {1}>".format(self.sign, self.frequency)
+
+
+class HuffmanReader:
+    def __init__(self, file):
+        self.file = file
+        self.buffer = []
+        self.is_last_byte = False
+
+    def get_number_of_additional_bits_in_the_last_byte(self) -> int:
+        bin_num = self.get_bit() + self.get_bit() + self.get_bit()
+        return int(bin_num, 2)
+
+    def load_tree(self) -> Node:
+        """
+        Load tree from file
+
+        :return:
+        """
+        node_stack = deque()
+        queue_leaves = deque()
+        root = Node()
+
+        current_node = root
+        is_end_of_tree = False
+        while not is_end_of_tree:
+            current_bit = self.get_bit()
+            if current_bit == "0":
+                current_node.left = Node()
+                current_node.right = Node()
+                node_stack.append(current_node.right)  # going to left node, right push on stack
+                current_node = current_node.left
+            else:
+                queue_leaves.append(current_node)
+                if node_stack:
+                    current_node = node_stack.pop()
+                else:
+                    is_end_of_tree = True
+
+        self._fill_tree(queue_leaves)
+
+        return root
+
+    def _fill_tree(self, leaves_queue):
+        """
+        Load values to tree after reading tree
+        :param leaves_queue:
+        :return:
+        """
+        leaves_queue.reverse()
+        while leaves_queue:
+            node = leaves_queue.pop()
+            s = int(self.get_byte(), 2)
+            node.sign = s
+
+    def _load_byte(self, buff_limit=8) -> bool:
+        """
+        Load next byte is buffer is less than buff_limit
+        :param buff_limit:
+        :return: True if there is enough bits in buffer to read
+        """
+        if len(self.buffer) <= buff_limit:
+            byte = self.file.read(1)
+
+            if not byte:
+                return False
+
+            i = int.from_bytes(byte, "big")
+            self.buffer.extend(list("{0:08b}".format(i)))
+
+        return True
+
+    def get_bit(self, buff_limit=8):
+        if self._load_byte(buff_limit):
+            bit = self.buffer.pop(0)
+            return bit
+        else:
+            return -1
+
+    def get_byte(self):
+        if self._load_byte():
+            byte_list = self.buffer[:8]
+            self.buffer = self.buffer[8:]
+
+            return "".join(byte_list)
+        else:
+            return -1
+
+
+class HuffmanWriter:
+    def __init__(self, file):
+        self.file = file
+        self.buffer = ""
+        self.saved_bits = 0
+
+    def write_char(self, char):
+        self.write_int(ord(char))
+
+    def write_int(self, num):
+        bin_int = "{0:08b}".format(num)
+        self.write_bits(bin_int)
+
+    def write_bits(self, bits):
+        self.saved_bits += len(bits)
+
+        self.buffer += bits
+
+        while len(self.buffer) >= 8:
+            i = int(self.buffer[:8], 2)
+            self.file.write(bytes([i]))
+            self.buffer = self.buffer[8:]
+
+    def save_tree(self, tree):
+        """
+        Generate and save tree code to file
+        :param tree:
+        :return:
+        """
+        signs = []
+        tree_code = ""
+
+        def get_code_tree(T):
+            nonlocal tree_code
+            if T.sign is not None:
+                signs.append(T.sign)
+            if T.left:
+                tree_code += "0"
+                get_code_tree(T.left)
+            if T.right:
+                tree_code += "1"
+                get_code_tree(T.right)
+
+        get_code_tree(tree)
+        self.write_bits(tree_code + "1")  # "1" indicates that tree ended (it will be needed to load the tree)
+        for int_sign in signs:
+            self.write_int(int_sign)
+
+    def _save_information_about_additional_bits(self, additional_bits: int):
+        """
+        Overwrite first three bits in the file
+        :param additional_bits: number of bits that were appended to fill last byte
+        :return:
+        """
+        self.file.seek(0)
+        first_byte_raw = self.file.read(1)
+        self.file.seek(0)
+        first_byte = "{0:08b}".format(int.from_bytes(first_byte_raw, "big"))
+        # overwrite first three bits
+        first_byte = first_byte[3:]
+        first_byte = "{0:03b}".format(additional_bits) + first_byte
+
+        self.write_bits(first_byte)
+
+    def close(self):
+        additional_bits = 8 - len(self.buffer)
+        if additional_bits != 8:  # buffer is empty, no need to append extra "0"
+            self.write_bits("0" * additional_bits)
+            self._save_information_about_additional_bits(additional_bits)
+
+
+class TreeFinder:
+    """
+    Class to help find signs in tree
+    """
+
+    def __init__(self, tree):
+        self.root = tree
+        self.current_node = tree
+        self.found = None
+
+    def find(self, bit):
+        """
+        Find sign in tree
+        :param bit:
+        :return: True if sign is found
+        """
+        if bit == "0":
+            self.current_node = self.current_node.left
+        elif bit == "1":
+            self.current_node = self.current_node.right
+        else:
+            self._reset()
+            return True
+
+        if self.current_node.sign is not None:
+            self._reset(self.current_node.sign)
+            return True
+        else:
+            return False
+
+    def _reset(self, found=""):
+        self.found = found
+        self.current_node = self.root
+
+
+class HuffmanCoding:
+    def __init__(self):
+        pass
+
+    @staticmethod
+    def decode_file(file_in_name, file_out_name):
+        with open(file_in_name, "rb") as file_in, open(file_out_name, "wb") as file_out:
+            reader = HuffmanReader(file_in)
+            additional_bits = reader.get_number_of_additional_bits_in_the_last_byte()
+            tree = reader.load_tree()
+
+            HuffmanCoding._decode_and_write_signs_to_file(file_out, reader, tree, additional_bits)
+
+        print("File decoded.")
+
+    @staticmethod
+    def _decode_and_write_signs_to_file(file, reader: HuffmanReader, tree: Node, additional_bits: int):
+        tree_finder = TreeFinder(tree)
+        is_end_of_file = False
+
+        while not is_end_of_file:
+            bit = reader.get_bit()
+            if bit != -1:
+                while not tree_finder.find(bit):  # read whole code
+                    bit = reader.get_bit(0)
+                file.write(bytes([tree_finder.found]))
+            else:  # There is last byte in buffer to parse
+                is_end_of_file = True
+                last_byte = reader.buffer
+                last_byte = last_byte[:-additional_bits]  # remove additional "0" used to fill byte
+                for bit in last_byte:
+                    if tree_finder.find(bit):
+                        file.write(bytes([tree_finder.found]))
+
+    @staticmethod
+    def encode_file(file_in_name, file_out_name):
+        with open(file_in_name, "rb") as file_in, open(file_out_name, mode="wb+") as file_out:
+            signs_frequency = HuffmanCoding._get_char_frequency(file_in)
+            file_in.seek(0)
+            tree = HuffmanCoding._create_tree(signs_frequency)
+            codes = HuffmanCoding._generate_codes(tree)
+
+            writer = HuffmanWriter(file_out)
+            writer.write_bits("000")  # leave space to save how many bits will be appended to fill the last byte
+            writer.save_tree(tree)
+            HuffmanCoding._encode_and_write_signs_to_file(file_in, writer, codes)
+            writer.close()
+
+        print("File encoded.")
+
+    @staticmethod
+    def _encode_and_write_signs_to_file(file, writer: HuffmanWriter, codes: dict):
+        sign = file.read(1)
+        while sign:
+            int_char = int.from_bytes(sign, "big")
+            writer.write_bits(codes[int_char])
+            sign = file.read(1)
+
+    @staticmethod
+    def _get_char_frequency(file) -> dict:
+        is_end_of_file = False
+        signs_frequency = defaultdict(lambda: 0)
+        while not is_end_of_file:
+            prev_pos = file.tell()
+            sign = file.read(1)
+            curr_pos = file.tell()
+            if prev_pos == curr_pos:
+                is_end_of_file = True
+            else:
+                signs_frequency[int.from_bytes(sign, "big")] += 1
+
+        return signs_frequency
+
+    @staticmethod
+    def _generate_codes(tree: Node) -> dict:
+        codes = dict()
+        HuffmanCoding._go_through_tree_and_create_codes(tree, "", codes)
+        return codes
+
+    @staticmethod
+    def _create_tree(signs_frequency: dict) -> Node:
+        nodes = [Node(frequency=frequency, sign=char_int) for char_int, frequency in signs_frequency.items()]
+        heapq.heapify(nodes)
+
+        while len(nodes) > 1:
+            left = heapq.heappop(nodes)
+            right = heapq.heappop(nodes)
+            new_node = Node(frequency=left.frequency + right.frequency, left=left, right=right)
+            heapq.heappush(nodes, new_node)
+
+        return nodes[0]  # root
+
+    @staticmethod
+    def _go_through_tree_and_create_codes(tree: Node, code: str, dict_codes: dict):
+        if tree.sign is not None:
+            dict_codes[tree.sign] = code
+
+        if tree.left:
+            HuffmanCoding._go_through_tree_and_create_codes(tree.left, code + "0", dict_codes)
+
+        if tree.right:
+            HuffmanCoding._go_through_tree_and_create_codes(tree.right, code + "1", dict_codes)
diff --git a/algorithms/matrix/multiply.py b/algorithms/matrix/multiply.py
new file mode 100644
index 0000000..2c1cba8
--- /dev/null
+++ b/algorithms/matrix/multiply.py
@@ -0,0 +1,28 @@
+"""
+This algorithm takes two compatible two dimensional matrix
+and return their product
+Space complexity: O(n^2)
+Possible edge case: the number of columns of multiplicand not consistent with
+the number of rows of multiplier, will raise exception
+"""
+
+
+def multiply(multiplicand: list, multiplier: list) -> list:
+    """
+    :type A: List[List[int]]
+    :type B: List[List[int]]
+    :rtype: List[List[int]]
+    """
+    multiplicand_row, multiplicand_col = len(
+        multiplicand), len(multiplicand[0])
+    multiplier_row, multiplier_col = len(multiplier), len(multiplier[0])
+    if(multiplicand_col != multiplier_row):
+        raise Exception(
+            "Multiplicand matrix not compatible with Multiplier matrix.")
+    # create a result matrix
+    result = [[0] * multiplier_col for i in range(multiplicand_row)]
+    for i in range(multiplicand_row):
+        for j in range(multiplier_col):
+            for k in range(len(multiplier)):
+                result[i][j] += multiplicand[i][k] * multiplier[k][j]
+    return result
diff --git a/algorithms/matrix/rotate_image.py b/algorithms/matrix/rotate_image.py
index 21f1c74..f237fbf 100644
--- a/algorithms/matrix/rotate_image.py
+++ b/algorithms/matrix/rotate_image.py
@@ -14,13 +14,14 @@ Could you do this in-place?
 # 4 5 6  => 4 5 6  => 8 5 2
 # 7 8 9     1 2 3     9 6 3
 
-def rotate(mat): 
+def rotate(mat):
     if not mat:
         return mat
     mat.reverse()
     for i in range(len(mat)):
         for j in range(i):
             mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
+    return mat
 
 
 if __name__ == "__main__":
diff --git a/algorithms/matrix/sudoku_validator.py b/algorithms/matrix/sudoku_validator.py
index ad2faeb..7bda6e4 100644
--- a/algorithms/matrix/sudoku_validator.py
+++ b/algorithms/matrix/sudoku_validator.py
@@ -82,32 +82,3 @@ def valid_solution_set (board):
                 return False
 
     return True
-
-# test cases
-# To avoid congestion I'll leave testing all the functions to the reader. Just change the name of the function in the below test cases.
-import unittest
-class TestSuite(unittest.TestCase):
-    def test_valid(self):
-        self.assertTrue(valid_solution([[5, 3, 4, 6, 7, 8, 9, 1, 2],
-                         [6, 7, 2, 1, 9, 5, 3, 4, 8],
-                         [1, 9, 8, 3, 4, 2, 5, 6, 7],
-                         [8, 5, 9, 7, 6, 1, 4, 2, 3],
-                         [4, 2, 6, 8, 5, 3, 7, 9, 1],
-                         [7, 1, 3, 9, 2, 4, 8, 5, 6],
-                         [9, 6, 1, 5, 3, 7, 2, 8, 4],
-                         [2, 8, 7, 4, 1, 9, 6, 3, 5],
-                         [3, 4, 5, 2, 8, 6, 1, 7, 9]]))
-
-    def test_invalid(self):
-        self.assertFalse(valid_solution([[5, 3, 4, 6, 7, 8, 9, 1, 2],
-                         [6, 7, 2, 1, 9, 0, 3, 4, 9],
-                         [1, 0, 0, 3, 4, 2, 5, 6, 0],
-                         [8, 5, 9, 7, 6, 1, 0, 2, 0],
-                         [4, 2, 6, 8, 5, 3, 7, 9, 1],
-                         [7, 1, 3, 9, 2, 4, 8, 5, 6],
-                         [9, 0, 1, 5, 3, 7, 2, 1, 4],
-                         [2, 8, 7, 4, 1, 9, 6, 3, 5],
-                         [3, 0, 0, 4, 8, 1, 1, 7, 9]]))
-
-if __name__ == "__main__":
-    unittest.main()
diff --git a/algorithms/tree/b_tree.py b/algorithms/tree/b_tree.py
new file mode 100644
index 0000000..bedf31b
--- /dev/null
+++ b/algorithms/tree/b_tree.py
@@ -0,0 +1,235 @@
+"""
+B-tree is used to disk operations. Each node (except root) contains
+at least t-1 keys (t children) and at most 2*t - 1 keys (2*t children)
+where t is the degree of b-tree. It is not a kind of typical bst tree, because
+this tree grows up.
+B-tree is balanced which means that the difference between height of left subtree and right subtree is at most 1.
+
+Complexity
+    n - number of elements
+    t - degree of tree
+    Tree always has height at most logt (n+1)/2
+    Algorithm        Average        Worst case
+    Space            O(n)           O(n)
+    Search           O(log n)       O(log n)
+    Insert           O(log n)       O(log n)
+    Delete           O(log n)       O(log n)
+"""
+
+
+class Node:
+    def __init__(self):
+        # self.is_leaf = is_leaf
+        self.keys = []
+        self.children = []
+
+    def __repr__(self):
+        return "<id_node: {0}>".format(self.keys)
+
+    @property
+    def is_leaf(self):
+        return len(self.children) == 0
+
+
+class BTree:
+    def __init__(self, t=2):
+        self.min_numbers_of_keys = t - 1
+        self.max_number_of_keys = 2 * t - 1
+
+        self.root = Node()
+
+    def _split_child(self, parent: Node, child_index: int):
+        new_right_child = Node()
+        half_max = self.max_number_of_keys // 2
+        child = parent.children[child_index]
+        middle_key = child.keys[half_max]
+        new_right_child.keys = child.keys[half_max + 1:]
+        child.keys = child.keys[:half_max]
+        # child is left child of parent after splitting
+
+        if not child.is_leaf:
+            new_right_child.children = child.children[half_max + 1:]
+            child.children = child.children[:half_max + 1]
+
+        parent.keys.insert(child_index, middle_key)
+        parent.children.insert(child_index + 1, new_right_child)
+
+    def insert_key(self, key):
+        if len(self.root.keys) >= self.max_number_of_keys:  # overflow, tree increases in height
+            new_root = Node()
+            new_root.children.append(self.root)
+            self.root = new_root
+            self._split_child(new_root, 0)
+            self._insert_to_nonfull_node(self.root, key)
+        else:
+            self._insert_to_nonfull_node(self.root, key)
+
+    def _insert_to_nonfull_node(self, node: Node, key):
+        i = len(node.keys) - 1
+        while i >= 0 and node.keys[i] >= key:  # find position where insert key
+            i -= 1
+
+        if node.is_leaf:
+            node.keys.insert(i + 1, key)
+        else:
+            if len(node.children[i + 1].keys) >= self.max_number_of_keys:  # overflow
+                self._split_child(node, i + 1)
+                if node.keys[i + 1] < key:  # decide which child is going to have a new key
+                    i += 1
+
+            self._insert_to_nonfull_node(node.children[i + 1], key)
+
+    def find(self, key) -> bool:
+        current_node = self.root
+        while True:
+            i = len(current_node.keys) - 1
+            while i >= 0 and current_node.keys[i] > key:
+                i -= 1
+
+            if i >= 0 and current_node.keys[i] == key:
+                return True
+            elif current_node.is_leaf:
+                return False
+            else:
+                current_node = current_node.children[i + 1]
+
+    def remove_key(self, key):
+        self._remove_key(self.root, key)
+
+    def _remove_key(self, node: Node, key) -> bool:
+        try:
+            key_index = node.keys.index(key)
+            if node.is_leaf:
+                node.keys.remove(key)
+                return True
+            else:
+                self._remove_from_nonleaf_node(node, key_index)
+
+            return True
+
+        except ValueError:  # key not found in node
+            if node.is_leaf:
+                print("Key not found.")
+                return False  # key not found
+            else:
+                i = 0
+                number_of_keys = len(node.keys)
+                while i < number_of_keys and key > node.keys[i]:  # decide in which subtree may be key
+                    i += 1
+
+                action_performed = self._repair_tree(node, i)
+                if action_performed:
+                    return self._remove_key(node, key)
+                else:
+                    return self._remove_key(node.children[i], key)
+
+    def _repair_tree(self, node: Node, child_index: int) -> bool:
+        child = node.children[child_index]
+        if self.min_numbers_of_keys < len(child.keys) <= self.max_number_of_keys:  # The leaf/node is correct
+            return False
+
+        if child_index > 0 and len(node.children[child_index - 1].keys) > self.min_numbers_of_keys:
+            self._rotate_right(node, child_index)
+            return True
+
+        if (child_index < len(node.children) - 1 and
+                len(node.children[child_index + 1].keys) > self.min_numbers_of_keys):  # 0 <-- 1
+            self._rotate_left(node, child_index)
+            return True
+
+        if child_index > 0:
+            # merge child with brother on the left
+            self._merge(node, child_index - 1, child_index)
+        else:
+            # merge child with brother on the right
+            self._merge(node, child_index, child_index + 1)
+
+        return True
+
+    def _rotate_left(self, parent_node: Node, child_index: int):
+        """
+        Take key from right brother of the child and transfer to the child
+        """
+        new_child_key = parent_node.keys[child_index]
+        new_parent_key = parent_node.children[child_index + 1].keys.pop(0)
+        parent_node.children[child_index].keys.append(new_child_key)
+        parent_node.keys[child_index] = new_parent_key
+
+        if not parent_node.children[child_index + 1].is_leaf:
+            ownerless_child = parent_node.children[child_index + 1].children.pop(0)
+            # make ownerless_child as a new biggest child (with highest key) -> transfer from right subtree to left subtree
+            parent_node.children[child_index].children.append(ownerless_child)
+
+    def _rotate_right(self, parent_node: Node, child_index: int):
+        """
+        Take key from left brother of the child and transfer to the child
+        """
+        parent_key = parent_node.keys[child_index - 1]
+        new_parent_key = parent_node.children[child_index - 1].keys.pop()
+        parent_node.children[child_index].keys.insert(0, parent_key)
+        parent_node.keys[child_index - 1] = new_parent_key
+
+        if not parent_node.children[child_index - 1].is_leaf:
+            ownerless_child = parent_node.children[child_index - 1].children.pop()
+            # make ownerless_child as a new lowest child (with lowest key) -> transfer from left subtree to right subtree
+            parent_node.children[child_index].children.insert(0, ownerless_child)
+
+    def _merge(self, parent_node: Node, to_merge_index: int, transfered_child_index: int):
+        from_merge_node = parent_node.children.pop(transfered_child_index)
+        parent_key_to_merge = parent_node.keys.pop(to_merge_index)
+        to_merge_node = parent_node.children[to_merge_index]
+        to_merge_node.keys.append(parent_key_to_merge)
+        to_merge_node.keys.extend(from_merge_node.keys)
+
+        if not to_merge_node.is_leaf:
+            to_merge_node.children.extend(from_merge_node.children)
+
+        if parent_node == self.root and not parent_node.keys:
+            self.root = to_merge_node
+
+    def _remove_from_nonleaf_node(self, node: Node, key_index: int):
+        key = node.keys[key_index]
+        left_subtree = node.children[key_index]
+        if len(left_subtree.keys) > self.min_numbers_of_keys:
+            largest_key = self._find_largest_and_delete_in_left_subtree(left_subtree)
+        elif len(node.children[key_index + 1].keys) > self.min_numbers_of_keys:
+            largest_key = self._find_largest_and_delete_in_right_subtree(node.children[key_index + 1])
+        else:
+            self._merge(node, key_index, key_index + 1)
+            return self._remove_key(node, key)
+
+        node.keys[key_index] = largest_key
+
+    def _find_largest_and_delete_in_left_subtree(self, node: Node):
+        if node.is_leaf:
+            return node.keys.pop()
+        else:
+            ch_index = len(node.children) - 1
+            self._repair_tree(node, ch_index)
+            largest_key_in_subtree = self._find_largest_and_delete_in_left_subtree(
+                node.children[len(node.children) - 1])
+            # self._repair_tree(node, ch_index)
+            return largest_key_in_subtree
+
+    def _find_largest_and_delete_in_right_subtree(self, node: Node):
+        if node.is_leaf:
+            return node.keys.pop(0)
+        else:
+            ch_index = 0
+            self._repair_tree(node, ch_index)
+            largest_key_in_subtree = self._find_largest_and_delete_in_right_subtree(node.children[0])
+            # self._repair_tree(node, ch_index)
+            return largest_key_in_subtree
+
+    def traverse_tree(self):
+        self._traverse_tree(self.root)
+        print()
+
+    def _traverse_tree(self, node: Node):
+        if node.is_leaf:
+            print(node.keys, end=" ")
+        else:
+            for i, key in enumerate(node.keys):
+                self._traverse_tree(node.children[i])
+                print(key, end=" ")
+            self._traverse_tree(node.children[-1])


Test patch:
diff --git a/tests/test_compression.py b/tests/test_compression.py
new file mode 100644
index 0000000..611886b
--- /dev/null
+++ b/tests/test_compression.py
@@ -0,0 +1,38 @@
+from algorithms.compression.huffman_coding import HuffmanCoding
+
+import unittest
+
+
+class TestHuffmanCoding(unittest.TestCase):
+    @classmethod
+    def setUpClass(cls):
+        cls.file_in_name = "huffman_coding_in.txt"
+        cls.file_out_bin_name = "huffman_coding_out.bin"
+        cls.file_out_name = "huffman_coding_out.txt"
+
+    def setUp(self):
+        import random
+        random.seed(1951)
+        with open(self.file_in_name, "wb") as file_in:
+            for i in range(10000):
+                file_in.write(bytes([random.randrange(0, 256)]))
+
+    def test_huffman_coding(self):
+        HuffmanCoding.encode_file(self.file_in_name, self.file_out_bin_name)
+        HuffmanCoding.decode_file(self.file_out_bin_name, self.file_out_name)
+
+        with open(self.file_in_name, "rb") as file_1, open(self.file_out_name, "rb") as file_2:
+            content_1 = file_1.read()
+            content_2 = file_2.read()
+
+            self.assertEqual(content_1, content_2)
+
+    def tearDown(self):
+        import os
+        os.remove(self.file_in_name)
+        os.remove(self.file_out_bin_name)
+        os.remove(self.file_out_name)
+
+
+if __name__ == "__main__":
+    unittest.main()
diff --git a/tests/test_matrix.py b/tests/test_matrix.py
index 152727a..4d7e129 100644
--- a/tests/test_matrix.py
+++ b/tests/test_matrix.py
@@ -1,34 +1,86 @@
 from algorithms.matrix import (
-    crout_matrix_decomposition
-    )
+    bomb_enemy,
+    copy_transform,
+    crout_matrix_decomposition,
+    multiply,
+    rotate_image,
+    sparse_dot_vector,
+    spiral_traversal,
+    sudoku_validator
+)
+import unittest
 
 
-import unittest
+class TestBombEnemy(unittest.TestCase):
+    def test_3x4(self):
+        grid1 = [
+                 ["0","E","0","0"],
+                 ["E","0","W","E"],
+                 ["0","E","0","0"]
+                ]
+        self.assertEqual(3, bomb_enemy.max_killed_enemies(grid1))
+
+        grid1 = [
+                 ["0", "E", "0", "E"],
+                 ["E", "E", "E", "0"],
+                 ["E", "0", "W", "E"],
+                 ["0", "E", "0", "0"]
+                ]
+        grid2 = [
+                 ["0", "0", "0", "E"],
+                 ["E", "0", "0", "0"],
+                 ["E", "0", "W", "E"],
+                 ["0", "E", "0", "0"]
+                ]
+        self.assertEqual(5, bomb_enemy.max_killed_enemies(grid1))
+        self.assertEqual(3, bomb_enemy.max_killed_enemies(grid2))
+
+
+class TestCopyTransform(unittest.TestCase):
+    """[summary]
+    Test for the file copy_transform.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_copy_transform(self):
+        self.assertEqual(copy_transform.rotate_clockwise(
+            [[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [[7, 4, 1], [8, 5, 2], [9, 6, 3]])
+
+        self.assertEqual(copy_transform.rotate_counterclockwise(
+            [[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [[3, 6, 9], [2, 5, 8], [1, 4, 7]])
+
+        self.assertEqual(copy_transform.top_left_invert(
+            [[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [[1, 4, 7], [2, 5, 8], [3, 6, 9]])
+
+        self.assertEqual(copy_transform.bottom_left_invert(
+            [[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [[9, 6, 3], [8, 5, 2], [7, 4, 1]])
 
 
 class TestCroutMatrixDecomposition(unittest.TestCase):
     """[summary]
-    Test for the file crout_matrix_decomposition.crout_matrix_decomposition.py
+    Test for the file crout_matrix_decomposition.py
 
     Arguments:
         unittest {[type]} -- [description]
     """
-    
+
     def test_crout_matrix_decomposition(self):
         self.assertEqual(([[9.0, 0.0], [7.0, 0.0]],
                           [[1.0, 1.0], [0.0, 1.0]]),
                          crout_matrix_decomposition.crout_matrix_decomposition(
-                             [[9,9], [7,7]]))
-                         
+                             [[9, 9], [7, 7]]))
+
         self.assertEqual(([[1.0, 0.0, 0.0],
                            [3.0, -2.0, 0.0],
                            [6.0, -5.0, 0.0]],
-                           [[1.0, 2.0, 3.0],
-                            [0.0, 1.0, 2.0],
-                            [0.0, 0.0, 1.0]]),
+                          [[1.0, 2.0, 3.0],
+                           [0.0, 1.0, 2.0],
+                           [0.0, 0.0, 1.0]]),
                          crout_matrix_decomposition.crout_matrix_decomposition(
-                             [[1,2,3],[3,4,5],[6,7,8]]))
-                         
+                             [[1, 2, 3], [3, 4, 5], [6, 7, 8]]))
+
         self.assertEqual(([[2.0, 0, 0, 0],
                            [4.0, -1.0, 0, 0],
                            [6.0, -2.0, 2.0, 0],
@@ -38,9 +90,154 @@ class TestCroutMatrixDecomposition(unittest.TestCase):
                            [0, 0, 1.0, 0.0],
                            [0, 0, 0, 1.0]]),
                          crout_matrix_decomposition.crout_matrix_decomposition(
-                             [[2,1,3,1], [4,1,4,1], [6,1,7,1], [8,1,9,1]]))
-                           
-    
-        
+                             [[2, 1, 3, 1], [4, 1, 4, 1], [6, 1, 7, 1], [8, 1, 9, 1]]))
+
+
+class TestMultiply(unittest.TestCase):
+    """[summary]
+    Test for the file multiply.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_multiply(self):
+        self.assertEqual(multiply.multiply(
+            [[1, 2, 3], [2, 1, 1]], [[1], [2], [3]]), [[14], [7]])
+
+
+class TestRotateImage(unittest.TestCase):
+    """[summary]
+    Test for the file rotate_image.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_rotate_image(self):
+        self.assertEqual(rotate_image.rotate(
+            [[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [[7, 4, 1], [8, 5, 2], [9, 6, 3]])
+
+
+class TestSparseDotVector(unittest.TestCase):
+    """[summary]
+    Test for the file sparse_dot_vector.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_sparse_dot_vector(self):
+        self.assertEqual(sparse_dot_vector.dot_product(sparse_dot_vector.vector_to_index_value_list(
+            [1., 2., 3.]), sparse_dot_vector.vector_to_index_value_list([0., 2., 2.])), 10)
+
+
+class TestSpiralTraversal(unittest.TestCase):
+    """[summary]
+    Test for the file spiral_traversal.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_spiral_traversal(self):
+        self.assertEqual(spiral_traversal.spiral_traversal(
+            [[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [1, 2, 3, 6, 9, 8, 7, 4, 5])
+
+
+class TestSudokuValidator(unittest.TestCase):
+    """[summary]
+    Test for the file sudoku_validator.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_sudoku_validator(self):
+        self.assertTrue(
+            sudoku_validator.valid_solution(
+                [
+                    [5, 3, 4, 6, 7, 8, 9, 1, 2],
+                    [6, 7, 2, 1, 9, 5, 3, 4, 8],
+                    [1, 9, 8, 3, 4, 2, 5, 6, 7],
+                    [8, 5, 9, 7, 6, 1, 4, 2, 3],
+                    [4, 2, 6, 8, 5, 3, 7, 9, 1],
+                    [7, 1, 3, 9, 2, 4, 8, 5, 6],
+                    [9, 6, 1, 5, 3, 7, 2, 8, 4],
+                    [2, 8, 7, 4, 1, 9, 6, 3, 5],
+                    [3, 4, 5, 2, 8, 6, 1, 7, 9]
+                ]))
+
+        self.assertTrue(
+            sudoku_validator.valid_solution_hashtable(
+                [
+                    [5, 3, 4, 6, 7, 8, 9, 1, 2],
+                    [6, 7, 2, 1, 9, 5, 3, 4, 8],
+                    [1, 9, 8, 3, 4, 2, 5, 6, 7],
+                    [8, 5, 9, 7, 6, 1, 4, 2, 3],
+                    [4, 2, 6, 8, 5, 3, 7, 9, 1],
+                    [7, 1, 3, 9, 2, 4, 8, 5, 6],
+                    [9, 6, 1, 5, 3, 7, 2, 8, 4],
+                    [2, 8, 7, 4, 1, 9, 6, 3, 5],
+                    [3, 4, 5, 2, 8, 6, 1, 7, 9]
+                ]))
+
+        self.assertTrue(
+            sudoku_validator.valid_solution_set(
+                [
+                    [5, 3, 4, 6, 7, 8, 9, 1, 2],
+                    [6, 7, 2, 1, 9, 5, 3, 4, 8],
+                    [1, 9, 8, 3, 4, 2, 5, 6, 7],
+                    [8, 5, 9, 7, 6, 1, 4, 2, 3],
+                    [4, 2, 6, 8, 5, 3, 7, 9, 1],
+                    [7, 1, 3, 9, 2, 4, 8, 5, 6],
+                    [9, 6, 1, 5, 3, 7, 2, 8, 4],
+                    [2, 8, 7, 4, 1, 9, 6, 3, 5],
+                    [3, 4, 5, 2, 8, 6, 1, 7, 9]
+                ]))
+
+        self.assertFalse(
+            sudoku_validator.valid_solution(
+                [
+                    [5, 3, 4, 6, 7, 8, 9, 1, 2],
+                    [6, 7, 2, 1, 9, 0, 3, 4, 9],
+                    [1, 0, 0, 3, 4, 2, 5, 6, 0],
+                    [8, 5, 9, 7, 6, 1, 0, 2, 0],
+                    [4, 2, 6, 8, 5, 3, 7, 9, 1],
+                    [7, 1, 3, 9, 2, 4, 8, 5, 6],
+                    [9, 0, 1, 5, 3, 7, 2, 1, 4],
+                    [2, 8, 7, 4, 1, 9, 6, 3, 5],
+                    [3, 0, 0, 4, 8, 1, 1, 7, 9]
+                ]))
+
+        self.assertFalse(
+            sudoku_validator.valid_solution_hashtable(
+                [
+                    [5, 3, 4, 6, 7, 8, 9, 1, 2],
+                    [6, 7, 2, 1, 9, 0, 3, 4, 9],
+                    [1, 0, 0, 3, 4, 2, 5, 6, 0],
+                    [8, 5, 9, 7, 6, 1, 0, 2, 0],
+                    [4, 2, 6, 8, 5, 3, 7, 9, 1],
+                    [7, 1, 3, 9, 2, 4, 8, 5, 6],
+                    [9, 0, 1, 5, 3, 7, 2, 1, 4],
+                    [2, 8, 7, 4, 1, 9, 6, 3, 5],
+                    [3, 0, 0, 4, 8, 1, 1, 7, 9]
+                ]))
+
+        self.assertFalse(
+            sudoku_validator.valid_solution_set(
+                [
+                    [5, 3, 4, 6, 7, 8, 9, 1, 2],
+                    [6, 7, 2, 1, 9, 0, 3, 4, 9],
+                    [1, 0, 0, 3, 4, 2, 5, 6, 0],
+                    [8, 5, 9, 7, 6, 1, 0, 2, 0],
+                    [4, 2, 6, 8, 5, 3, 7, 9, 1],
+                    [7, 1, 3, 9, 2, 4, 8, 5, 6],
+                    [9, 0, 1, 5, 3, 7, 2, 1, 4],
+                    [2, 8, 7, 4, 1, 9, 6, 3, 5],
+                    [3, 0, 0, 4, 8, 1, 1, 7, 9]
+                ]))
+
+
 if __name__ == "__main__":
     unittest.main()
diff --git a/tests/test_tree.py b/tests/test_tree.py
index 1fbcd6a..912496f 100644
--- a/tests/test_tree.py
+++ b/tests/test_tree.py
@@ -6,6 +6,7 @@ from algorithms.tree.traversal import (
     inorder,
     inorder_rec
 )
+from algorithms.tree.b_tree import BTree
 
 import unittest
 
@@ -50,5 +51,62 @@ def create_tree():
     return n1
 
 
+class TestBTree(unittest.TestCase):
+
+    @classmethod
+    def setUpClass(cls):
+        import random
+        random.seed(18719)
+        cls.random = random
+        cls.range = 10000
+
+    def setUp(self):
+        self.keys_to_insert = [self.random.randrange(-self.range, self.range) for i in range(self.range)]
+
+    def test_insertion_and_find_even_degree(self):
+        btree = BTree(4)
+        for i in self.keys_to_insert:
+            btree.insert_key(i)
+
+        for i in range(100):
+            key = self.random.choice(self.keys_to_insert)
+            self.assertTrue(btree.find(key))
+
+    def test_insertion_and_find_odd_degree(self):
+        btree = BTree(3)
+        for i in self.keys_to_insert:
+            btree.insert_key(i)
+
+        for i in range(100):
+            key = self.random.choice(self.keys_to_insert)
+            self.assertTrue(btree.find(key))
+
+    def test_deletion_even_degree(self):
+        btree = BTree(4)
+        key_list = set(self.keys_to_insert)
+        for i in key_list:
+            btree.insert_key(i)
+
+        for key in key_list:
+            btree.remove_key(key)
+            self.assertFalse(btree.find(key))
+
+        self.assertEqual(btree.root.keys, [])
+        self.assertEqual(btree.root.children, [])
+
+    def test_deletion_odd_degree(self):
+        btree = BTree(3)
+        key_list = set(self.keys_to_insert)
+        for i in key_list:
+            btree.insert_key(i)
+
+        for key in key_list:
+            btree.remove_key(key)
+            self.assertFalse(btree.find(key))
+
+        self.assertEqual(btree.root.keys, [])
+        self.assertEqual(btree.root.children, [])
+
+
 if __name__ == '__main__':
     unittest.main()