알고리즘 , 자료구조
[자료구조] 트리 (Tree)
KimGeon-U
2025. 1. 8. 23:38
트리 (Tree)
트리(Tree)는 계층적 관계를 나타내는 자료구조로 노드(Node)와 간선(Edge)로 구성되어잇으며 가장 상위 노드인 루트(Root)가있다. 각 노드는 다른 노드와 연결되어 부모.자식 관계를 형성하며 노드들은 자식 노드를 가질 수 있습니다.
- 노드(Node) : 트리의 각 요소. 데이터를 표현하는데 사용한다.
- 간선(Edge) : 두 노드를 연결, 관계를 나타낸다.
- 루트(Root) : 트리의 최상위 노드. 부모가 없는 노드
- 부모(Parent) : 다른 노드를 자식으로 가지는 노드
- 자식(Child) : 부모 노드에 의해 연결되는 노드
- 리프(Leaf) : 자식 노드가 없는 노드
특징 및 종류
- 트리는 계층적으로 구성되어 있으며, 루트노드를 시작으로 여러 자식 노드들이 존재 할 수 있다.
- 노드는 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
- 두 노드간의 경로는 유일하다.
- 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
- 트리는 이진트리, 이진탐색트리(BST), 균형트리(AVL, RBT), 이진 힙(최대힙, 최소힙) 등이 있다.
이진트리(Binary Tree)
- 각 노드가 최대 두개의 자식을 갖는 트리
- 모든 트리가 이진 트리는 아니다
- 기본적인 트리 구조로, 이진 검색트리, 힙(Heap) 트리 등에 사용된다.
이진탐색트리 (Binary Search Tree)
- 이진 트리의 형태, 각 노드는 키 값이 왼쪽 서브 트리의 모든 값보다 크고, 오른쪽 서브트리의 모든 값보다 작다.
- 삽입, 삭제, 검색 등이 평균적으로 O(log n)의 시간 복잡도를 가지고 있다.
- 트리가 불균형시 최악의 경우 O(n)의 시간복잡도를 가진다.
- AVL Tree : 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이차이가 1인 이진 탐색 트리
- 삽입,삭제시 회전(Rotate)하며 트리구조의 균형을 유지한다.
- RB Tree : 각 노드에 색깔(Red,Black)을 부여하여 균형을 맞추는 이진 탐색 트리
- AVL과 같이 노드간의 균형을 유지하지만, 더 적은 회전을 하며 정렬한다.
힙(Heap)
- 각 부모 노드의 값이 자식 노드의 값보다 우선순위가 높은 구조
- 최대 힙과 최소 힙이 있다.
- 최대 힙 : 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
- 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작거나 같다.
- 완전 이진 트리 형태를 가지며, 삽입,삭제 시 O(log n)의 시간복잡도를 가진다.
그래프 VS 트리
