7.1 트리의 용어 [디딤돌 자료구조와 알고리즘 with C++]

7.1 트리의 용어

트리에는 부모가 없는 노드가 없거나 유일합니다. 그리고 이를 루트라고 말합니다.

 

그리고 트리에서 자료를 보관하는 것을 정점(Vertex) 혹은 노드(Node)라고 부르며 정점에서 다른 정점으로 가는 경로를 간선(Edge) 혹은 링크(Link, 다른 노드의 위치 정보)라고 부릅니다.

 

언제나 트리의 정점은 간선 개수보다 1개 많습니다.

N(V) = N(E)+1 , N(V)는 정점의 개수, N(E)는 간선의 개수

 

루트에서 자신에게 걸리는 거리를 레벨(Level)이라 부르고 루트를 Level 1로 출발합니다. 그리고 가장 높은 레벨(Level)을 트리의 높이(Height) 혹은 깊이(Depth)라고 부릅니다.

 

간선은 링크 혹은 가지라고도 부르며 Level N인 노드로 가기 위한 Level N-1에 있는 노드를 부모(Parent)라고 부릅니다. 그리고 Level N인 노드와 연결 상태인 Level N+1에 있는 노드들을 자식(Son)이라 부릅니다. 같은 부모를 갖는 노드는 서로 형제(Sibling)라고 부릅니다. 자신에게 오기 위한 경로에 있는 모든 노드를 조상(Ancestors)라고 부르며 자신을 출발로 갈 수 있는 모든 노드를 후손(descendant)이라고 부릅니다.

 

특정 노드의 자식 수를 노드의 차수(Degree)라고 부르며 트리의 모든 노드 중에 가장 높은 차수를 트리의 차수라고 말합니다. 그리고 차수가 0인(자식이 없는) 노드를 단말(Terminal) 혹은 잎(Leaf)이라고 부릅니다.

 

자신의 자식을 루트로 하는 트리를 서브 트리(Sub Tree)라고 부르며 차수와 서브 트리의 개수는 같습니다.

 

트리 중에 모든 노드의 차수가 2 이하로 구성하는 트리를 이진 트리(Binary Tree)라고 말합니다. 그리고 마지막 레벨까지 모든 노드가 있을 때 포화 이진 트리(Full Binary Tree, 꽉 찬 이진 트리) 혹은 정 이진 트리라 말하며 노드를 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리를 완전 이진 트리(Complete Binary Tree) 혹은 전 이진 트리라고 말합니다.

 

꽉 찬 이진 트리에서 Level N에는 2의 N-1 승의 노드가 존재합니다. 따라서 높이 H인 꽉 찬 이진 트리에는 2의 H승 – 1 개의 노드가 존재합니다.

 

그리고 한 쪽으로 기울어진 트리를 사향 트리 혹은 편향 트리라고 부릅니다.

 

루트(Root): 부모가 없는 노드

정점(Vertex): 자료를 보관하는 단위, 노드(Node)라고 부름

간선(Edge): 정점에서 다른 정점으로 가는 경로, 링크(Link, 다른 노드의 위치 정보) 혹은 가지(Branch)로 부름

N(V) = N(E)+1 , N(V)는 정점의 개수, N(E)는 간선의 개수

레벨(Level): 루트에서 자신에게 걸리는 거리를 레벨(Level), 루트를 Level 1로 출발

트리의 높이(Height): 가장 높은 레벨(Level), 깊이(Depth)라고 부름

부모(Parent): Level N인 노드로 가기 위한 Level N-1에 있는 노드

자식(Son): Level N인 노드와 연결 상태인 Level N+1에 있는 노드

형제(Sibling): 같은 부모를 갖는 노드

조상(Ancestors): 자신에게 오기 위한 경로에 있는 모든 노드

후손(descendant): 자신을 출발로 갈 수 있는 모든 노드

노드의 차수(Degree): 특정 노드의 자식 수

트리의 차수: 트리의 모든 노드 중에 가장 높은 차수

단말(Terminal): 차수가 0인(자식이 없는) 노드, 단말(Terminal) 혹은 잎(Leaf)이라고 부름

서브 트리(Sub Tree): 자신의 자식을 루트로 하는 트리, 차수와 서브 트리의 개수는 같음

이진 트리(Binary Tree): 트리 중에 모든 노드의 차수가 2 이하로 구성하는 트리

포화 이진 트리(Full Binary Tree, 꽉 찬 이진 트리): 마지막 레벨까지 모든 노드가 있는 이진 트리

완전 이진 트리(Complete Binary Tree): 노드를 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리

사향 트리(Skewed Binary Tree),: 한쪽으로 기울어진 트리, 편향 트리라고도 부름

꽉 찬 이진 트리 N(Level n) = 2의 N-1 승

꽉 찬 이진 트리 N(Height h) = 2의 h승 – 1