[자료구조] 이진트리 (BinaryTree)

[BinaryTree]

 

트리는 stack list queue 등 선형자료구조와 다른 관점으로 접근해야한다.
위와 같은 선형자료구조는 목적이 저장, 삭제, 조회등 "데이터관리" 에 초점이 맞춰졌다.

하지만 비선형구조인 트리, 그래프는 "데이터 표현" 에 초점이 맞춰진 자료구조이다.

트리랑 그래프 다 데이터 저장하고 삭제하기 위해서 나온 것이기도 하다.

하지만 트리는 새로운 "데이터 표현" 을 통해서 "데이터 관리" 라는 목적을 실현하는 것들이다.

즉 데이터 표현을 "트리"로 함으로써 "데이터 관리"가 가능하게 된 것이다.

 

예를 들어 보자면,

stack을 보면

 

그냥 원래 있는 도구인 "배열"을 사용해서 자료를 저장하고

저장 추출 조회 ADT만 만든다.

즉 여기서 우리가 만든 것은 데이터구조에 대한 ADT는 없고 그저 기능에 대한 ADT 뿐이다

 

하지만 트리 라는 것을 원래 기본적으로 제공되는 것들로 만들 수 있는게 아니다.

 

따라서  "트리"라는 자료구조를 만드는 작업,

즉 트리를 표현하는 작업부터 시작해야한다!

 

그러므로 stack에는 없었던,

해당 자료구조부터 만드는 "데이터 표현" 부터 시작해야한다는 것이고,

이로써 "데이터 표현"에 초점이 되어야한다는 것이다!

 

---

[이진트리에서 log2n의 의미]

 

이진트리를 사용하는 자료구조나 

이진트리를 사용하지 않지만 재귀구조가 이진트리인

알고리즘들의 시간복잡도에 log2n이 끼어있다

 

이유는 다음과 같다.

 

예를 들어, 

이진트리로 나타낸 N개의 데이터가 있고

여기서 맨 막 노드(시간복잡도이므로)를

참조한다고 할때 비교연산을 몇번 해야할까

 

이진트리이니 이분탐색을 하고

이때 우리는 N/2 씩 쪼개가면서 탐색을 한다.

 

즉, 한번 비교연산을 할때마다 범위가 1/2만큼 줄어든다는 것이다

 

즉, 다음과 같다.

 

 

마지막 탐색 범위가 1인 경우가 K번 반복했을때라고 가정한다면, (1/2)K * N 이 된다는 의미다.

결국 K만큼 반복한다고 했으니 K에 대해 풀어보면 다음과 같다.

 

 

 

따라서 이진트리로 나타낸 N개의 데이터에서 어떤 수를 찾는 과정에 대한 

시간 복잡도는 O(log2N)이라는 것이고 이래서 항상 log2n이 끼어있는 것이다.