[트리] 이진 트리 & 이진 검색 트리 & 트리 DP

📌 트리(Tree)

계층적인 구조를 표현한다.
ex) 조직도, 디렉토리, 가계도 등
노드(Node)와 노드들을 연결하는 링크(Link)들로 구성된다.

📌 용어

루트(root) : 시작 노드

자식 노드를 가진다.
자식 노드는 링크(Link)로 연결되어 있다.

형제(sibling) 관계

부모가 동일한 노드들의 관계를 형제 관계라고 부른다.
루트 노드를 제외한 나머지 노드들은 유일한 부모 노드를 가진다.

리프(leaf) 노드

자식이 없는 노드들을 리프 노드라고 부른다.
리프 노드가 아닌 노드들은 내부(Internal) 노드라고 부른다.

부트리(Sub Tree)

트리에서 어떤 한 노드와 자손으로 이루어진 트리를 부트리라고 부른다.

레벨(Level)

높이(height)

레벨의 개수

차수

자식 노드의 개수

크기

모든 자식 노드의 개수

깊이

루트에서부터 현재 노드까지 거리
위에서 아래로 단방향으로 향한다.

📌 트리의 기본적인 성질

N개의 노드의 트리는 항상 N-1개의 링크(link)를 가진다.
어떤 노드로 가는 길은 유일하다. (같은 노드를 두 번 이상 방문하지 않는 조건하에)

📌그래프와 트리의 차이점

트리는 순환 구조를 가지지 않는 그래프이다.
트리는 한번 연결된 노드가 다시 연결되는 법이 없다.
그래프는 단방향, 양방향을 가리킬 수 있다.
트리는 부모에서 자식을 가리키는 단방향 뿐이다.
트리는 하나의 부모 노드를 갖는다.
💬
그래프의 일종으로, 트리는 순환 구조를 가지지 않는다. 그래프는 단방향, 양방향 모두 가리킬 수 있지만 트리는 하나의 부모를 가지며, 부모에서 자식을 가리키는 단방향 뿐이다.

📌 이진 트리

트리 중에서 가장 널리 사용되는 트리 자료구조는 이진 트리이진 탐색 트리(Binary Search Tree)이다.
각 노드는 최대 2개의 자식을 가진다.
각 노드는 부모의 왼쪽 자식인지 오른쪽자식인지가 지정된다.

이진 트리의 응용

Expression Tree
Haffman Code
a ~ z로 이루어진 파일이 있으면 → 인코딩 했을때 파일의 길이를 최소화할 수 있음

이진 트리의 종류

정 이진 트리(Full Binary Tree)

모든 노드가 0개 또는 2개의 자식 노드를 갖는다.

완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.

포화 이진 트리(Perfect Binary Tree)

모든 노드가 2개의 자식 노드를 갖고 있다.
모든 리프 노드동일한 깊이 또는 레벨을 갖는다.
문자 그대로 가장 완벽한 유형의 트리이다.

이진 트리의 표현

연결 구조(Linked Structure) 표현
각 노드에 아래와 같은 정보를 가진다.
데이터 필드
왼쪽 자식(left)
오른쪽 자식(right)
부모 노드(p)
부모 노드의 주소는 반드시 필요한 것이 아니면 생략한다.

이진 트리 순회(Traversal)

이진 트리의 모든 노드를 방문하는 것을 말한다.
1~3번은 유사하다.
1.
중순위(inorder) 순위 → left, x, right
2.
선순위(preorder) 순회 → x, left, right
3.
후순위(postorder) 순회 → left, right, x
4.
레벨오더(level-order) 순회
레벨 순으로 방문한다.
동일 레벨에서는 왼쪽에서 오른쪽 순서로 방문한다.
주로 큐를 이용해서 구현한다.
Q에 노드를 넣는다.
Q에서 꺼내서 방문하고, 자식 노드를 넣는다.
위 2가지 반복

📌 이진 검색 트리(Binary Search Tree)

자식이 2개 이하이기 때문에 왼쪽 자식과 오른쪽 자식으로 구분할 수 있다. 따라서 이진 검색 트리는 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진 트리를 의미한다.

시간 복잡도

삽입, 삭제, 검색 모두 O(log N)
트리가 편향됨에 따라 실제 시간 복잡도는 최악의 경우 O(N), 이를 개선한 자가 균형 트리가 존재한다.

삽입

루트부터 자기 자리를 찾아가는데 비교하는 횟수와 비례한다.
O(N)

검색

루트부터 좌우로 움직인다.
높이에 비례한다.

삭제

지우면 끝나는 것이 아니다.
자식 노드가 없으면 그냥 지워도 상관없다.
아래와 같은 상황에서 생기면, 어떤 노드를 25자리에 옮겨야 할지 고민이 생긴다.
32를 25자리로 보내면 이진 검색 트리의 성질을 만족한다. 따라서 25보다 크면서 가장 작은 수를 옮겨야 한다.
자기 자리를 찾아가는데 높이에 비례하게 된다.

편향 트리의 문제점과 이를 개선하기 위한 트리

트리가 편향되어 있는 경우 삽입, 삭제시 공간 복잡도를 많이 쓰는 상황이 생긴다.
이진 검색 트리가 편향되지 않게 바로잡도록 삽입, 삭제를 개선한 트리가 있다. 주로 AVL 트리와 Red Black 트리를 많이 다룬다.

📌 트리 DP

💬
DP(Dynamic Programming)? 부분 문제의 해를 이용하여 큰 문제의 해를 구한다. (DP는 보통 선형으로 이루어진 공간)

트리 DP란?

트리에서 dp를 하는 것. (트리는 비선형 구조)
서브 트리에서 구한 해를 이용하여 전체 트리의 해를 구한다.

어떤 로직으로 수행되나?

dp[i] = i를 루트로 하는 서브 트리의 ~~와 같은 식으로 dp 테이블을 정의한다.
트리에서 dp를 하기 전에 일반적으로 탐색 순서를 미리 정해준다.
탐색 순서는 dfs를 돌면서 나오는 트리, 즉 dfs tree를 기준으로 한다.
트리 dp도 대부분 상태 dp가 들어간다.
💬
상태 DP? ex) dp[i][j] = i를 루트로 하는 서브트리에서 i의 상태가 j일 때 ~~와 같은 식으로 한다.

📌 참고 자료

TOP