Tree 구조는 뭘까요…🥲

Tree, TreeMap, TreeSet.

이번에는 tree에 대하여 정리 해볼려고 합니다!

Tree? what the fxxk??

tree 구조는 무엇일까요?

일반적으로 저희가 나무(tree) 를 생각하면

나무는 기둥에서 여러가지 가지로 나뉘어서 흩어져 있습니다. 이러한 의미를 그대로 계승하여 네이밍을 한것이라고 생각하면 좋습니다!

tree 구조란 : 최상위 Root값을 기준으로 왼쪽과 오른쪽으로 데이터들이 뻗어나가 있는 형태를 말합니다.

어? 그러면 저희가 알고있는 선형적 자료구조(list,map,set,array) 의 개념이랑 다르게 비선형적 자료구조라고 할수 있겠죠??

 

 

 

여기서 비선형구조란,

계층도를 떠올리면 이해가 가기 쉬울겁니다. 한가지의 값을 기준으로 아래로 계속 계층적으로 뻗어나가는것입니다.

(역시 말보단 사진이지 ㅋ)

위와 같이 정렬되 있는것을 Tree Data Structure 라고 합니다!

이게 어떻게 가능한걸까요?? 저희가 알고 있는 배열의 구조는 무조건 선형구조라고 생각을 해왔는데 말이지요.

저도 알아봤는데 이번에, tree의 자료구조는 root를 기준으로 왼쪽과 오른쪽에 하나의 주소지를 가지고 있는겁니다!.

그래서 부모노드의 왼쪽, 오른쪽 주소지를 통해서 데이터가 자식노드와 서로 연결을 시켜주는겁니다.

 

 

 

한마디로 쉽게 말해서 데이터를 = Node 라고 생각하고,

저러한 계층도의 구조 == Tree 라고 생각을 해봅시다..

그렇다면 Node를 생성하고 관리하는 클래스에는 Node를 생성할때 Node를 기준으로 왼쪽, 오른쪽 주소지를 만들어서 할당시켜줍니다.

당연히 맨처음에 Tree 구조에서 Node를 생성하게 되면 root값이 null로 되있을테니 추가하는 Node를 root로 설정을 합니다.

그리고 그 이후에 들어오는 Node는 일단 root가 null인지 확인하고 null이 아니면 root값에 있는 Node의 왼쪽 오른쪽 주소지중 하나를

부여받고 밑으로 뻗어나가는 겁니다. 그와 동시에 내려간 Node에게도 역시 왼쪽,오른쪽 주소지를 할당해줍니다.

자 이게 뭐라는건지 모르시겠죠??….저도 사실 쓰면서 이게 맞나 싶긴해요 ㅋ

 

 

그래도 최대한 쉽게 표현하기 위해 노력하고 있답니다…..

근데 이 tree 구조를 왜? 언제? 어디서? 성능은? 이걸 궁금하지 않고 모른다면 당연히 tree구조도 알 필요가 없겠다 생각이 들겠죠?

아니 어디서 왜 쓰는지도 모르는데 그걸 알아서 어따 써요.. 그럴바엔 그냥 선형데이터 구조를 쓰고 말지….

그래서 일단 위에 설명을 잠시 접어두고, 일단 tree 구조의 장점과 단점 그리고 언제 쓰는지를 알아보겠습니다!!!

---

트리 는 계층적인 관계 표현에 쓰이기 때문에,

OS의 FileSystem 구조나 대용량의 데이터를 계층적으로 저장할 때 많이 쓰이는 자료구조 가 되겠습니다.

라고 하는데 좀더 쉽게 풀이해보겠습니다.

일단 일반적으로 모든 tree 구조가 계층적으로 표현이 되기는 하지만 이것이 곧 대용량의 데이터를

빠르고, 간단하게 처리할수 있다는 뜻은 아닙니다….

 

우리는 이제 이진검색트리(binary search tree) 에 대해서 알아야지 tree가 이래서 좋구나??? 할겁니다

 

이진검색트리 (BinarySearch Tree)

 

자 용어적인거 다 꺼지라 하고 쉽게 말해봅시다.

트리구조는 루트값을 기준으로 오른쪽 왼쪽 아무곳이나 가지처럼 뻗어가서 데이터가 저장이 된다고했죠?

그렇다면 이진트리는 뭘까요?

왼쪽, 오른쪽에 부모노드가 최대 2개의 노드만 가질 수 있는것을 의미합니다.

위에서 봤던 이 사진이 이진트리에요!!!

 

 

자 그렇다면 아 이진트리는 부모노드가 최대 2개의 노드만 가지는거구나!

그러면 검색은 뭐지? 이진검색??? 어디서 들어봤는데??

자 이진검색=이진탐색정렬 + 검색

모든 데이터를 반절로 나눠서 탐색을 한다는것입니다!!

한번 검색을 시도할때마다 데이터를 반절로 나눠서 그 반절을 기준으로 찾고자 하는 데이터의 값이 크냐 작냐로 나뉘어서

크다면 작은쪽을 다 무시하고 큰쪽을 또 반절로 나눠서 나눈값 기준으로 크냐 작냐를 계속해서 비교해 나가다가 결국에는

찾고자 하는 값에 도달합니다!!!

 

 

그렇다면, 이진검색트리란???

Root노드를 기준으로 데이터의 값이 크면 오른쪽 작으면 왼쪽으로 정렬하는것입니다..

구현 방식을 생각해보면 간단해요.

만약에 root보다 저장하고자 하는 데이터가 작다면 root의 왼쪽 주소지를 저장하고자 하는 Node에게 부여합니다.

그리고 또 다시 저장하고자 하는 데이터가 root 보다 작다면??

다시 왼쪽 노드로 갑니다. 갔더니 이미 노드 한개가 자리를 차지하고 있죠?? 이제 그 노드보다 값이 큰지 작은지를 비교합니다.

만약에 크다면? 자리를 바꿔야 겠죠??? 자리를 바꾸고 기존에 있던 노드는 자신보다 작은값이 오면 줄려고 했던 주소지에 가있게

되는겁니다.

이걸 왼쪽오른쪽 주소지 딱 2개만 둬서 이진 트리라는걸 만든거고 값이 크냐 작냐는 기준을 추가해서 이진검색트리를 완성할 수 있게 된겁니다!.

---

자 장단점을 알고자 했는데 왜 여기까지 왔냐고요???

그 이유는 그냥 tree구조의 장점이 좋아서 쓰는게 아니라

이진검색트리의 구조가 매우 효율이 좋아서 쓰는거에요!!

 

 

그냥 tree구조는 저장되있는 값이 랜덤이기때문에 크고작고를 다시 정렬 해줘야하지만

이진검색트리를 만들어놓으면 자동으로 정렬이 되는거죠!!

 

 

그래서 애는 데이터를 삽입할때마다 항상 자동으로 데이터가 정렬이 되기에

검색에 있어서 속도가 매우 빨라서, 만약에 클라이언트가 저희 홈페이지는 검색이 제일 빠르게 해주세요!

라고 요청이오면 이진검색트리를 쓰는게 좋은거죠!! (그 중에서도 향샹된 기능을 자랑하는 레드블랙 이진트리를 사용하는걸 권합니다)

이진검색트리는 무엇보다 검색에 있어서는 성능을 보장하기때문에, 이점을 생각해뒀다가 클라이언트의 요청에 따라 어떤

자료구조를 쓸까? 에 도움이 될수 있는거겠죠…

 

 

자자 오늘은 여기까지만 설명하고 다음번에 tree를 구현함과 동시에 순회방식까지 한번 구현해보는걸로 하겠습니다.

(이 정도만 이해해도 ㅈ나 장한건디;;)