B Tree - insertion 구현(reactive way) Java

Chan Young Jeong·2023년 3월 19일
0

B 트리에서 삽입 방식을 구현하는 방식은 2가지로 나뉩니다.

대부분의 B 트리의 삽입 방식을 설명하는 것이
첫 번째로 삽입될 leaf노드의 위치를 찾는다.
두 번째로 삽입 후에 해당 노드가 넘치면 split하는 방식입니다.
이 방식을 reactive한 방식이라고 합니다. 혹은 insertion without aggressive splitting이라고도 합니다.

그래서 이 방식으로 코드를 작성하기 위해 다른 코드들을 참고하면 뭔가 이상합니다. 대부분의 블로그에서 포스팅하고 있는 insertion 방식은 proactive한 방식입니다.

두 방식의 차이는 split을 언제해주냐 차이입니다.

reactive 방식은 split이 필요할 때만 해주는 반면 proactive 방식은 미리 split을 합니다.

먼저 reactive 방식부터 보겠습니다.

1~5까지 차례대로 삽입

6 삽입
6을 삽입하면 leaf 노드가 넘치기 때문에 split을 해줘야 합니다.

7~16까지 차례대로 삽입

22~30까지 차례대로 삽입

17 삽입
여기서 reactive와 proactive 방식이 차이를 보입니다. reactive 방식 같은 경우는 split을 해야만 하는 상황에 반응해서 split을 합니다. 그렇기 때문에 17이 들어갈 leaf 노드는 넘치지 않았기 때문에 split을 해줄 필요가 없습니다. 그래서 17을 삽입한 후에 모습은 다음과 같습니다.

proactive 방식은 노드가 넘칠 것을 염려해서 미리 split 해주는 것입니다.
현재 root 노드는 4 8 12 16 25로 꽉 차있기 때문에 만약 여기서 leaf노드가 넘쳐 부모 노드로 자식 노드의 키가 올라 온다면 부모 노드가 넘치는 상황이 발생해서 이를 염려해 미리 split하는 것입니다. 그럼 다음과 같은 모습이 됩니다.

proactive 방식 같은 경우는 미리 split하기 때문에 node를 두번 순회할 필요가 없습니다. 하지만 split할 필요가 없는 상황에서도 split이 발생할 수 있습니다.
reactive 방식 같은 경우는 배운 방식대로 코드를 작성할 수 있어 이해하기 쉽다는 점입니다. 하지만 split을 하는 과정에서 node를 두번 순회해야하는 단점이 존재합니다.

The advantage of splitting before is, we never traverse a node twice. If we don’t split a node before going down to it and split it only if a new key is inserted (reactive), we may end up traversing all nodes again from leaf to root. This happens in cases when all nodes on the path from the root to leaf are full. So when we come to the leaf node, we split it and move a key up. Moving a key up will cause a split in parent node (because the parent was already full). This cascading effect never happens in this proactive insertion algorithm. There is a disadvantage of this proactive insertion though, we may do unnecessary splits.

많은 블로그에서 proactive 방식의 코드는 확인할 수 있기 때문에 reactive 방식으로 코드를 작성하였습니다.


package datastructure;

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.OptionalInt;

public class BTree {


    private int T;
    private Node root;
    private Node newNode;
    private OptionalInt val;


    public BTree(int t) {
        T = t;
        root = new Node();
        root.leaf = true;
        newNode = null;
        val = OptionalInt.empty();
    }


    class Node{
        List<Integer> key = new ArrayList<>(); // KEY는  최대 2*T-1개
        List<Node> children = new ArrayList<>(); // 자식은 최대 2*T개
        boolean leaf = true; // 해당 노드가 leaf 노드인지 아닌지

    }


    public void insert(int key) {

        newNode = null;
        val = OptionalInt.empty();

        _insert(key, root);

        if (newNode != null) {
            Node newRoot = new Node();
            newRoot.leaf = false;

            newRoot.key.add(val.getAsInt());
            newRoot.children.add(root);
            newRoot.children.add(newNode);

            root = newRoot;
        }
    }

    public void _insert(int key, Node curNode) {

        if (curNode.leaf == true) {
            int pos = lowerBound(curNode.key, key);
            curNode.key.add(pos, key);

            if (curNode.key.size() == 2 * T) {
                newNode = new Node();
                newNode.leaf = true;

                val = OptionalInt.of(curNode.key.get(T)); // 승급할 key

                for (int i = T + 1; i < 2 * T; i++) {
                    newNode.key.add(curNode.key.get(i));
                }

                curNode.key = curNode.key.subList(0, T);
            }

        }
        else{
            int i = 0;
            while (i < curNode.key.size() && key > curNode.key.get(i)) {
                i++;
            }

            _insert(key, curNode.children.get(i));

            if (newNode == null) {  // 더이상 split 필요 x
                return;
            }

            if (curNode.key.size() < 2 * T - 1) {
                curNode.key.add(i, val.getAsInt());
                curNode.children.add(i+1,newNode);
                newNode = null;
            }else{
                curNode.key.add(i, val.getAsInt());
                curNode.children.add(i + 1, newNode);

                split(curNode);
            }

        }

    }

    private void split(Node curNode) {
        newNode = new Node();
        newNode.leaf = false;

        val = OptionalInt.of(curNode.key.get(T));
        for (int i = T + 1; i < 2 * T; i++) {
            newNode.key.add(curNode.key.get(i));
        }
        curNode.key = curNode.key.subList(0, T);

        for (int i = T+1; i <= 2 * T; i++) {
            newNode.children.add(curNode.children.get(i));
        }

        curNode.children = curNode.children.subList(0, T + 1);

    }

    private static int lowerBound(List<Integer> data ,int target) {
        int begin = 0;
        int end = data.size();

        while(begin < end) {
            int mid = (begin + end) / 2;

            if(data.get(mid) >= target) {
                end = mid;
            }
            else {
                begin = mid + 1;
            }
        }
        return end;
    }

    void traverse() {
        _traverse(root,0);
    }

    void _traverse(Node node,int tab)
    {
        int i;
        String s = "";

        // Print 'tab' number of tabs
        for (int j = 0; j < tab; j++) {
            s += "\t";
        }
        for (i = 0; i < node.key.size(); i++) {

            // If this is not leaf, then before printing key[i]
            // traverse the subtree rooted with child C[i]
            if (node.leaf == false)
                _traverse(node.children.get(i),tab + 1);

            System.out.println(s + node.key.get(i));

        }

        // Print the subtree rooted with last child
        if (node.leaf == false) {
            _traverse(node.children.get(i),tab + 1);
        }
    }
    public static void main(String[] args) {
        BTree bTree = new BTree(3);



        bTree.insert(1);
        bTree.insert(2);
        bTree.traverse();

        bTree.insert(5);
        bTree.insert(6);
        bTree.traverse();

        bTree.insert(3);
        bTree.insert(4);
        bTree.traverse();






  /*      bTree.insert(1);
        bTree.insert(15);
        bTree.insert(2);
        bTree.insert(5);
        bTree.insert(30);
        bTree.insert(90);
        bTree.insert(20);
        bTree.insert(7);
        bTree.insert(9);
        bTree.insert(8);
        bTree.insert(10);
        bTree.insert(50);
        bTree.insert(70);
        bTree.insert(60);
        bTree.insert(40);*/


    }
}

출처
geeksforgeeks-b tree insert without aggressive splitting
geeksforgeeks-insert operation in b tree

0개의 댓글