Tree 자료구조

자료 구조 트리란?

트리는 계층 구조로 데이터를 저장하는 자료구조이며, 노드 간의 부모-자식 관계로 이루어져 있습니다.

평균적으로 탐색 시간 복잡도는 O(log N)이나, 노드가 한쪽으로 치우치면 O(N)이 될 수 있습니다.

이를 방지하기 위해 밸런스 트리가 사용됩니다.

 

💡 밸런스 트리(Balanced Tree)란?
밸런스 트리는 삽입/삭제 시 트리의 균형을 유지하도록 설계된 자료구조로, 항상 O(log N)의 탐색 성능을 보장합니다. 대표적으로 Red-Black Tree와 B-Tree가 있습니다. 다만, 삽입/삭제 시 추가적인 연산이 필요하여 일반 트리보다 성능이 약간 낮을 수 있습니다.

 

밸런스 트리는 최악의 경우에도 O(logN)이므로, 탐색시간에 매우 효율적인 자료구조입니다.

 

Binary Tree, RB Tree, B tree, B+ tree

 

BST(Binary Search Tree)와 Binary Tree

이진트리(Binary Tree) 는 자식 노드가 최대 두 개인 노드들로 구성된 트리이고,

이진 탐색 트리(BST) 는 이진 탐색과 연결리스트를 결합한 자료구조입니다.

 

Binary Search Tree

 

• 왼쪽 서브트리의 모든 값은 부모보다 작고, 오른쪽은 부모보다 큽니다.
• 삽입/삭제가 빈번한 경우 트리가 편향되어 성능이 O(N)으로 저하될 수 있습니다.

 

Red-Black Tree

 

• BST에 색상 정보를 추가하여 균형을 유지합니다.
• 삽입/삭제 시 색상 변경과 회전을 통해 O(log N)의 탐색 성능을 보장합니다.
• 활용 사례: Java의 TreeMap, TreeSet.

 

---

 

색상은 Red 와 Black 으로 나뉘어져 있고, 각 노드는 Red 혹은 Black 색상을 가지게 된다.

트리가 변경될 때마다, 새로운 트리는 재 나열되고, 다시 색깔이 설정되어 색깔 특성을 회복하고 이것은 unbalanced 트리가 worst - case 가 되는 것을 막습니다.

재 균형은 완벽하지 않지만 O(log n) 의 검색 시간을 보장합니다. 노드 삽입과 삭제 시에도 재 나열과 repaint 를 포함해 O(log n)  안에 수행합니다.

 

 

 

 

활용

• Java의 TreeMap, TreeSet, 데이터베이스 인덱스.

 

 

 

B-tree 

 "데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. " by wiki 

 

• 다중 자식 노드를 가질 수 있는 자기 균형 트리 구조.
• BST를 확장하여 노드가 가질 수 있는 자식 수를 2개 이상으로 일반화한 트리.

 

 

B 트리는 자식을 두개만 가질 수 있는 이진 트리를 확장하여 더 많은 수의 자식을 가질 수 있게 일반화하였다. 같은 수의 자료라 할지라도 하나의 레벨에 더 많이 저장되므로 전체적으로 트리의 높이가 낮아진다.

 

B 트리는 자식 수에 대한 일반화를 하면서 트리의 균형을 자동으로 맞추는 로직까지 갖추고 있다. B 트리는 레벨로만 따지면 완전히 균형을 맞춘 트리이다.

 

하나의 노드에 많은 데이터를 가질 수 있다는 점은 대량의 데이터를 처리해야 하는 검색 구조인 경우 큰 장점으로 다가온다.대량의 데이터는 메모리보다 하드디스크, SSD 에 저장되어야 하는데, 이들 외부기억장치들은 블럭 단위로 입출력을 하기 때문입니다.

 

 

 

B+tree 

 B+tree는 B-tree의 확장개념으로, b-tree와 달리 모든 노드에 key, data가 있지 않으며, leaf 노드에만 key, data가 있다. 그리고 B-트리와 달리 삽입, 삭제 연산이 leaf  노드에서만 이루어지며 leaf  노드끼리 연결리스트로 연결되어 있다. 

 leaf  노드가 순차집합 연결되어 있기 때문에 순차적인 탐색에 유리하다.

​

B트리는 BST의 높이를 줄이기 위해 등장한 m원 탐색트리의 좌우 균형을 맞추기 위하여 등장하였고 B+트리는 순차 검색이 힘들다는 B트리를 보완하기 위해 등장하였다. 직접 탐색의 경우 B트리와 B+트리나 성능이 비슷하지만 순차 탐색의 경우 B+트리의 성능이 뛰어나다.

 

 

• Binary Tree와 Binary Search Tree의 차이점은 무엇인가요?
  • 답변: Binary Tree는 각 노드가 최대 두 자식을 가지는 트리이고, Binary Search Tree는 추가로 왼쪽 자식 < 부모 < 오른쪽 자식 조건을 만족합니다.
• Red-Black Tree의 특징은 무엇인가요?
  • 답변: 레드-블랙 트리는 삽입/삭제 시에도 트리의 높이를 O(log n)으로 유지하기 위해 색상과 회전을 사용합니다. 균형을 유지하는 규칙으로는 루트 노드는 검정색, 빨간색 노드의 자식은 검정색 등이 있습니다.
• B-Tree와 B+ Tree의 차이점은 무엇인가요?
  • 답변: B-Tree는 모든 노드에 데이터를 저장하지만, B+ Tree는 리프 노드에만 데이터를 저장하고 리프 노드가 연결 리스트로 연결되어 있어 범위 검색이 더 효율적입니다.
• B+ Tree는 왜 데이터베이스 인덱스에 적합한가요?
  • 답변: B+ Tree는 리프 노드끼리 연결되어 있어 범위 검색과 순차 접근이 효율적입니다. 또한, 한 노드에 여러 키를 저장해 디스크 I/O를 줄여 데이터베이스 성능을 향상시킵니다.

 

B-Tree와 B+ Tree는 균형 트리 자료구조로, 데이터베이스나 파일 시스템에서 대용량 데이터를 효율적으로 관리하기 위해 사용됩니다. 두 트리는 비슷한 구조를 가지고 있지만, 몇 가지 차이점이 있습니다.

---

B-Tree:

1. 구조:
   • M-항 트리로, 각 노드가 최대 M개의 자식 노드를 가질 수 있습니다.
   • 노드에는 키 값과 데이터가 함께 저장됩니다.
2. 특징:
   • 모든 노드는 최소 ⌈M/2⌉개의 자식을 가지며, 루트 노드는 예외적으로 2개 미만의 자식을 가질 수 있습니다.
   • 키 값이 정렬된 상태로 저장되어 있어 빠른 탐색이 가능합니다.
   • 삽입/삭제 시 트리의 균형을 유지하므로, 높이는 **O(log n)**을 보장합니다.
   • 데이터가 루트부터 리프 노드까지 분산 저장됩니다.
3. 활용:
   • 데이터베이스에서 인덱스를 구현하거나 파일 시스템의 블록 관리를 위해 사용됩니다.

---

B+ Tree:

1. 구조:
   • B-Tree에서 확장된 형태로, 모든 데이터를 리프 노드에 저장합니다.
   • 중간 노드는 데이터를 저장하지 않고 인덱스 역할만 수행합니다.
   • 리프 노드끼리 연결 리스트로 연결되어 있습니다.
2. 특징:
   • 리프 노드에 데이터가 저장되므로, 중간 노드는 메모리를 더 효율적으로 사용하며 범위 검색에 유리합니다.
   • 리프 노드가 연결 리스트로 연결되어 있어 순차 접근이 빠릅니다.
   • 범위 검색이나 정렬된 데이터를 조회할 때 성능이 더 우수합니다.
3. 활용:
   • 데이터베이스 인덱스와 트랜잭션 시스템에서 범위 검색이나 대량의 정렬 데이터를 효율적으로 관리할 때 사용됩니다.

B-Tree와 B+ Tree의 차이점:

특성B-TreeB+ Tree

데이터 저장 위치	모든 노드에 데이터 저장	리프 노드에만 데이터 저장
중간 노드 역할	데이터와 인덱스를 함께 저장	인덱스 역할만 수행
리프 노드 연결	연결 리스트가 없음	연결 리스트로 리프 노드가 연결됨
범위 검색 성능	효율적이지 않음	매우 효율적
메모리 효율성	중간 노드에 데이터가 있어 메모리 낭비	중간 노드에 인덱스만 있어 더 효율적

---

결론:

• B-Tree는 데이터와 인덱스를 함께 저장하며, 삽입/삭제와 같은 작업에서 균형 유지가 용이합니다.
• B+ Tree는 모든 데이터를 리프 노드에 저장하고, 중간 노드는 인덱스 역할만 하므로 범위 검색이나 순차 접근이 필요한 경우 더 적합합니다.

 

참고자료: https://dev-coco.tistory.com/159 [슬기로운 개발생활:티스토리]

https://seunggi92.tistory.com/39