비선형 자료구조
정의
무엇을 저장하고 꺼내야 한다는 사고를 벗어나야 합니다.
용어
트리에 사용되는 다양한 용어가 있습니다.🧩 노드 (Node)
- 데이터를 저장하는 단위로, 트리를 구성하고 있는 각각의 요소입니다.
- 각 노드는 0개 이상의 자식을 가집니다.
🧩 간선 (Edge)
- 계층을 표현하는 선입니다.
- 부모 노드와 자식 노드를 연결합니다.
🧩 루트 (Root)
- 트리 구조에서 시작점이 되는 최상위 노드입니다.
- 루트에는 부모가 있지 않습니다.
🧩 리프 (Leaf)
- 자식이 없는 노드이며, 단말 노드라고 합니다.
- 하위에 다른 노드가 연결되어 있지 않습니다.
🧩 내부 (Internal)
- 단말 노드를 제외한 모든 노드이며, 비단말 노드라고 합니다.
- 루트 노드도 포함합니다.
🧩 높이 (Height)
- 루트에서 가장 깊은 리프까지의 거리를 루트 높이라고 합니다.
- 해당 노드에서 리프까지 가는 가장 긴 경로의 간선 수를 노드 높이라고 합니다.
🧩 서브 트리 (Height)
- 트리 안에 포함된 작은 트리입니다.
- 트리의 임의의 노드를 새로운 루트로 잡았을 때, 그 노드를 포함한 모든 하위 노드들이 이루는 트리입니다.
종류
트리에는 다양한 종류가 있습니다.일반 트리 (General Tree)
트리 (Tree) 정의트리 자료구조의 가장 일반적인 형태입니다.가장 자유로운 트리 구조로, 자식의 수에 제한이 없어 각 노드가 0개 이상의 자식 노드를 가질 수 있습니다.트리 자료구조의 구조와
develop-enchantment.tistory.com
🌲 이진 트리 (Binary Tree)
- 계층을 표현하는 선입니다.
- 부모 노드와 자식 노드를 연결합니다.
🌲 이진 탐색 트리 (BST, Binary Search Tree)
- 트리 구조에서 시작점이 되는 최상위 노드입니다.
- 루트에는 부모가 있지 않습니다.
🌲 균형 이진 트리 (AVL, Red-Black)
- 자식이 없는 노드이며, 단말 노드라고 합니다.
- 하위에 다른 노드가 연결되어 있지 않습니다.
🌲 힙 (Heap)
- 단말 노드를 제외한 모든 노드이며, 비단말 노드라고 합니다.
- 루트 노드도 포함합니다.
🌲 트라이 (Trie)
- 루트에서 가장 깊은 리프까지의 거리를 루트 높이라고 합니다.
- 해당 노드에서 리프까지 가는 가장 긴 경로의 간선 수를 노드 높이라고 합니다.