📌Tree의 정의
Tree는 이름 그대로 나무의 형태를 가지고있다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습이다.
그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮았다고 해서 트리 구조라 부른다.
데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다.
데이터를 순차적으로 나열시킨 선형구조가 아닌, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.
Tree의 구조와 특징
루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선으로 연결한다.
각 데이터를 노드(Node) 라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.
그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 **자식 노드(Child Node)이다.
자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다.
깊이 (Depth)
루트로부터 하위 계층의 특정 노드까지의 깊이 (Depth)를 표현할 수 있다.
루트 A의 depth는 0이고, B와 C의 depth는 1이다. D,E,F,G의 깊이는 2다.
레벨 (Level)
같은 깊이를 가지고 있는 노드를 묶어서 레벨(Level)로 표현한다.
depth가 0인 루트 A의 level은 1이다. depth가 1인 B와 C는 level 2이다. D, E, F, G는 레벨 3이다.
같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 한다
Level은 Depth에서 +1을 한 것이다.
높이 (Height)
리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다.
ex) H, I, E, F, J의 높이는 0이고, D와 G의 높이는 1, B와 C의 높이는 2이다. 이 때 B는 D의 height +1을, C는 G의 height +1을 높이로 가진다.
아래서 부터 올라가면서 +1 한다.
서브 트리(Sub tree)
트리 구조를 갖춘 작은 트리를 서브 트리라고 부른다.
(D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E)나 (C, F, G, J)도 서브 트리이다.
📌용어 정리
-
노드(Node) : 트리 구조를 이루는 모든 개별 데이터
-
루트(Root) : 트리 구조의 시작점이 되는 노드
-
부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
-
자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
-
리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
