btree.py

class Node:
    def __init__(self, t, is_leaf=True):
        self.t = t
        self.is_leaf = is_leaf
        self.keys = []
        self.children = []

    def is_full(self):
        return len(self.keys) == 2 * self.t - 1

    def search(self, key):
        i = 0
        n = len(self.keys)
        while i < n and key > self.keys[i]:
            i += 1
        if i < n and key == self.keys[i]:
            return (self, i)
        elif self.is_leaf:
            return None, None
        else:
            c = self.children[i]
            return c.search(key)

    def split_child(self, i):
        t = self.t
        y = self.children[i]
        z = Node(self.t, y.is_leaf)
        k = y.keys[t - 1]
        y.keys, z.keys = y.keys[: t - 1], y.keys[t:]
        if not y.is_leaf:
            y.children, z.children = y.children[:t], y.children[t:]
        self.children.insert(i + 1, z)
        self.keys.insert(i, k)

    def insert_nonfull(self, key):
        n = len(self.keys)
        i = n - 1
        if self.is_leaf:
            while i >= 0 and key < self.keys[i]:
                i -= 1
            self.keys.insert(i + 1, key)
        else:
            while i >= 0 and key < self.keys[i]:
                i -= 1
            i += 1
            c = self.children[i]
            if c.is_full():
                self.split_child(i)
                if key > self.keys[i]:
                    c = self.children[i + 1]
            c.insert_nonfull(key)


class BTree:
    def __init__(self, t):
        self.t = t
        self.root = Node(self.t, True)

    def search(self, key):
        if self.root:
            node, i = self.root.search(key)
            if node:
                return node.keys[i]
        return None

    def insert(self, key):
        if self.root.is_full():
            s = Node(self.t, False)
            s.children.append(self.root)
            s.split_child(0)
            s.insert_nonfull(key)
            self.root = s
        else:
            self.root.insert_nonfull(key)