Repository: keon/algorithms
Pull request #501 (2019-05-01 19:02:20)

Add b-tree
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [x] **If creating a new file :**
  - [x] added links to it in the README files ?
  - [x] included tests with it ?
  - [x] added description (overview of algorithm, time and space compleixty, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


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

* **397** of **436**   **(91.06%)**  changed or added relevant lines in **4** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage increased (+**0.9%**) to **75.66%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [tests/test_compression.py](https://coveralls.io/builds/23132662/source?filename=tests%2Ftest_compression.py#L38) | 26 | 27 | 96.3%
| [algorithms/tree/b_tree.py](https://coveralls.io/builds/23132662/source?filename=algorithms%2Ftree%2Fb_tree.py#L27) | 133 | 151 | 88.08%
| [algorithms/compression/huffman_coding.py](https://coveralls.io/builds/23132662/source?filename=algorithms%2Fcompression%2Fhuffman_coding.py#L23) | 195 | 215 | 90.7%
<!-- | **Total:** | **397** | **436** | **91.06%** | -->


|  Totals | [![Coverage Status](https://coveralls.io/builds/23132662/badge)](https://coveralls.io/builds/23132662) |
| :-- | --: |
| Change from base [Build 898](https://coveralls.io/builds/23075108): |  0.9% |
| Covered Lines: | 5987 |
| Relevant Lines: | 7913 |

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


Patch:
diff --git a/README.md b/README.md
index 89def9e..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)
@@ -340,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/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/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_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()