1️⃣ None Linear Data Structure
비선형 데이터 구조는 데이터 요소가 선형적으로 나열되지 않고, 계층적이거나 복잡한 연결 관계를 가진 구조를 말한다. 이러한 데이터 구조는 다양한 수준의 관계를 갖고 데이터 요소를 구성하며, 여러 경로를 통해 요소들 사이를 탐색할 수 있다. 대표적인 비선형 데이터 구조로는 트리와 그래프가 있다. 오늘은 트리에 대해 알아보도록 하자.
2️⃣ 트리(Tree)
트리는 노드로 구성된 계층적 데이터 구조로, 한 노드가 여러 노드를 가리킬 수 있지만, 어떤 노드도 두 개 이상의 노드에 의해 가려켜지지 않는다. 각 노드는 특정 값을 저장하며, 노드 간에는 부모-자식 관계가 있다. 트리 구조의 종류로는 일반 트리, 이진 트리, 이진 검색 트리, AVL 트리, 레드-블랙 트리 등이 있다.
3️⃣ 트리(Tree)의 구성요소
1. 노드(Node)
트리의 기본 요소로, 데이터를 저장한다. 각 노드는 하나 이상의 자식 노드를 가질 수 있고, 정확히 하나의 부모 노드를 갖고 있다. (루트 노드는 제외한다.)
2. 루트 노드(Root Node)
트리 구조에서 최상위에 위치하며, 부모 노드가 없는 유일한 노드이다.
3. 리프 노트(Leaf Node)
자식 노드가 없는 노드로 트리의 가장 아래에 위치한다.
4. 서브 트리(Subtree)
트리의 어떤 노드와 그 자손 노드들로 구성된 트리이다.
5. 깊이(Depth)
루트 노드에서 특정 노드에 이르는 경로에 포함된 에지(Edge, 연결선)의 수이다.
6. 높이(Height)
트레에서 가장 긴 경로에 있는 노드의 깊이이다.
4️⃣ 트리(Tree)의 유형
1. 바이너리 트리(Binary Tree)
각 노드가 최대 두 개의 자식을 가지는 트리
2. 바이너리 서치 트리(BST, Binary Search Tree)
바이너리 트리의 한 형태로, 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자신 노드는 부모 노드보다 큰 값을 갖도록 구성된 데이터 구조이다. 이 구조는 검색, 삽입, 삭제 작업을 효율적으로 수행할 수 있도록 한다.
3. AVL 트리
자동으로 균형을 잡는 바이너리 서치 트리로, 모든 노드의 좌우 서브트리의 높이 차가 최대 1을 넘지 않도록 유지한다.
4. 레드-블랙 트리
균형 잡힌 바이너리 서치 트리의 한 종류로, 노드의 색상(레드 또는 블랙)을 사용하여 트리의 균형을 유지한다.
5️⃣ Python 예제 : Binary Tree
- 노트 클래스 정의
- 각 노드는 자신의 데이터와 왼쪽 및 오른쪽 자식에 대한 참조를 저장한다.
- 이진 트리 클래스 정의
- 이진 트리를 구성하고 노드를 추가하며, 다양한 방식으로 트리를 순회하는 메소드를 제공한다.
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, key):
if self.root is None:
self.root = Node(key)
else:
self._insert(self.root, key)
def _insert(self, node, key):
if key < node.val:
if node.left is None:
node.left = Node(key)
else:
self._insert(node.left, key)
else:
if node.right is None:
node.right = Node(key)
else:
self._insert(node.right, key)
def inorder_traversal(self, node):
elements = []
if node:
elements += self.inorder_traversal(node.left)
elements.append(node.val)
elements += self.inorder_traversal(node.right)
return elements
# 사용 예
tree = BinaryTree()
tree.insert(8)
tree.insert(3)
tree.insert(10)
tree.insert(1)
tree.insert(6)
tree.insert(14)
# 중위 순회(Inorder Traversal) 출력
print("Inorder Traversal:", tree.inorder_traversal(tree.root))
🖥️ 각 코드별 설명
1. 노드 클래스(Node Class)
- 'Node' 클래스는 트리의 기본 단위인 노드를 정의한다.
- '__init__' 메소드는 노드 객체를 생성할 때 호출된다.
- 'key' : 노드에 저장될 데이터이다.
- 'left'와 'righ' 속성의 각각 노드의 왼쪽 및 오른쪽 자식을 가리키며, 초기에는 'None'으로 설정된다. 이는 자식 노드가 없을 의미한다.
2. 이진 트리 클래스(Binary Tree Class)
- 'BinaryTree' 클래스는 이진 트리를 정의하고 관리한다.
- '__init__' : 트리의 루트 노드를 초기화한다. 트리가 비어있을 땐 루트가 'None'이다.
- 'insert' 새로운 키를 트리에 삽입하는 메소드이다. 루트 노드가 'None' 이면 새 노드를 루트로 설정하고, 그렇지 않으면 '_insert' 메소드를 재귀적으로 호출하여 적절한 위치에 노드를 추가한다.
- '_insert' : 재귀적으로 노드를 삽입하는 내부 메소드이다. 삽일할 키와 현재 노드의 값을 비교하여 왼쪽 또는 오른쪽 서브트리에 삽입한다. 적절한 위치에 돋ㄹ하면 새 노드를 생성하여 연결한다.
3. 중위 순회 메소드(Inorder Traversal Method)
- 'inorder_traversal' : 중위 순회를 통해 트리의 모든 노드들 정렬된 순서로 방문하고 값을 리스트로 반환한다.
- 이 메소드는 왼쪽 서브트리를 재귀적으로 방문한 다음, 현재 노드의 값을 리스트에 추가하고 마지막으로 오른쪽 서브트리를 방문한다.
- 중위 순회는 이진 검색 트링서 노드를 오름차순으로 방문하는 가장 일반적인 방법이다.
4. 사용 예
- 이 부분은 'BinaryTree' 인스턴스를 생성하고 여러 키를 트리에 삽입한 다음 중위 순회 트리를 사용하여 트리의 모든 노드를 오름차순으로 출력한다.