안녕하세요.

오늘은 B 트리 에 대해 포스팅 합니다.

B 트리이진 탐색 트리의 일종으로 탐색 성능을 높이기 위해 균형있게 높이를 유지하는 균형 트리 입니다.

균형 이진 탐색 트리는 대표적으로 RedBlackTree, AVL 트리 같은것이 있습니다. 두 트리가 독특한 규칙으로 높이를 유지 하는것처럼 B 트리도 자신만의 규칙이 존재합니다.

특이한점은, 이진 트리가 아니라는 점 입니다. 규칙에 따라 노드의 자식 노드 개수는 2개 이상이 될 수 도 있습니다.

B 트리 장점

B 트리의 장점은 크게 3가지가 존재합니다.

  • 균형 트리
  • 데이터 로드 효율성

균형 트리의 장점은 이진 탐색 트리 에서도 살펴봤다시피, 노드들이 한쪽으로 치우쳐 연결 리스트의 형태가 되는것을 방지하여 검색 효율을 높일 수 있다는 장점이 있습니다.

데이터 로드 효율성 측면은 대량의 데이터로 트리를 구성할 때, 진가를 발휘합니다.

데이터가 많은경우 메모리에 트리 구조를 유지하기 보다는 외부장치에 데이터를 저장해야 합니다. 각 노드의 값을 파일로 저장한 후, 파일 정보만 저장하고 있다면 메모리에서도 충분히 트리를 유지할 수 있게 됩니다.

외부장치에서 데이터를 읽어올때 데이터가 크던 작던 블럭 크기 만큼 읽어옵니다. 즉 노드의 데이터를 특정 블럭 크기 만큼 지정하여 저장 할 수 있다면 효율적으로 데이터를 읽어올 수 있다는 장점이 생깁니다.


B 트리 구성 방법

B 트리 만의 독특한 구성 규칙이 존재합니다. 이해를 위해서 모든 규칙은 맨 마지막에 정리하고, 중요한 조건순으로 차근차근 알아가봅시다.

N차 B 트리

B 트리를 구성할 때, 가장 중요한 조건은 노드가 최대 몇개의 데이터를 가질 수 있느냐 입니다.

만약 최대 3개의 자료를 가질 수 있다고 정의하면, 노드 자식 개수는 최대 4개를 가질 수 있습니다. 이때 최대 자식 개수를 사용하여 4차 B 트리 라고 표현 합니다.

즉 일반화 해본다면, 하나의 노드가 최대 M개의 자료를 가질 수 있다면 최대 자식 노드 개수는 M+1이 되므로 M+1차 B 트리 입니다.

왜 최대 자식 노드 개수가 M+1 이냐구요? 아래 B 트리 삽입 에서 살펴봅시다!

N차 B 트리는 노드의 최대 자료수는 N-1 이며, 최대 N개의 자식노드를 가질 수 있습니다.


B 트리 탐색

B 트리 탐색은 탐색 노드와 특징을 이용합니다.

특정 노드의 범위 위치를 찾은 후 아래의 자식 노드로 이동합니다.

아래의 과정은 0016 값을 찾는 과정입니다.

  • 루트 노드에서 0016 값의 범위 위치를 찾습니다. (0015 < 0016)
  • 다음 노드에 0016 값이 존재하는지 찾아봅니다. 존재하지 않으므로 0016 값의 범위 위치를 찾습니다. (0016 < 0017)
  • 다음 노드는 리프노드 이므로 해당 노드에 값이 존재하지 않는다면 트리에 값이 존재하지 않음을 알 수 있습니다. 0016 값이 있으므로 탐색을 종료합니다.


B 트리 삽입

B 트리의 차수를 정할 때 홀수냐 짝수냐에 따라 알고리즘이 조금 다릅니다. 홀수가 조금 더 계산하기 편하므로 홀수로 설명하겠습니다.

3차 B 트리 를 예시로 들어봅시다. (노드의 최대 자료 개수는 2개)

삽입의 핵심은 노드 분열 작업 입니다.

아래의 삽입 과정은 최초 노드 분열이 발생하는 과정입니다.

  • 01~02 번 삽입 과정은 루트 노드에 빈자리가 존재하여 자리를 찾아 삽입 합니다.
    • 데이터 저장 순서는 오름 차순으로 저장합니다.
  • 03번은 0011 을 루트 노드에 넣을 자리가 없는 경우 입니다.
    • 이때 B 트리 핵심 과정 중 하나인 노드 분열이 발생합니다.
    • 03-2. 루트 노드의 값들과 넣을 값을 포함하여 중간 값을 찾습니다. (홀수 차수를 고른것이 이때 편합니다.)
    • 03-3. 중간 값 0005 값을 부모 노드로 올리고, 왼쪽 값들과 오른쪽 값들을 자식 노드로 각각 구성하여 연결합니다.

아래의 과정에서 발생하는 노드 분열도 한번 살펴보시죠.

  • 04번 삽입은 탐색 노드 특징을 이용하여 리프노드 까지 도달합니다.
    • 리프노드에 자리가 비었으므로, 0017값이 그대로 저장됩니다.
  • 05-01. 0022 값의 자리를 탐색하여 리프 노드 까지 도달했습니다.
    • 05-01. 하지만, 리프 노드엔 자리가 없습니다. 노드 분열과 마찬 가지로 중간 값을 찾습니다.
    • 05-02. 중간 값을 부모 노드로 이동시킵니다. (노드 분열이 발생합니다.)
    • 05-02. 남은 값들은 각각 노드로 구성하여 중간 값 왼쪽, 오른쪽 자식노드로 연결합니다.

위 예시와 같이 리프노드에 공간이 부족할 때, 부모 노드로 중간 값을 옮기는 노드 분열를 수행하면 재밌는 특징이 생깁니다.

  • 규칙1. 노드의 자료가 최대 N개 라면, 해당 노드의 자식 노드 개수는 항상 N+1 입니다.
  • 규칙2. 모든 리프 노드들은 항상 같은 레벨에 위치하게 됩니다.
  • 규칙3. 노드의 자료가 최대 N개 라면, 리프 노드가 분열 할때 항상 중간 값으로 분열 하므로 노드의 자료 개수는 [N/2]~N개가 보장 됩니다.
    [3/2] ⇒ 2 (올림연산 입니다.)

마지막으로 아래의 노드 분열을 이해 하실 수 있다면, 트리 삽입 과정을 이해 하실 수 있습니다.


B 트리 삭제

B 트리의 삭제는 크게 두가지 케이스로 나누어 생각 해볼 수 있습니다.

  • 리프 노드에서 값 삭제.
  • 리프 노드가 아닌 중간 노드에서 값 삭제.

리프 노드에서 삭제

이 경우에도 크게 3가지 경우로 나뉩니다.

  • 리프 노드에서 값을 삭제 하더라도 최소 유지 개수 ([N/2]) 조건에 만족하는 경우.
  • 리프 노드에서 값을 삭제 할 때, 최소 유지 개수를 만족하지 못하지만 바로 옆 형제 노드들 중 최소 유지 개수 보다 많아 값을 빌려올 수 있는 경우.
  • 리프 노드에서 값을 삭제 할 때, 최소 유지 개수를 만족하지 못하고 옆 형제 노드들도 최소 유지 개수만 가지고 있어 값을 빌려올 수 없는 경우.

리프 노드에서 바로 삭제.

리프 노드가 최소 유지 개수를 만족하는 경우 바로 삭제가 가능합니다.

형제 노드에서 값을 빌려 오는 경우.

  1. 리프 노드형제 노드에서 빌려야 할 값을 찾습니다.
    • 오른쪽 형제 노드라면 형제 노드중 최대값.
    • 왼쪽 형제 노드라면 형제 노드중 최소 값.
  1. 리프 노드부모 노드에서 리프 노드형제 노드를 동시에 가리키고 있는 값을 찾습니다.
  1. 리프 노드에서 값을 삭제 후, 부모 노드에서 찾은 값을 리프노드로 내려주고 빌린 형제 노드 값을 부모 노드 찾은 값 자리에 넣습니다.

형제 노드에서도 값을 빌릴 수 없는 경우.

  1. 삭제할 리프 노드형제 노드를 병합 합니다. 병합 노드최소 개수 조건을 만족 시키기 위해 부모 노드에서 값 하나를 내려줍니다.
  1. 부모 노드도 최소 개수 조건을 만족하지 않는다면, 1번 과정을 리프 노드 대신 부모 노드로 치환하여 수행합니다.
  1. 만약 병합된 노드가 최대 개수를 넘는다면, 중간 값을 찾아 병합 노드의 부모 노드로 값을 넘겨줍니다.

중간 노드에서 삭제

해당 경우도 3가지로 나눌 수 있습니다.

  • 최소 개수 보다 많아 값을 빌려올 수 있는 자식 노드가 존재하는 경우.
  • 여유있는 자식 노드가 없지만, 부모 노드가 최소 개수보다 많은 경우.
  • 자식 노드도, 부모 노드도 여유가 없는 경우.

자식 노드에게 값을 빌려오는 경우.

  1. 값을 빌려올 자식 노드의 값을 찾습니다.
    • 왼쪽 자식 노드라면 최소 값을 찾습니다.
    • 오른쪽 자식 노드라면 최대 값을 찾습니다.
  1. 타겟 노드의 값을 지우고, 해당 자리를 찾은 자식 노드의 값으로 대체 합니다.

여유있는 자식 노드는 없지만, 부모 노드가 여유가 있는 경우.

  1. 노드의 삭제 값의 자식 노드들을 합병합니다.

자식노드, 부모노드 둘다 여유가 없는 경우.

  1. 노드의 삭제 값의 자식 노드들을 병합합니다.
  1. 노드의 형제 노드부모노드를 대상으로 병합을 진행합니다.
  1. 만약 병합 노드가 최대 개수를 초과 한다면 중간 값을 추출해 병합 노드부모노드로 이동시킵니다.


B+트리

B 트리의 단점은 순회?

Warning!! 주관적인 생각이 섞여 있습니다.

B 트리 는 자료 순회가 단점이라는 글이 많습니다. B 트리도 트리 구조이기 때문에 트리 순회와 똑같은 시간복잡도가 걸립니다. 그렇기에 단점이라 할 수는 없습니다.

많은 자료들이 단점이라 오해(?)하는 이유는 트리 순회를 개선한 B+트리의 존재 유무 때문이 아닐까 생각이 듭니다.

리프 노드들을 모든 노드의 값이 포함되도록 처리

B+ 트리의 순회 연산의 개선 포인트는 리프 노드들의 구조에 있습니다.

다음의 예시를 보면, 리프 노드들은 모든 값들을 포함하고 있고 연결리스트 형태를 구성하고 있습니다.

리프 노드의 위 노드들은 검색을 위해 유지하고 있는 모습입니다.

특정 범위를 순회하고 싶다면, 손쉽게 특정 리프 노드에서 차례대로 순회 할 수 있습니다.

빠른 검색-삽입-삭제 + 범위 검색 이 필요한 관계형 데이터베이스가 해당 자료구조를 사용하고 있습니다.


B 트리의 삽입, 삭제 과정을 단번에 이해하긴 어려운거 같습니다.

더군다나 트리의 특정 스냅샷 기준으로 설명했기 때문에 높이가 큰 트리인 경우에는 설명한 개념에 더해 재귀 개념 까지 합산하여 이해를 해야 하기 때문에 더 어려운거 같습니다.

B 트리 특징들을 살펴보면서 항상 만족했던 조건들을 다시 정리해보면 아래와 같습니다.

  • N차 B 트리는 노드의 최대 자료수는 N-1 이며, 자식노드는 최대 N개.
  • 노드의 자료가 최대 N개 라면, 해당 노드의 자식 노드 개수는 항상 N+1.
  • 노드의 자료가 최대 N개 라면, 노드의 자료 개수는 [N/2] ~ N개. (루트 노드 제외)
  • 모든 리프 노드들은 항상 같은 레벨에 위치한다.

오늘 준비한 포스팅은 여기까지 입니다.

읽어주셔서 감사합니다.

'자료구조' 카테고리의 다른 글

[자료구조] 이진탐색트리  (1) 2021.07.12
[자료구조] 트리(Tree)  (0) 2021.07.10

포스팅이 도움 되셨다면, 커피 한잔 후원해주세요!
더 좋은 포스팅 작성에 큰 힘이 됩니다.

Buy me a coffeeBuy me a coffee
Tree 란

안녕하세요.

오늘은 자료구조 트리(Tree)에 대해 포스팅 합니다.

필수적으로 알아야 할것들만 정리하였습니다.

트리구조에 대해 대략적으로 설명하므로, 특정 용어나 개념들은 따로 찾아봐야 합니다.

 

트리(Tree) 란

위 본문의 그림과 같이 노드간선으로 이루어진 것을 그래프(Graph) 라고 합니다.

트리는 이러한 그래프 의 일종 입니다. 아래의 규칙을 따르는 그래프트리라고 일컫습니다.

사실 규칙을 외울 필요는 없고, 이런 형태구나 정도로 기억하면 될 거 같습니다.

 

트리 규칙

  • 특정 노드는 오직 하나의 조상 노드와 N 개의 자식 노드와 연결됩니다.

    • 특정노드에서 조상노드, 자식노드는 레벨의 차이가 반드시 1이어야 합니다.
    • C 노드는 하나의 조상 노드인 A와 2개의 자식 노드인 G , H와 연결됩니다.
  • 여러 노드가 한 노드를 가리킬 수 없습니다.
  • 노드와 노드를 잇는 길(간선)이 하나만 존재합니다.

 

또한 트리는 다음과 같은 특징들을 가집니다.

높이

트리는 루트로 부터 레벨 을 셀 수가 있는데 이때 최대 레벨의 값을 높이라 부를 수 있습니다.

따라서, 예제의 트리의 높이는 3입니다.

 

말단 노드(리프 노드)

자식이 없는 노드를 말단 노드 또는 리프 노드라 일컫습니다.

 

형제 노드

같은 부모를 가지는 노드들을 형제(sibling)노드라 부릅니다.

 

서브 트리

트리안에서 특정 범위를 묶어 하나의 작은 트리를 구성 할 수 있습니다.

예제 트리의 빨간 박스, 파란 박스 와 같은 예시처럼 묶을 수 있으며 이를 서브 트리라 일컫습니다.

 

이진트리 (Binary Tree) 란

트리의 특정 노드는 자식의 개수를 제한 없이 가질 수 있는데요.

이때, 최대 2개의 자식 노드만 가질 수 있다 는 조건을 추가한것을 이진트리라고 부릅니다.

쉽게 말해, 노드가 왼쪽 자식오른쪽 자식을 갖는 특징을 가집니다.

예제의 트리도 이진트리라 부를 수 있습니다.

 

이진트리구조를 갖추면, 해당 구조가 제공하는 연산의 이점들이 존재합니다.

예를들면, 노드의 개수를 알면 높이를 알 수 있습니다.

레벨(N)당 노드의 개수는 2^N 이기 때문입니다.

 

대표적으로 사용되는 연산은 탐색입니다.

너무나도 유명한 이진 탐색 트리 를 구성할 수 있습니다.

 

특정 조건이 추가된 이진 트리들이 있습니다.

완전 이진트리

  • 모든 레벨에서의 노드가 꽉차 있어야 합니다.

  • 예외적으로, 마지막 레벨에서의 노드는 꽉차 있지 않아도 되지만 왼쪽에서 차례대로 채워져야만 합니다.

  • 예시 트리도 완전 이진트리 입니다.

  • 예시 트리에서 N 만 없애거나, (M, N) 을 없애거나, (L, M, N)을 없앤 케이스도 완전 이진트리입니다.

전 이진트리

  • 특정 노드의 자식이 0개 또는 2개로만 구성되어 있는 트리를 의미합니다.
  • 예시 트리에서 (G, H)를 없애거나, (E, F, K, L, M, N)을 없앤 케이스를 전 이진트리로 볼 수 있습니다.

 

포화 이진트리

  • 모든 말단 노드가 같은 높이에 있어야 합니다.

    • 예를들어, (E, F, K, L, M, N)을 없앤 케이스를 전 이진트리형태는 말단 노드인 B가 다른 말단 노드인 G와 레벨이 동일하지 않습니다.
  • 마지막 레벨에서 노드의 개수가 최대가 되어야 합니다.

  • 예시 트리도 포화 이진트리라 부를 수 있습니다.

 

이진 탐색트리

  • 노드의 자식은 아래의 규칙을 따릅니다.

    • 오른쪽 노드의 값 < 현재 노드의 값 < 왼쪽노드의 값
  • 값을 이용한 규칙을 통해 구조를 쌓으면 추후 이진 탐색을 사용할 수 있습니다.

다음 포스팅에서 자세히 다룰 예정입니다.

 

이진트리 순회

이진트리를 연산하기 위해서는 순회는 빼놓을 수 없습니다. 방문하지 않으면 값을 알 수 없기 때문입니다.

순회는 많이 알려진 방법인 너비우선탐색(BFS), 깊이우선탐색(DFS) 으로 나눌 수 있습니다.

 

너비우선탐색(BFS)

레벨순으로 차례대로 탐색합니다.

예시 트리를 기준으로 설명드리자면, 아래와 같이 탐색합니다.

Root > A > B > C > D > E > F > G > H > I > J > K > L > M > N

 

깊이우선탐색(DFS)

탐색 방법 3가지가 존재합니다.

기본적으로 왼쪽 자식 노드에서 오른쪽 자식 노드로 순회를 한다고 가정(B -> C)하고 현재 노드(A)가 방문되는 순서를 기억하면 좋습니다.

  • 전위 순회 (pre-order traversal)

    • 현재 노드(A)가 첫번째로 방문 됩니다.
    • B ->C는 고정이므로 첫번째로 방문되려면 맨 앞에 배치 되어야 합니다.
    • A -> B -> C
  • 중위 순회 (in-order traversal)

    • 현재 노드(A)가 중간에 방문 됩니다.
    • B -> A -> C
  • 후위 순회 (post-order traversal)

    • 현재 노드(A)가 마지막에 방문 됩니다.
    • B -> C -> A

 

위 예시는 서브 트리가 존재하지 않는 트리인 경우 입니다.

만약 서브 트리가 존재한다면 어떻게 방문할까요?

이때는 서브 트리를 하나의 노드라 생각하고 방문합니다.

다음의 트리를 이용하여 전위 순회로 알아봅시다.

 

해당 예시의 서브 트리는 (B, D, E) 입니다.

STEP1: 서브 트리를 하나의 노드(BB)로 치환하여 전위 순회를 진행합니다.(A -> BB -> C)

STEP2: BB도 트리이므로 내부적으로 순회를 똑같이 진행합니다. (B -> D -> E)

STEP3: 서브 트리 순회 결과를 치환한 노드BB에 반영합니다. (A -> B -> D -> E -> C)

 

최초 분문의 예시를 각 방법으로 순회 하면 다음과 같습니다. (ROOT의 위치를 살펴보세요.)

전위 순회 : ROOT > A > C > G > H > D > I > J > B > E > K > L > F > M > N

중위 순회 : G > C > H > A > I > D > J > ROOT > K > E > L > B > M > F > N

후위 순회 : G > H > C > I > J > D > A > K > L > E > M > N > F > B > ROOT

 

오늘 준비한 내용은 여기까지 입니다.

읽어주셔서 감사합니다.

'자료구조' 카테고리의 다른 글

[자료구조] B 트리  (0) 2021.07.29
[자료구조] 이진탐색트리  (1) 2021.07.12

포스팅이 도움 되셨다면, 커피 한잔 후원해주세요!
더 좋은 포스팅 작성에 큰 힘이 됩니다.

Buy me a coffeeBuy me a coffee

+ Recent posts