[자료구조/알고리즘] 211011 자료구조 Tree 기초개념 복습

📌 Tree

말그대로 나무 형태인데 나무를 뒤집어 모은 모양새이다. 단방향 그래프에 하나의 뿌리로부터 가지가 사방으로 뻗은 형태라고 볼 수 있다. 간단하게 용어정리를 하자면(내가 이해하기 쉽게 적은 것이므로 공식적인 정의가 아니다)

용어정리

• 노드 : 모든 개별 데이터(숫자가 각각 적혀있는)
• 루트 : 트리의 뿌리
• 부모노드 : 말그대로 부모 노드(1하고 6의 부모노드는 3)
• 자식노드 : 말그대로 자식 노드(반대로 3의 자식노드는 1하고 6)
• 리프 : 자식노드가 없는 노드

☑ 트리에서의 깊이란?

루트로부터 특정노드의 깊이를 표현할 수 있다. 루트에서 6까지의 깊이는 2이고, 루트에서 4까지의 깊이는 3이다.

☑ 트리에서의 레벨이란?

같은 깊이를 가지고 있는 노드를 묶어서 레벨이라고 표현하는데 쉽게 말하면 층의 개념이다. 깊이(depth)가 1인 레벨은 3과 10이다. 깊이가 2인 레벨은 1과 6 그리고 14이다.

☑ 트리에서의 높이란?

리프 노드를 기준으로 루트까지의 높이(height). 4와 7그리고 13의 높이는 0이며, 1,6 그리고 14의 높이는 1이다.

서브트리?

트리구조를 갖춘 작은 트리를 가리킨다. 3,1,6도 서브트리이며, 6,4,7도 서브트리다.

트리의 실사용 예제?

• 컴퓨터의 파일탐색기
• 월드컵 토너먼트 대진표, 가계도(족보), 조직도

❗ 헷갈리지 않기

• 간선(edge)
• 정점(vertex)

📌 BST(Binary Search Tree)

많은 트리 구조 중 가장 많이쓰는 게 이진트리와 이진 탐색트리 이다. 이진트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있습니다. 자식노드가 최대 두개라는 건 자식노드가 0(=없음)일수도 1(=하나)일수도 있다는 말이다.

이진트리는 또 3가지로 나뉘진다

이진트리

• 정이진트리 : 각 노드가 0개 혹은 2개의 자식노드 가질 수 있다. (불완전모양)
• 포화이진트리 : 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리
• 완전이진트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져 있어야 함

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징을 가진다.