[CS] Tree

트리구조는 나무를 뒤집어 놓은 모습과 유사한 구조를 가지고 있어 붙여진 이름이다. 하나의 뿌리(루트 노드)로부터 가지를 뻗어 값을 이룬 형태가 나무와 닮아 있다.
트리는 그래프의 여러 구조 중 단방향 그래프의 한 구조이다.

트리구조는 데이터가 하나 이상의 다른 데이터에 무방향으로 연결된 계층적 자료구조이다. 데이터를 순차적으로 나열시킨 선형 구조가 아닌 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다. 또한, 단방향으로 연결되어 아래로만 뻗어 나가기 때문에 사이클이 존재하지 않는다.

트리의 구조 & 특징

루트(Root)
최상위에 존재하는 데이터는 루트(Root)라고 한다. 루트부터 시작하여 여러 개의 데이터를 간선(edge)으로 연결한다.

노드(Node)
노드는 루트를 포함하여 트리 구조의 각 데이터를 노드라고 한다. 노드 간의 상하 계층으로 연결되면 이를 부모-자식 관계를 가진다. 또한, 최상위 데이터는 루트 노드라고도 한다.

부모 노드(Parent Node)
노드 A와 노드 B가 서로 연결되어 A가 상위, B가 하위에 존재한다면, A는 B의 부모 노드이다.

자식 노드(Child Node)
마찬가지로 위 예시를 들면, B는 A의 자식 노드이다.

리프 노드(Leaf Node)
리프 노드는 자식이 없는 노드이다.

깊이(Depth)
트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다. 루트 노드의 depth는 0이며, 하위 노드로 1칸씩 내려갈 때마다 1씩 증가한다.
위 그림으로 나타내면 12와 23의 depth는 1, 2, 11, 7의 depth는 2가 된다.

레벨(Level)
같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있다. depth가 0인 루트 노드는 level 1이 된다. 또한, 같은 레벨에 나란히 존재하는 노드들은 형제 노드(Sibling Node)라고 한다.

높이(Height)
리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현한다. 각 리프 노드의 height는 0이 되며, 상위 노드로 올라갈 때마다 height + 1을 가진다.

서브 트리(Sub tree)
트리 구조안에 존재하는 작은 트리 구조를 뜻한다. 위 그림 상에서 D, H, I는 루트가 A인 트리 구조안에서 작은 트리 구조를 이룬다. 이를 서브 트리라 한다.