btree is used to disk operations each node except root contains at least t1 keys t children and at most 2t 1 keys 2t children where t is the degree of btree it is not a kind of typical bst tree because this tree grows up btree 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 n12 algorithm average worst case space on on search olog n olog n insert olog n olog n delete olog n olog n class of node def initself self isleaf isleaf self keys self children def reprself return idnode 0 formatself keys property def isleafself class of btree def initself tval2 self minnumbersofkeys tval 1 self maxnumberofkeys 2 tval 1 self root node def splitchildself parent node childindex int newrightchild node halfmax self maxnumberofkeys 2 child parent childrenchildindex middlekey child keyshalfmax newrightchild keys child keyshalfmax 1 child keys child keys halfmax child is left child of parent after splitting if not child isleaf newrightchild children child childrenhalfmax 1 child children child children halfmax 1 parent keys insertchildindex middlekey parent children insertchildindex 1 newrightchild def insertkeyself key overflow decide which child is going to have a new key finds key currentnode self root while true i lencurrentnode keys 1 while i 0 and currentnode keysi key i 1 if i 0 and currentnode keysi key return true if currentnode isleaf return false currentnode currentnode childreni 1 def removekeyself key self removekeyself root key def removekeyself node node key bool try keyindex node keys indexkey if node isleaf node keys removekey else self removefromnonleafnodenode keyindex return true except valueerror key not found in node if node isleaf printkey not found return false key not found else i 0 numberofkeys lennode keys decide in which subtree may be key while i numberofkeys and key node keysi i 1 actionperformed self repairtreenode i if actionperformed return self removekeynode key else return self removekeynode childreni key def repairtreeself node node childindex int bool child node childrenchildindex the leafnode is correct if self minnumbersofkeys lenchild keys self maxnumberofkeys return false if childindex 0 and lennode childrenchildindex 1 keys self minnumbersofkeys self rotaterightnode childindex return true if childindex lennode children 1 and lennode childrenchildindex 1 keys self minnumbersofkeys 0 1 self rotateleftnode childindex return true if childindex 0 merge child with brother on the left self mergenode childindex 1 childindex else merge child with brother on the right self mergenode childindex childindex 1 return true def rotateleftself parentnode node childindex int newchildkey parentnode keyschildindex newparentkey parentnode childrenchildindex 1 keys pop0 parentnode childrenchildindex keys appendnewchildkey parentnode keyschildindex newparentkey if not parentnode childrenchildindex 1 isleaf ownerlesschild parentnode childrenchildindex 1 children pop0 make ownerlesschild as a new biggest child with highest key transfer from right subtree to left subtree parentnode childrenchildindex children appendownerlesschild def rotaterightself parentnode node childindex int parentkey parentnode keyschildindex 1 newparentkey parentnode childrenchildindex 1 keys pop parentnode childrenchildindex keys insert0 parentkey parentnode keyschildindex 1 newparentkey if not parentnode childrenchildindex 1 isleaf ownerlesschild parentnode childrenchildindex 1 children pop make ownerlesschild as a new lowest child with lowest key transfer from left subtree to right subtree parentnode childrenchildindex children insert 0 ownerlesschild def mergeself parentnode node tomergeindex int transferedchildindex int frommergenode parentnode children poptransferedchildindex parentkeytomerge parentnode keys poptomergeindex tomergenode parentnode childrentomergeindex tomergenode keys appendparentkeytomerge tomergenode keys extendfrommergenode keys if not tomergenode isleaf tomergenode children extendfrommergenode children if parentnode self root and not parentnode keys self root tomergenode def removefromnonleafnodeself node node keyindex int key node keyskeyindex leftsubtree node childrenkeyindex if lenleftsubtree keys self minnumbersofkeys largestkey self findlargestanddeleteinleftsubtree leftsubtree elif lennode childrenkeyindex 1 keys self minnumbersofkeys largestkey self findlargestanddeleteinrightsubtree node childrenkeyindex 1 else self mergenode keyindex keyindex 1 return self removekeynode key node keyskeyindex largestkey def findlargestanddeleteinleftsubtreeself node node if node isleaf return node keys pop else chindex lennode children 1 self repairtreenode chindex largestkeyinsubtree self findlargestanddeleteinleftsubtree node childrenlennode children 1 self repairtreenode chindex return largestkeyinsubtree def findlargestanddeleteinrightsubtreeself node node if node isleaf return node keys pop0 else chindex 0 self repairtreenode chindex largestkeyinsubtree self findlargestanddeleteinrightsubtree node children0 self repairtreenode chindex return largestkeyinsubtree def traversetreeself self traversetreeself root print def traversetreeself node node if node isleaf printnode keys end else for i key in enumeratenode keys self traversetreenode childreni printkey end self traversetreenode children1 class of node self is_leaf is_leaf return if it is a leaf class of btree child is left child of parent after splitting overflow tree increases in height find position where insert key overflow decide which child is going to have a new key finds key key not found in node key not found decide in which subtree may be key the leaf node is correct 0 1 merge child with brother on the left merge child with brother on the right take key from right brother of the child and transfer to the child make ownerless_child as a new biggest child with highest key transfer from right subtree to left subtree take key from left brother of the child and transfer to the child make ownerless_child as a new lowest child with lowest key transfer from left subtree to right subtree self _repair_tree node ch_index self _repair_tree node ch_index
class Node:
    

    def __init__(self):
        
        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_val=2):
        self.min_numbers_of_keys = t_val - 1
        self.max_number_of_keys = 2 * t_val - 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]
        

        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:
            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:  
            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:
                self._split_child(node, i + 1)
                
                if node.keys[i + 1] < 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
            if current_node.is_leaf:
                return False
            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)
            else:
                self._remove_from_nonleaf_node(node, key_index)
            return True

        except ValueError:  
            if node.is_leaf:
                print("Key not found.")
                return False  
            else:
                i = 0
                number_of_keys = len(node.keys)
                
                while i < number_of_keys and key > node.keys[i]:
                    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:
            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):  
            self._rotate_left(node, child_index)
            return True

        if child_index > 0:
            
            self._merge(node, child_index - 1, child_index)
        else:
            
            self._merge(node, child_index, child_index + 1)

        return True

    def _rotate_left(self, parent_node: Node, child_index: int):
        
        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)
            
            
            parent_node.children[child_index].children.append(ownerless_child)

    def _rotate_right(self, parent_node: Node, child_index: int):
        
        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()
            
            
            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])
            
            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])
            
            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])