Krafton_jungle 5기 13일차 TIL - B-Tree, 알고리즘

 자료구조

B-Tree

B트리란?	B트리는 디스크나 다른 직접 접근 보조 기억장치에서 잘 동작하도록 설계된 균형잡힌 트리이다.
B트리의 특징	이진트리와 다르게 하나의 노드에 여러개의 값을 가질 수 있다. 최대 M(B트리의 차수)개의 자식노드를 가질 수 있다. 3차 B트리라면 3개의 자식을 가질 수 있다.(leaf 노드 제외) 각 노드는 ⌈M/2⌉개의 key를 저장한다.
데이터 삽입	추가는 항상 leaf에 삽입한다. 노드가 넘치면 가운데 key를 기준으로 좌우 key들을 분리하고 다운데 key는 승진한다.
노드가 넘친다?	각 노드가 가질 수 있는 최대 M-1개의key를 초과한 경우를 뜻함
데이터 삭제	데이터의 삭제는 리프 노드에서만 이루어진다. 여기서 리프 노드가 아닌 노드에서 삭제를 시도할 경우, 가장 좌측 자식 노드로 한번 이동한 후 그 뒤로는 쭉 가장 큰 값을 지닌 노드로 내려간다. 이 후 리프노드에 도달하게 되면 해당 노드의 가장 큰 값과 삭제하려는 노드를 스왑하고 삭제한다. 이렇게 스왑하는 이유는 삭제하려는 노드의 가장 근삿값과 스왑하려는 의미를 담고있는 것 같다. 그 후 B-tree의 법칙에 위배되지 않게 노드를 정렬. https://cs.usfca.edu/~galles/visualization/BTree.html 정렬 과정은 위 시뮬레이션을 통해 이해하는게 빠르다.

 

 

알고리즘 문제풀이

1991 트리순회

import sys

N = int(sys.stdin.readline().strip())
tree = {}

for n in range(N):
    root, left, right = sys.stdin.readline().strip().split()
    tree[root] = [left, right]


def preorder(root):
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left
        preorder(tree[root][1])  # right


def inorder(root):
    if root != '.':
        inorder(tree[root][0])  # left
        print(root, end='')  # root
        inorder(tree[root][1])  # right


def postorder(root):
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')  # root


preorder('A')
print()
inorder('A')
print()
postorder('A')

처음 전위순회 중위순회 후위순회의 기준을 몰라서 결국 답지를 본 문제.

답지를 보고 나서 하노이 풀었을때 그 이상으로 허무했다.

 

5639 이진 검색 트리

import sys
sys.setrecursionlimit(20_000)
input = sys.stdin.readline


class Node:
    def __init__(self, data):
        # double linked list
        self.data = data
        self.left = None
        self.right = None


class binary_search_tree:
    def __init__(self):
        self.root = None  # 루트노드

    def __insert__(self, data):
        if self.root is None:
            self.root = Node(data)
            return
        node = self.root
        while node is not None:
            parent = node
            if node.data > data:
                node = node.left
            else:
                node = node.right
        if parent.data == data:
            return
        if parent.data > data:
            parent.left = Node(data)
        else:
            parent.right = Node(data)

    def postorder(self):
        root = self.root
        def postorder(root):

            if root is None:
                return
            if root != None:
                postorder(root.left)  # left
                postorder(root.right)  # left
                print(root.data)  # root
        postorder(root)


# 실행
BST = binary_search_tree()
while True:
    try:
        n = int(input())
        BST.__insert__(n)
    except:
        break
BST.postorder()

이진 검색트리를 그대로 재현하려니깐 생각보다 고민할거리가 많았다.

후위 순회는 앞선 트리 순회의 방법을 그대로 따가져와서 크게 어렵지 않았지만, Node 클래스 정의와 left, right 노드를 설정하는 방법이 생각보다 까다로웠다.

그리고 RecursionError 에러가 계속 발생해서 재귀의 깊이를 조금 줄여줬더니 통과됐다.

나와 같은 문제를 겪은 사람들이 많은 듯 하다.

 

오늘은 복습에 시간을 많이 써서 많이 공부를 못한것같다.