[TIL][02.19] 비선형 자료구조, 트리, 이진트리, 이진검색, 분할정복

비선형 자료구조

데이터가 선형적으로 배치되지 않고, 계층적 또는 비계층적으로 연결된 구조

복잡한 관계를 표현하고, 효율적인 데이터 검색 및 관리 가능

종류 : 트리, 그래프

연속된 메모리 구조(선형) : 배열, 리스트, 셋, 큐, 스택 ...

 

트리

 

사이클x, 부모, 자식 존재

 

노드: 데이터의 단위(정점)

루트: 트리의 최상위 노드(첫 노드)

리프: 자식 노드가 없는 노드(끝 노드)

서브트리: 특정 노드를 루트로 하는 하위 트리

높이: 트리의 루트에서 가장 깊은 리프까지의 경로 길이(전체 깊이)

깊이: 특정 노드가 루트에서 얼마나 떨어져 있는지를 나타냅니다

간선: 부모 노드와 자식 노드를 연결,트리는 사이클이 없고, 항상 연결되어 있어야 함. 노드 수가 n이면 간선의 수는 항상 n-1

 

이진트리

자식이 둘만 있는 트리

전위탐색:

중위탐색:

후위탐색:

 

이진검색(분할정복)

• 어떤 노드를 찾기 위해 모든 노드를 순회해야 한다면(완전탐색) O(n)이 된다. 이것을 O(log n)으로 만들 수 있는 방법이 이진 검색이다. 조건: 모든 노드가 정렬되어 있어야 함
• java.util.Arrays.binarySearch()
• 트리구조에서 이진검색되는 API : java.util.TreeSet
• TreeSet은 삽입할 때마다 정렬, 검색, 삽입, 삭제가 O(log n)
• HashSet은 순서를 보장하지 않음. 삽입, 삭제, 검색의 평균 시간 복잡도는 O(1). 정렬하려면 별도의 작업이 필요하며, 이로 인해 성능 차이가 발생할 수 있음