Tree 자료구조 종류

 

1.이진 트리 (Binary Tree)
모든 노드가 최대 2개의 서브 트리를 가지는 트리입니다.
가장 많이 사용되며, 서브 트리도 모두 이진 트리여야 합니다.
이진 트리의 서브 트리는 공집합일 수 있습니다.
예시: 이진 탐색 트리 (Binary Search Tree)  등

2. 포화 이진 트리 (Full Binary Tree)
각 레벨에 노드가 꽉 차 있는 이진 트리입니다.
노드에 레벨 단위로 번호를 붙일 수 있으며, 번호는 항상 일정합니다.

3. 완전 이진 트리 (Complete Binary Tree)
높이가 k일 때, 레벨 1부터 k-1까지는 노드가 채워져 있고, 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워진 이진 트리입니다.
마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만, 중간에 빈 곳이 있으면 안 됩니다.

예시 : java Heap(힙)

4. B-트리 (B-Tree)
데이터베이스와 파일 시스템에서 사용되는 트리 구조입니다.
다양한 차수를 가지며, 데이터를 효율적으로 저장하고 검색하는 데 사용됩니다.

B-Tree는 자식 2개 만을 갖는 이진 트리(Binary Tree)를 확장하여 N개의 자식을 가질 수 있도록 고안된 것입니다. 그리고 좌우 자식 간의 균형이 맞지 않을 경우에는 매우 비효율적이라, 항상 균형을 맞춘다는 의미에서 균형 트리(Balanced Tree)라고 불립니다.

B-Tree는 최상위에 단 하나의 노드 만이 존재하는데, 이를 루트 노드(Root Node)라고 합니다. 그리고 중간 노드를 브랜치 노드(Branch Node), 최하위 노드를 리프 노드(Leaf Node)라고 합니다.

5. B+ 트리 (B+ Tree)
B-트리의 변형으로, 데이터베이스 인덱스에서 주로 사용됩니다.
리프 노드에만 데이터가 저장되며, 리프 노드는 연결 리스트로 연결되어 있습니다.