[자료구조] 트리(Tree) 관련 용어 간단 정리

 

 

트리는 스택, 큐, 배열, 리스트와는 다르게 계층적 구조를 가져 굉장히 중요한 자료구조이다. 트리를 공부하며 느낀 것은 트리라는 개념도 어렵지만 트리를 설명하는데 나오는 여러 새로운 용어들이 발목을 많이 잡는 것 같다. 여기서는 트리 관련하여 나오는 주요 용어를 정리하고자 한다.

 

노드(Node) , 키(Key)

 

트리를 구성하는  하나의 요소를 노드라고 부르며 하나의 노드가 저장하는 값을 키라고 한다.

하나의 노드는 키와 자손을 가리키는 참조 변수(left, right)를 갖는다.

 

 

루트 노드(Root Node), 서브 트리(Subtree)

가장 낮은 높이에 존재하는 노드를 루트 노드(Root Node)라고 부른다. 트리의 접근은 언제라 루트 노드를 시작으로 접근할 수 있다.

 

해당 노드의 왼쪽 혹은 오른쪽에 있는 노드들을 묶으면 또 하나의 트리 형태가 되는데 이를 서브 트리(Subtree)라고 한다. 이진 탐색 트리의 경우 왼쪽 서브트리의 노드들은 모두 부모 노드보다 값이 작으며, 오른쪽 서브트리의 노드들은 부모 노드보다 모두 값이 크다.

 

트리의 높이 , 노드의 레벨

노드의 레벨은 루트 노드가 레벨 0에서 시작하여 자식 노드로 내려갈 수록 레벨이 1씩 증가한다.

경우에 따라 루트 노드의 레벨을 1로 보는 경우도 있으며 단지 초기 레벨 설정의 차이임으로 개념은 동일하다.

 

트리의 높이는 레벨이 가장 높은 노드의 레벨이다. 해당 그림의 경우 오른쪽 서브트리의 단말 노드(Leaf node) I , J, K, L의 레벨이 3이기에 트리의 높이는 3이 된다.

 

 

부모 노드, 형제 노드, 조상 노드

 

해당 노드를 기준으로 바로 위의 레벨에 있는 노드를 부모 노드

해당 노드를 기준으로 같은 레벨에 있는 노드를 형제 노드

해당 노드를 기준으로 바로 아래 레벨에 있는 노드를 자식 노드

해당 노드를 기준으로 바로 위는 아니지만 위에 있는 노드를 조상 노드

해당 노드를 기준으로 바로 아래는 아니지만 아래 레벨에 있는 노드를 후손 노드

 

단말 노드(Leaf node), 내부 노드(Internal node)

자손을 가지지 않는 노드를 단말 노드 혹은 Leaf 노드라고 한다.

이외에 자손을 가지는 노드를 내부 노드라고 한다.

 

내부 노드보다는 단말 노드(Leaf node)의 개념이 자주 사용된다.

 

 

---

이미지 출처

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼