🍇 트리 (Tree)
🍇 트리 (Tree)
트리(Tree)는 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조입니다.
모양이 마치 나무를 엎어 놓은 것과 같다고 해서 Tree 라는 이름이 붙여졌습니다.
🌲 트리(Tree)의 특징
- 트리 자료구조는 일반적으로 대상 정보의 각 항목들을 계층적으로 구조화할 때 사용하는 비선형 자료구조입니다.
- 트리의 구조는 '데이터 저장'의 의미보다는 '저장된 데이터를 더 효과적으로 탐색'하기 위해서 사용됩니다.
- 리스트 처럼 데이터가 단순히 나열되는 구조가 아니라 부모(parent)와 자식(child)의 계층적인 관계로 표현됩니다.
- 서로 다른 두 노드의 연결이 오직 하나의 엣지 (edge) 뿐입니다..
- 트리에서 루트노드를 제외한 모든 노드는 단 하나의 부모노드를 가집니다.
🌲 트리(Tree)의 용어
- 노드 (Node) : 트리의 구성 요소로, 값(value/key)과 자식노드 有
- 엣지 (Edge) : 부모 노드와 자식 노드를 연결하는 연결선
- 루트 노드 (Root Node) : 가장 상위에 있는 노드로, 부모 노드를 갖지 않으며, 하나의 트리에 오직 하나의 루트 노드
- 단말 노드 (Leaf Node) : 가장 하위에 있는 노드로, 자식 노드X
- 내부 노드 (Internal) : 단말 노드가 아닌 모든 노드
- 부모 (Parent) : 부속 트리(Sub-tree)를 가지는 노드
- 자식 (Child) : 부속 트리에서 부모에 속하는 노드
- 형제 (Sibling) : 같은 부모 노드를 갖는 노드
- 조상 (Ancestor) : 노드의 모든 부모 노드의 집합 (현재 노드의 부모 노드, 부모의 부모 노드….)
- 자손 (Descendent) : 노드의 부속 트리에 있는 모든 하위 노드들 (현재 노드의 자식 노드, 자식 노드의 자식 노드, …)
- 깊이 (Depth) : 루트 노드에서 현재 노드 사이의 Edge의 개수
- 레벨 (Level) : 루트 노드로부터의 깊이 (루트 노드 = 1), level = depth + 1
트리에서 특정 깊이를 가지는 노드의 집합 - 높이 (Height) : 트리의 최대 레벨
- 노드의 차수 (Degree) : 하위 트리 개수, 노드가 가진 가지(자식)의 수
- 트리의 차수 (Degree of Tree) : 트리의 최대 차수
🌲 트리의 순회
👉 트리의 순회란 트리의 각 노드를 체계적인 방법으로 탐색하는 과정을 의미합니다.
노드를 탐색하는 순서에 따라 전위 순회, 중위 순회, 후위 순회 3가지로 분류됩니다.
1. 전위 순회 (Preorder)
루트노드 --> 왼쪽 서브트리 --> 오른쪽 서브트리 의 순서로 순회하는 방식입니다. (깊이 우선 순회)
2. 중위 순회 (Inorder)
왼쪽 서브트리 --> 노드 --> 오른쪽 서브트리 의 순서로 순회하는 방식입니다. (대칭 순회)
3. 후위 순회 (Postorder)
왼쪽 서브트리 --> 오른쪽 서브트리 --> 노드 의 순서로 순회하는 방식입니다.
🌲 이진 트리(Binary Tree)
트리의 종류는 크게 Binary Tree와 Non-binary Tree로 나눌 수 있습니다.
Binary Tree는 자식 노드를 최대 2개 가질 수 있으며, Non-Binary Tree는 자식의 개수에 제한이 없는 트리를 말합니다.
그 중 모든 트리의 기본이 되는 이진 트리를 알아보겠습니다.
- 이진트리(Binary Tree)는 모든 노드가 두 개 이하의 자식 노드를 갖습니다. (1개나 없는 것도 가능)
- 2개의 자식노드 중에서 왼쪽의 노드를 (Left Node)라고 하고, 오른쪽의 노드를 (Right Node)라고 합니다
▶ 이진 트리의 종류
📌편향 이진 트리 (Skewed Binary Tree)
편향 이진 트리는 하나의 차수로만 이루어져 있는 경우를 의미합니다.
이러한 구조는 배열(리스트)와 같은 선형 구조이므로 'Leaf Node'(단말 노드) 탐색 시
모든 데이터를 전부 탐색해야 한다는 단점이 있습니다.
📌포화 이진 트리 (Full Binary Tree)
포화 이진 트리는 단말노드를 제외한 모든 노드의 차수가 2개로 이루어져 있는 경우를 의미한다.
이 경우 해당 차수에 몇 개의 노드가 존재하는지 바로 알 수 있으므로 노드의 개수를 파악할 때 용이한 장점이 있습니다.
📌완전 이진 트리 (Complete Binary Tree)
완전 이진 트리는 포화 이진 트리와 같은 개념으로 트리를 생성하지만,
모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리를 의미합니다.
📌이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리(Binary Search Tree)는 탐색을 위한 이진 트리 기반의 자료구조입니다.
이진 탐색 트리는 이진 트리와 연결리스트를 합친 개념이라고 생각하면 쉽습니다.
이진 트리 : 탐색에 소요되는 시간 복잡도는 O(N), 그러나 삽입,삭제가 불가능합니다.
연결리스트 :삽입, 삭제의 시간복잡도는 O(1), 그러나 탐색하는 시간복잡도가 O(N) 입니다.
즉, 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능하게 만든 것입니다.
- left node에는 부모노드보다 작은 값이 저장됩니다.
- right node에는 부모노드와 값이 같거나 큰 값이 저장됩니다.
- 모든 노드는 중복된 값을 가지지 않습니다.
👉 이진 탐색 트리는 다음의 절차를 거쳐서 탐색합니다. (ADT)
1. 루트 노드의 키와 찾고자 하는 값을 비교합니다. 찾고자 하는 값이라면 탐색을 종료합니다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행합니다.
3. 찾고자 하는 값이 루트노드의 키보다 크다면 오른쪽 서브트리로 탐색을 진행합니다.
위 과정을 찾고자 하는 값을 찾을 때까지 반복해서 진행합니다.
만약 값을 찾지 못한다면 그대로 종료합니다.
이러한 탐색 과정을 거치면 최대 트리의 높이(h)만큼의 탐색이 진행됩니다.
👉 그럼 [28, 21, 15, 14, 32, 25, 18, 11, 30, 19]를 이진 탐색 트리의 형태로 만들어볼까요?
왜 이진 탐색 트리 형태로 만들까요?
바로 데이터를 효율적으로 검색할 수 있기 때문입니다!
원하는 값을 찾을 때까지 현재의 노드값보다 찾고자하는 값이 작으면 왼쪽으로 움직이고, 크면 오른쪽으로 움직입니다.
이렇게 원하는 값을 더 빠르게 찾을 수 있게 됩니다.
