트리-자료구조<10>

hans·2022년 4월 30일

자료구조 트리

자료구조 공부 정리

목록 보기

10/14

글에 앞서

오늘은 드디어 비선형 구조인 트리에 대해 공부를 시작헀다
비선형 구조 부터가 진짜 자료구조의 벽에 시작이라는데 잘극복하기를 나 자신에게 바라며
트리에 대해 공부한 내용을 천천히 정리해 나가보자

오늘 정리해볼 내용

1.트리의 기본적인 구조
2.트리 관련 용어
3.이진 트리,서브 트리의 개념

1.트리의 기본적인 구조

트리는 계층적 관계를 표현하는 자료구조이다

계층적 관계라는 말은 처음 공부할 당시에는 생소한 단어였지만 예시를 그림으로 확인하니
어떤 느낌인지 바로 알수있었다

그림에 예시 말고도 족보,조직도,선택 알고리즘 등등 우리가 접할수 있는 다양한 사례가 존재한다
트리는 말그대로 나무가 가지를 늘려가는 형태와 유사하다

2.트리 관련 용어

트리와 관련된 용어들을 정리해 보자

위의 그림을 기준으로 정리한다

노드(node)
트리의 구성요소에 해당하는 A,B,C,D,E,F,와 같은 요소
간선(edge)
노드와 노드를 연결하는 연결선
루트 노드(root node)
트리 구조에서 최상위에 존재하는 A와 같은 노드
단말 노드(terminal node)
아래로 또 다른 노드가 연결되어 있지 않는 E,F,C,D와 같은 노드
내부 노드(internal node)
단말 노드를 제외한 모든 노드로 A,B와 같은 노드

노드간의 관계

부모,자식 관계
그림에서 A와 B는 부모관계 이다 A에서 B가 파생된 관계
형제 관계
같은 부모 A 에서 파생된 관계들 끼리는 형제 관계라고 한다 (B,C,D는 A에서 파생됨으로 형제 관계이다)
후손 관계
A와E는 후손관계 이다

관계는 상대적으로 결정된다
A,B가 부모관계에서 B가 자식이지만 B,E에서는 B가 부모가 된다

3.이진 트리,서브 트리의 개념

서브트리의 이해
큰 트리에 속하는 작은 트리들을 가리켜 서브 트리 라고 명칭한다
D,E가 자식 노드를 생성한다면 B입장에서는 D,E에 파생된 트로 또한 서브 트리가 된다
이진 트리

이진 트리의 조건
1.루트 노드를 중심으로 두 개의 서브트리로 나눠진다
2.나뉘어진 두 서브 트리도 모두 이진 트리여야 한다

트리의 어떤 부분을 짤라놓고 봐도 이진 트리를 만족해야한다
4번 그림역시 이진트리의 조건을 만족한다

이런 트리는 당연히 이진 트리가 맞다
이진 트리의 조건을 만족시키지 않는것 처럼 보이지만 사실 이것은 일종의 이진트리의 약속인데
노드를 더 연결해서 2개의 이진트리를 만족시킬수있다면 이진 트리이다
즉 위의 그림에서 B,D,F,G,C,G에 노드를 더 추가한다면 이진트리 조건이 만족된다 그러면
추가해서 만족할수만 있다면 그것또한 이진트로이다
여기서 추가해서 공집합을 연결시키면 이해가 훨씬 수월하다