트리 (Tree)

# 트리 구조

트리란 Node와 Branch를 이용해, 사이클을 이루지 않도록 구성한 데이터구조. 재귀적인 구조이다.

여러 트리의 구조 중 이진트리 형태의 구조는 탐색 알고리즘 구현을 위해 많이 사용된다.

 

# 용어

Node : 트리에서 데이터를 저장하는 기본 요소

Edge : 각 노드들을 연결하는 선

Root Node : 트리 맨 위에 있는 Node

Level : 최상위 노드를 Level 0으로 할 때, 노드의 깊이

Parent Node : 부모 노드. 즉, 자신의 노드 위에 있는 노드

Child Node : 자식 노드. 즉, 자신의 노드 밑에 있는 노드

Leaf Node : 자식 노드가 하나도 없는 노드

Siblings : 동일한 Parent Node를 가진 노드

Depth : 트리에서 최대 Level

 

# 이진트리의 유형

전 이진트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.

완전 이진트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져

있는 트리이다.

포화 이진트리(Perfect Binary Tree) : 모든 내부 노드가 두 개의 자식 노드를 가지며 모든

잎 노드가 동일한 깊이 또는 레벨을 갖는다.

균형 이진트리(Balanced Binary Tree) : 왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는

트리이다. 예를 들어 AVL 및 Red-Black 트리는 균형 이진 트리이다.

 

# 이진트리 표현

배열 또는 연결 리스트로 표현이 가능하다.

- 배열

루트 노드의 인덱스가 0인 경우

노드 i에 왼쪽 자식은 2*i+1 번째 노드이다.

노드 i에 오른쪽 자식은 2*i+2 번째 노드이다.

노드 i에 부모는 (i-1)/2 번째 노드이다.

배열을 사용하면 노드 접근이 빠르고 구현이 용이하다는 장점이 있지만,

편향 이진트리같은 경우 많은 공간이 낭비되고 배열 크기 이상 노드를 추가할 수 없다.

 

# 이진트리 순회

전위 순회 (preorder) : root -> left -> right 순으로

중위 순회 (inorder) : left -> root -> right 순으로

후위 순회 (postorder) :  left -> right -> root 순으로 순회를 한다.

root의 위치에 따라 전위, 중위, 후위로 나뉜다.

재귀적인 자료구조라 순회도 재귀적으로 한다. 

 

# 이진 트리와 이진 탐색 트리

이 두개는 비슷해 보이지만 다르다.

이진트리는 노드의 최대 Branch가 2인 트리

이진 탐색 트리는 이진 트리에 추가적인 조건이 있다.

바로, 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있다.

즉, 이진 탐색트리는 이진트리에서 좀 더 탐색을 쉽게하기위해 업그레이드된 것이다.

 

# 이진 탐색 트리의 시간복잡도

트리의 높이 depth를 h라고 표기한다면 O(h)

h = log2 (n)

O(log2 (n)) -> 트리의 깊이

 

하지만 단점이 존재하는데 트리의 균형이 잘 잡혀있지 않을 때는 링크드 리스트와 같은 형태가 돼

동일한 성능을 보여주게 된다.

 

# 이진 탐색 트리 구현

삽입과 탐색, 삭제을 구현해준다.

https://ha-young.github.io/2020/data-structrue/2020-09-22-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Tree%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90---2-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%AC-%EA%B5%AC%ED%98%84/

자료구조 Tree에 대해 알아보자 - 2 이진 탐색 트리 구현

공부하는데 도움이 많이 된 좋은 글이다.

이걸 보고 공부해주자.

 

삭제는

1. 삭제할 노드가 Leaf Node

2. 삭제할 노드의 자식 노드가 1개

3. 삭제할 노드의 자식 노드가 2개

로 경우의 수를 나눠서 한다.