트리(tree)란?
(사진출처 https://creativecommons.org/licenses/by-nc/2.0/kr/)
트리(tree)는 계층적인 구조를 가진 비선형 자료구조로, 하나의 루트 노드에서 시작하여 각 노드가 여러 자식 노드를 가질 수 있는 구조를 말합니다.
트리 구조에서 사용되는 주요 용어
루트(Root)
- 트리의 시작 노드를 말함.
- 모든 다른 노드는 루트에서부터의 상대적인 위치를 가지게 된다.
노드(Node)
- 트리의 기본 구성 요소로, 데이터와 다수의 자식 노드에 대한 참조를 포함.
에지(Edge)
- 노드 간의 연결을 나타내는 선으로, 두 노드를 연결.
부모 노드(Parent Node)
- 어떤 노드의 바로 위에 위치한 노드.
- 즉, 특정 노드의 자식 노드를 가리키는 노드
자식 노드(Child Node)
- 어떤 노드 아래에 위치한 노드.
- 특정 노드의 부모 노드가 될 수 있다.
리프(Leaf)
- 자식이 없는 노드로, 트리의 가장 끝단에 위치한 노드.
서브트리(Subtree)
- 트리 내에서 어떤 노드와 그 노드의 모든 자손 노드로 이루어진 트리를 의미.
이진 트리(Binary Tree)
각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조를 말합니다.
이진 트리는 간단하면서도 다양한 응용 분야에서 사용되며, 다양한 종류의 이진 트리가 존재합니다.
트리순회
전위 순회(Preorder Traversal)
루트를 먼저 방문한 후, 왼쪽 서브트리를 전위 순회하고, 마지막으로 오른쪽 서브트리를 전위 순회합니다.
1. 방문 노드 2. 왼쪽 서브트리를 전위 순회 3. 오른쪽 서브트리를 전위 순회
중위 순회(Inorder Traversal):
왼쪽 서브트리를 중위 순회한 후에 루트를 방문하고, 마지막으로 오른쪽 서브트리를 중위 순회합니다.
1. 왼쪽 서브트리를 중위 순회 2. 방문 루트 3. 오른쪽 서브트리를 중위 순회
후위 순회(Postorder Traversal)
왼쪽 서브트리를 후위 순회하고, 오른쪽 서브트리를 후위 순회한 후에 루트를 방문합니다.
1. 왼쪽 서브트리를 후위 순회 2. 오른쪽 서브트리를 후위 순회 3. 방문 루트
예시: 아래 이진 트리를 기준으로 각 순회 방법
1
/ \
2 3
/ \
4 5전위 순회: 1 -> 2 -> 4 -> 5 -> 3
중위 순회: 4 -> 2 -> 5 -> 1 -> 3
후위 순회: 4 -> 5 -> 2 -> 3 -> 1
이진 트리의 특징
- 각 노드는 최대 두 개의 자식 노드를 가집니다.
- 왼쪽 자식 노드와 오른쪽 자식 노드는 순서를 가지며, 순서에 따라 부모 노드와 관련이 있습니다.
- 이진 트리는 재귀적인 성질을 가지고 있습니다. 각 자식 노드는 또 다른 이진 트리의 루트가 될 수 있습니다.
이진 트리의 종류
정 이진 트리(Full Binary Tree)
- 모든 레벨에서 노드들이 꽉 차 있는 이진 트리.
- 각 레벨의 노드 수가 2의 거듭제곱인 경우가 해당.
완전 이진 트리(Complete Binary Tree)
- 높이가 h인 이진 트리에서 레벨 1부터 h-1까지는 노드들로 꽉 차 있고, 마지막 레벨은 왼쪽부터 노드들이 채워져 있는 트리.
- 배열을 사용하여 효율적으로 구현할 수 있는 특징이 있다.
포화 이진 트리(Perfect Binary Tree)
- 모든 레벨에서 노드들이 꽉 차 있고, 모든 리프 노드가 동일한 깊이에 있는 이진 트리.
- 정 이진 트리와 완전 이진 트리의 특징을 모두 가지고 있다.
편향 이진 트리(Skewed Binary Tree)
- 한 쪽으로만 자식 노드를 가지는 트리로, 성능이 매우 저하될 수 있는 구조.
- 특정 상황에서는 연결 리스트와 유사한 효과를 나타낼 수 있다.
이진 탐색 트리(Binary Search Tree, BST)
이진 탐색 트리(Binary Search Tree, BST)는 효율적인 탐색, 삽입, 삭제 연산을 지원하는 이진 트리의 일종입니다.
이진 탐색 트리는 각 노드가 최대 두 개의 자식을 가지며, 다음 규칙을 따르도록 구성됩니다
- 왼쪽 서브트리 조건: 어떤 노드 N의 왼쪽 서브트리에 속한 모든 노드들은 N의 값보다 작아야 합니다.
- 오른쪽 서브트리 조건: 어떤 노드 N의 오른쪽 서브트리에 속한 모든 노드들은 N의 값보다 커야 합니다.
- 중복된 값이 없음: 모든 노드의 값은 서로 다르아야 합니다.(중복X)
오늘의 기록