트리 (Tree)

출처 : 파이썬 알고리즘 인터뷰

트리(Tree)는 계층 구조를 표현하는 비선형 자료 구조입니다. 하나의 루트(Root)노드에서 시작하여 여러 레벨의 자식 노드들이 분기되는 구조를 가지고 있습니다. 각 노드는 부모 노드와 자식 노드를 가지고 있으며, 한 노드는 여러 개의 자식 노드를 가질 수 있습니다.

 

트리는 이진 트리(Binary Tree)와 다진 트리(M-ary Tree)로 나뉩니다. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리를 의미합니다. 다진 트리는 각 노드가 최대 M개의 자식 노드를 가지는 트리를 의미합니다. 대표적으로 3진 트리, 4진 트리 등이 있습니다.

 

트리는 다음과 같은 용어를 사용합니다.

• 루트(Root) : 트리의 최상위 노드이며, 모든 노드는 루트로부터 직간접적으로 연결되어 있습니다.
• 부모(Parent) : 자식 노드들을 가진 노드를 의미합니다.
• 자식(Child) :  부모 노드에서 분기된 노드들을 의미하며, 부모 노드와 자식 노드는 서로를 가리킬 수 있는 관계를 갖습니다.
  
• 잎(Leaf) : 자식 노드가 없는 노드이며, 해당 노드가 트리의 끝에 위치한 노드입니다.
• 깊이(Depth)/레벨(Level) : 루트 노드부터 해당 노드까지의 경로를 따라 내려갈 때 거쳐가는 노드의 수를 의미합니다.
• 높이(Height) : 해당 노드부터 잎 노드까지의 가장 긴 경로의 길이를 의미합니다.

트리는 다양한 방식으로 구현될 수 있으며, 대표적인 방식으로는 배열과 연결리스트가 있습니다. 배열을 사용하면 인덱싱 연산이 빠르지만, 크기가 고정되어 있으므로 삽입 및 삭제 시에 다른 원소들을 이동해야 하므로 비효율적일 수 있습니다. 연결 리스트를 사용하면 크기가 유동적이지만, 삽입 및 삭제 시 포인터 연산이 필요하므로 일반적으로 배열보단 느립니다.