[자료구조] 비선형 구조 - 트리(Tree)

트리(Tree)

계층적 데이터를 저장하고 관리하는 데 사용된다. 트리에는 사이클 및 루프가 존재할 수 없다. 

트리(Tree)는 노드(Node)와 간선(Edge)으로 구성되며, 각 노드는 데이터와 자식 노드에 대한 참조를 포함한다.

 

 

트리의 기본 구성 요소

• 루트 노드(Root Node): 트리의 최상위 노드. 트리는 하나의 루트 노드를 가진다.
• 부모 노드(Parent Node): 자식 노드를 포함하는 상위 노드.(위의 이미지 상 A, a와 A.b에 대한 A)
• 자식 노드(Child Node): 부모 노드로부터 연결된 하위 노드. (위의 이미지 상 A에 대한  A, a와 A.b )
• 형제 노드(Sibling Nodes): 같은 부모 노드를 공유하는 노드. (위의 이미지 상   A,a와 A.b의 관계 )
• 잎 노드(Leaf Node): 자식 노드가 없는 노드로, 트리의 끝부분에 위치. (위의 이미지 상 A,a와 A.b )
• 간선(Edge): 노드와 노드를 연결하는 선으로, 노드 간의 관계를 나타냄.

* 자손 노드!= 자식노드

- 자손 노드는 부모노드 하위에 있는 모든 노드를 말한다.

 

트리의 종류

1. 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리.
   • 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 트리.( 마지막 레벨의 노드들은 왼쪽부터 오른쪽으로 채워져 있어야 한다. 이 말은 왼쪽부터 채워져 마지막 레밸에 하나만 채워도 완전 이진트리이다. )
   • 포화 이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리.
   • 균형 이진 트리(Balanced Binary Tree): 트리의 높이가 최소화된 이진 트리.
   • 이진 탐색 트리(Binary Search Tree, BST): 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 트리.

 

 

*포화 이진 트리와  완전 이진 트리의 차이

포화 이진 트리는 항상 완전 이진 트리이지만, 완전 이진 트리는 항상 포화 이진 트리는 아닙니다.(예시 이미지는 완전 이 진 트리이지만 포화 이진트리가 아닌 것.)

1. AVL 트리(AVL Tree): 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지하는 자가 균형 이진 탐색 트리.
2. 레드-블랙 트리(Red-Black Tree): 노드가 레드 또는 블랙으로 색칠된 자가 균형 이진 탐색 트리. 특정 규칙( 루트 노드는 항상 블랙이다 등)을 통해 균형을 유지.
3. B-트리(B-Tree): 데이터베이스와 파일 시스템에서 자주 사용되는 자가 균형 트리. 각 노드가 여러 개의 자식 노드를 가질 수 있으며, 노드 내의 키가 정렬되어 있다.

 

 

 

글을 쓰려고 찾아보다 보니 트리에 대한 이해도가 높아진 거 같다.