파이썬) 트리(Tree)

트리란 정점(Node)와 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한 자료구조를 말한다.

 

위 트리는 10개의 노드와 9개의 간선을 가진다. 

 

트리에 대한 용어들을 정리하자면

• 루트(Root) 노드 : 트리의 맨 위에 있는 시작점 노드를 뜻한다. 위 트리에서 루트 노드는 A이다.
• 리프(Leaf) 노드 : 더 이상 아래로 간선을 가지지 않는 트리의 맨 아래에 있는 노드를 뜻한다. 위 트리에서 리프 노드는 G,H,I,E,J이다.
• 내부(Internal) 노드 : 루트, 리프 노드가 아닌 중간에 있는 노드를 뜻한다. 위 트리에서 내부 노드는 B,C,D,F이다.
•  부모,자식 노드 : 한 간선으로 연결된 두 노드를 기준으로 위에 있는 노드를 부모 노드, 아래에 있는 노드를 자식 노드라고 한다. 노드 D는 G,H,I의 부모 노드이고 동시에 B의 자식 노드이다. 그리고 같은 부모를 가진 노드들을 서로 형제간이라 한다.
• 노드의 수준(Level): 루트 노드를 시작으로 몇개의 간선을 통해 자식노드에 갈 수 있는지에 대한 지표이다.

루트 노드 A의 수준은 0이고, A의 자식 노드 B,C는 한개의 간선을 통해 이동할 수 있으므로 수준은 1이된다. 위 트리과 같이 리프 노드까지 수준을 매길 수 있다.

• 트리의 높이(Height) 또는 깊이(Depth): 최대 수준(Level)+1로 정의한다. 위 트리의 높이는 3+1=4가 된다.
• 노드의 차수(Degree) : 자식 노드의 수를 의미한다.

루트 노드 A의 자식 노드는 B,C 두개가 있다. 따라서 A의 차수는 2이다. 리프 노드는 맨 아래 있는 노드이므로 차수는 자동으로 0이 된다. 위 트리와 같이 차수를 구할 수 있다.

 

트리의 종류에는 여러가지가 있는데 자료구조에서 특히 관심을 가지는 트리에는 이진 트리(Binary Tree)가 있다. 이진 트리란 모든 노드의 차수가 2이하인 트리를 말한다. 

이 트리의 차수는 모두 2이하이므로 이진 트리라 할 수 있다. 

 

포화 이진 트리(Full Binary Tree)란 모든 레벨에 노드들이 모두 채워져 있는 이진 트리를 말한다. 다른 말로 높이가 k이고 노드의 개수가 2^k -1개인 이진 트리이다.

위 트리의 높이는 3이고 노드의 개수는 8-1=7개 이므로 포화 이진 트리이다.

 

완전 이진 트리(Complete Binary Tree)는 다음 조건을 만족하는 트리이다.

 

- 높이가 k이고

- 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리

- 레벨 k-1에서는 왼쪽부터 순차적으로 노드가 채워져 있는 이진 트리

 

위 트리는 높이가 3이고, 레벨 1까지는 A가 B,C 2개의 자식 노드를 가진 포화 이진 트리이고, 레벨 2에서는 왼쪽부터 순차적으로 노드가 채워져 있으므로 완전 이진 트리이다.