트리

트리

트리는 순환이 발생하지 않는 그래프 자료구조이다. 이 특징으로 인해 한 노드를 특정하여 루트노드로 정하게 되면, 각 노드들은 한개의 부모노드와 여러 자식노드를 가질수 있어 데이터를 계층적으로 구조화 할수 있다.

트리에서 사용되는 용어

• 루트노드: 트리의 최상단에 위치한 노드
• 리프노드: 자식노드가 없는 최하단의 노드
• 서브트리: 어떤 노드와 그 노드의 모든 자손 노드로 이루어진 트리를 해당 노드의 서브 트리
• 레벨: 노드의 깊이를 나타내는 개념이다. 아래로 내려갈수록 레벨이 증가한다.

이진트리

최대의 자식노드가 2개인 트리

이진트리의 타입

• 완전 이진트리: 마지막레벨을 제외하고 모든레벨이 다 채워진 이진트리

    1
   / \
  2   3
   / \
  4   5
  

• 정 이진트리: 모든 노드가 정확히 0개 또는 2개의 자식을 가지는 이진 트리

      1
     / \
    2   3
   / \
  4   5
   / \
  6   7
  

• 포화 이진트리: 모든 레벨이 완전히 채워진 이진트리

     1
   /   \
  2     3
   / \   / \
  4   5 6   7
  

이진탐색트리

왼쪽서브트리의 모든노드의값은 부모노드보다 우선순위가 낮고 오른쪽 서브트리의 노드들이 부모노드들 보다 우선순위가 높은 이진트리.

이진탐색트리의 탐색, 삽입, 삭제 시간은 트리의 최대 레벨에 비례하는 경향이 있다. 따라서 최악의 트리에서는 O(n), 평균시간복잡도는 O(logn)이 된다.

이진탐색트리는 데이터가 물리적으로 정렬되있지 않아도 된다. 따라서 순차탐색이 아닌 랜덤탐색에 의한 하드디스크 기반의 보조 저장장치에서 속도저하 가능성이 있다.

힙

부모노드가 자식보다 항상 높은 우선순위를 가지는 완전 이진탐색트리. 우선순위큐의 구현에 활용된다. 힙의 최댓값 최솟값 검색, 삽입, 삭제시간은 트리의 최대레벨에 비례한다. 하지만 힙은 완전이진트리이므로 최악 시간복잡도, 평균 시간복잡도 모두 O(logn)이 된다.

AVL 트리

서브트리의 최대 레벨차이가 1이하를 유지하도록 스스로 균형을 잡는 이진트리. 서브트리간의 레벨차이가 발생하면 루트노드를 하위노드로 강등시켜 균형을 잡는다.

AVL트리도 이진트리 특성상 노드의 갯수가 2개때문에 균형은 유지하지만 트리의 높이가 높아지는 문제점이 있으며 노드 추가 삭제시 밸런스 체크, 리밸런싱 부하가 있다.

페이지화된 이진트리

이진트리를 메모리상의 페이지단위로 분리한다. 이를 통해 같은 페이지안의 노드들에 대해선 순차탐색이 가능하도록 한다. 사전에 모든 데이터를 가지고 있을때 유리하다. 데이터가 추가, 삭제 되는순간 트리의 균형이 깨지기 쉽다.

b-tree

AVL 트리와 페이지화된 이진트리의 단점을 보완하는 트리 자료구조이다. 항상 균형이 잡혀 있는 다차원 트리이다. 대용량 데이터베이스 및 파일 시스템에서 데이터를 저장하고 검색할때 사용되는 자료구조이다.

• 각각의 B트리 노드는 키와 데이터에 대한 참조의 조합들로 이루어진 인덱스 레코드 하나이자 메모리상의 하나의페이지이다. 따라서 삽입 삭제가 일어나더라도 페이지의 공간이 충분하면 리밸런싱 오버헤드를 막을수 있다.

• 삽입 및 삭제 연산의 재배치: B-트리는 삽입과 삭제 연산 시에 노드의 재배치를 통해 균형을 유지하며 데이터를 조작한다. 이러한 재배치 과정은 B-트리의 특성을 지키면서도 데이터를 효율적으로 관리할 수 있도록 한다.

• B-트리는 다단계 인덱싱과 궁합이 잘맞아 대용량 데이터를 효과적으로 관리할 수 있다. 인덱스 레벨마다 노드 래퍼런스가 포함되어 있어 데이터를 빠르게 찾을 수 있다.

• 노드의 다양한 자식 수: B-트리의 각 노드는 여러 개의 자식을 가질 수 있다. 일반적으로 B-트리에서 각 노드는 M개 이상, 2M개 이하의 자식을 가진다. M은 B-트리의 최소 차수라고도 불린다.