[CLRS] [17][18] B-tree

1. B-tree?

- B-tree는 Tree Data Structure의 일종으로 Binary Tree를 확장하여,

- 하나의 노드의 차수의 최댓값이 2보다 큰 Tree 라고 말 할 수 있다.

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree

[자료구조] 그림으로 알아보는 B-Tree

- B-tree에 대해 자료를 수집하는 중, 가장 정리가 잘된 블로그를 공유한다. 

- B-tree의 개념은 해당 링크를 타서 학습하고, 코드 구현은 나의 블로그를 참고하기 바란다.

2. B-tree의 특징

'''

최대M개의 자식을 가질 수 있는 B-tree를 M차 B-tree라고 한다.

1. 노드는 최대 M개부터 M / 2개 까지의 자식을 가질 수 있다.(정렬되어 있는 상태다)

2. 노드에는 최대 M-1개부터 [M/2]-1 개의 키가 포함가능하다.

3. 노드의 키가 x개라면 자식의 수는 x + 1개이다.

4. 최소차수가 t라면 M = 2t-1을 만조한다. 

'''

 

3. Code구현

class BTreeNode:
    def __init__(self, t, is_leaf=True):
        self.t = t  # 최소 차수 (degree)
        self.keys = []  # 키들을 저장
        self.children = []  # 자식 노드를 저장
        self.is_leaf = is_leaf  # Leaf 노드 여부

    def traverse(self):
        """노드의 키들을 출력"""
        i = 0
        for i in range(len(self.keys)):
            if not self.is_leaf:
                self.children[i].traverse()
            print(self.keys[i], end=" ")
        if not self.is_leaf:
            self.children[i + 1].traverse()

    def search(self, k):
        """키 k를 검색"""
        i = 0
        while i < len(self.keys) and k > self.keys[i]:
            i += 1
        if i < len(self.keys) and self.keys[i] == k:
            return self
        if self.is_leaf:
            return None
        return self.children[i].search(k)

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

    def traverse(self):
        """B-트리를 출력"""
        if self.root is not None:
            self.root.traverse()

    def search(self, k):
        """키 k를 검색"""
        if self.root is None:
            return None
        else:
            return self.root.search(k)

    def insert(self, k):
        """키 k를 삽입"""
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            # 루트가 가득 찼을 경우 분리
            s = BTreeNode(self.t, is_leaf=False)
            self.root = s
            s.children.append(root)
            self._split_child(s, 0)
            self._insert_non_full(s, k)
        else:
            self._insert_non_full(root, k)

    def _insert_non_full(self, x, k):
        """노드가 가득 차지 않았을 때 삽입"""
        i = len(x.keys) - 1
        if x.is_leaf:
            # Leaf 노드에 삽입
            x.keys.append(None)
            while i >= 0 and k < x.keys[i]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            # 자식으로 내려가기
            while i >= 0 and k < x.keys[i]:
                i -= 1
            i += 1
            if len(x.children[i].keys) == 2 * self.t - 1:
                self._split_child(x, i)
                if k > x.keys[i]:
                    i += 1
            self._insert_non_full(x.children[i], k)

    def _split_child(self, x, i):
        """자식 노드를 분리"""
        t = self.t
        y = x.children[i]
        z = BTreeNode(t, is_leaf=y.is_leaf)
        x.keys.insert(i, y.keys[t - 1])
        x.children.insert(i + 1, z)

        # z로 키와 자식들을 옮기기
        z.keys = y.keys[t:]
        y.keys = y.keys[:t - 1]
        if not y.is_leaf:
            z.children = y.children[t:]
            y.children = y.children[:t]

    def delete(self, k):
        """키 k를 삭제"""
        if not self.root:
            print("트리가 비어있습니다.")
            return
        self._delete(self.root, k)
        if len(self.root.keys) == 0:
            if self.root.is_leaf:
                self.root = None
            else:
                self.root = self.root.children[0]

    def _delete(self, node, k):
        t = self.t
        i = 0
        while i < len(node.keys) and k > node.keys[i]:
            i += 1

        # 1. 키가 노드에 존재하는 경우
        if i < len(node.keys) and node.keys[i] == k:
            if node.is_leaf:
                node.keys.pop(i)  # Leaf에서 바로 삭제
            else:
                self._delete_internal_node(node, k, i)
        elif not node.is_leaf:
            self._delete_non_leaf(node, k, i)
        else:
            print(f"키 {k}가 트리에서 존재하지 않습니다.")

    def _delete_internal_node(self, node, k, i):
        t = self.t
        if len(node.children[i].keys) >= t:
            # 전임자 키 사용
            pred = self._get_predecessor(node, i)
            node.keys[i] = pred
            self._delete(node.children[i], pred)
        elif len(node.children[i + 1].keys) >= t:
            # 후임자 키 사용
            succ = self._get_successor(node, i)
            node.keys[i] = succ
            self._delete(node.children[i + 1], succ)
        else:
            # 병합 후 삭제
            self._merge(node, i)
            self._delete(node.children[i], k)

    def _delete_non_leaf(self, node, k, i):
        t = self.t
        child = node.children[i]
        if len(child.keys) >= t:
            self._delete(child, k)
        elif i != len(node.keys) and len(node.children[i + 1].keys) >= t:
            self._borrow_from_next(node, i)
            self._delete(child, k)
        elif i != 0 and len(node.children[i - 1].keys) >= t:
            self._borrow_from_prev(node, i)
            self._delete(child, k)
        else:
            if i != len(node.keys):
                self._merge(node, i)
            else:
                self._merge(node, i - 1)
            self._delete(node.children[i], k)

    def _get_predecessor(self, node, i):
        current = node.children[i]
        while not current.is_leaf:
            current = current.children[-1]
        return current.keys[-1]

    def _get_successor(self, node, i):
        current = node.children[i + 1]
        while not current.is_leaf:
            current = current.children[0]
        return current.keys[0]

    def _borrow_from_prev(self, node, i):
        child = node.children[i]
        sibling = node.children[i - 1]
        child.keys.insert(0, node.keys[i - 1])
        node.keys[i - 1] = sibling.keys.pop(-1)
        if not sibling.is_leaf:
            child.children.insert(0, sibling.children.pop(-1))

    def _borrow_from_next(self, node, i):
        child = node.children[i]
        sibling = node.children[i + 1]
        child.keys.append(node.keys[i])
        node.keys[i] = sibling.keys.pop(0)
        if not sibling.is_leaf:
            child.children.append(sibling.children.pop(0))

    def _merge(self, node, i):
        child = node.children[i]
        sibling = node.children[i + 1]
        child.keys.append(node.keys.pop(i))
        child.keys.extend(sibling.keys)
        if not child.is_leaf:
            child.children.extend(sibling.children)
        node.children.pop(i + 1)