트리
트리는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)로, 루트 값과 부모-자식 관계의 서브 트리로 구성되며, 서로 연결된 노드의 집합이다.
하나의 뿌리에서 뻗어 나가는 형상, 즉 나무처럼 생겨서 '트리'라는 명칭이 붙었다.
트리는 재귀로 정의된 자기 참조 자료구조이다. 따라서 자식도 트리고 그 자식도 트리이다. 즉, 여러개의 서브 트리가 쌓아 올려져 큰 트리가 된다.
트리 자료구조 중 이진트리, 이진탐색트리(BST)가 널리 사용된다.
트리의 구성
루트는 자식 노드와 간선(Edge)으로 연결되어 트리 구조를 형성한다.
(단방향 -> 간선 화살표 생략 가능)
루트(Root): 트리의 시작점
차수: 연결된 자식노드의 개수
리프(Leaf): 트리의 가장 끝 노드
크기: 자신을 포함한 모든 자식 노드의 개수 (ex. 5의 크기: 3)
깊이(Depth): 루트에서 현재 노드까지의 거린
높이(Height): 현재 위치에서 리프(Leaf)까지의 거리
레벨(Level): 노드 계층
그래프 vs 트리
트리는 순환구조를 갖지 않는 그래프이다.
트리는 특수한 형태의 그래프 일종으로, 한번 연결된 노드가 다시 연결되지 않는다.
또한 단방향, 양방향을 모두 가리킬 수 있는 그래프와 달리 부모 노드에서 자식 노드를 가리키는 단방향뿐이다.
- 트리가 아닌 예시
이진 트리
각 노드가 m개 이하의 자식을 가지고 있는 트리를 m-ary 트리(다항트리, 다진트리)라 한다.
이때 m=2일 경우, 즉 모든 노드의 차수 2 이하(자식 노드가 2개 이하)일때 이진 트리(Binary Tree)라고 부른다.
따라서 각 노드마다 왼쪽, 오른쪽 최대 2가의 자식을 가지는 매우 단순한 형태로 대표적으로 3가지의 유형이 있다.
이진 트리 유형
정 이진 트리 (Full Binary Tree)
모든 노드가 0개 or 2개의 자식 노드를 갖는다.
완전 이진 트리 (Complete Binary Tree)
마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다. 단, 마지막 레벨의 노드들은 왼쪽부터 채워져야 한다.
포화 이진 트리 (Perfect Binary Tree)
모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.
균형 이진 트리 (Balenced Binary Tree)
왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 이진 트리
이진 트리 속성
레벨(level) - 노드
n 레벨 에서의 최대 노드 수: 2ⁿ
높이(h) - 노드 합
n 높이 에서의 이진 트리의 최대 노드의 개수: 2ⁿ-1 (시작 높이:0 일 시 2 n+1(제곱)-1)
높이: n
2ⁿ-1 = 노드 개수
2ⁿ= 노드 개수 + 1
n = log2[밑](노드개수 +1)
높이 = log2[밑](노드개수 +1)이진 트리 표현
배열(Array)
루트 노드의 index가 0인 경우
노드 index i 일때,
-> 왼쪽 자식 노드 index: 2 x i
-> 오른쪽 자식 노드 index: 2 x i + 1
-> 부모 노드의 index: (i-1)/2루트 노드의 index가 1인 경우
노드 index i 일때,
-> 왼쪽 자식 노드 index: 2 x i +1
-> 오른쪽 자식 노드 index: 2 x i + 2
-> 부모 노드의 index: i/2
완전 이진 트리 경우, 배열 공간을 효율적으로 쓰고 있음
편향 트리(skew tree) 인 경우, 많은 배열 공간이 낭비됨
배열을 사용하면 노드 접근이 빠르고 구현이 용이하지만, 편향 이진트리 같은 경우 많은 공간이 낭비될 수 있고 배열 크기 이상 노드를 추가할 경우 리사이징을 하여 비용 낭비가 발생한다.
연결리스트(포인터)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right연결 리스트는 배열보단 접근 속도가 느리지만 삽입 삭제가 쉽고 노드를 포인터로 연결하기 때문에 노드 수에 제한 없음
Reference)
파이썬 알고리즘 인터뷰
https://ko.wikipedia.org/wiki/트리_구조
https://namu.wiki/w/트리(그래프)#s-4
https://medium.com/quantum-ant/%ED%8A%B8%EB%A6%AC-tree-cec69cfddb14
https://yoongrammer.tistory.com/69 - 이진트리 속성, 표현 - 이미지, 설명 참조
- 1차 작성[22.08.29]: 트리, 트리 구성, 그래프, 트리 차이점,
- 2차 작성[22.09.01]: 이진트리 - 유형, 속성, 표현 __정리
